A Hypothetical form of Broadcast Encryption

I have pursued the mental exercise, of supposing that a group of (n) people might exist, who are to receive a broadcast, encrypted message, but in such a way that two of those recipients’ credentials are required, to decrypt that message. The assumed author of the message is a secure party, entrusted to keep all the encryption details of the system.

The basis of my exercise is, that RSA encryption and hybrid encryption may be used, with the twist, that as long as the modulus is the same for two transactions, a symmetrical key can be encrypted twice, in order to be decrypted twice. A formalized way to write this could be:

C = (T ^ E1) ^ E2 mod (p)(q)

T = (C ^ D2) ^ D1 mod (p)(q)

Where (p) and (q) are random 1024-bit prime numbers, (T) stands for the symmetrical encryption key, and (C) stands for the encrypted form of that key. Clearly, (p) and (q) would be filtered by the central party, such that neither (p-1) nor (q-1) are divisible by either (E1) or (E2), which are, 65537 and 32771 respectively.

My concept continues, that the central party associates a single prime number with each distributed recipient for the long term, and that the recipient is not allowed to know their own prime number. For any pair of recipients, a modulus (p)(q) follows, which the recipients store, for each other recipient, that the current recipient may eventually want to combine his key with.

(Corrected 09/22/2018, 18h00 … )

(As of 09/21/2018, 23h40 : )

Additionally, there will be one parameter known about each recipient, that places any two in a fixed order, such as their exact birth-date, appended to their actual Recipient IDThis information does not need to be stored with the recipient. And in order to obscure this information further, the order in which recipients are named in any one database- or message- entry, can be randomized.

In addition to the modulus, each recipient is to know the private key, either (D1) or (D2) – but not both – which they must use when combining their decryption procedure with each other recipient. Thus, there will be (n-1) entries in the database of each recipient, each of which consists of:

{ ‘Recipient 2 ID’ , (p)(q) , (D1|D2) }

These credentials need to be communicated to each recipient in a secure way, but that secure way may consist of single-recipient, public-key cryptography, that uses a separate set of encryption keys not explained here.

When the author initializes the recipients, it orders its database of recipients into pairs, and extracts from the database the associated prime number of each of generates two random prime numbers for the two resulting recipients. It then computes the Totient Product of the two prime numbers, which can also be written:

(p-1)(q-1)

And stores that totient product along with the modulus (p)(q). The author next associates (E1) with the ‘first’ recipient out of the pair, and (E2) with the ‘second’ out of the pair. The author then uses the totient product to compute either (D1) or (D2) of the respective recipient, as the multiplicative inverse of either (E1) or (E2), which is to be communicated to the recipient securely, before any broadcast scenario.

When the author composes a message, it traverses its database of recipients, again ordering them into pairs, but this time, only computes uses the stored modulus (p)(q) for the pair, and encrypts the per-message symmetrical key, by raising it to the power of (E1)(E2) within that modulus. A list of up to (n)(n-1)/2 entries:

{ ‘Recipient 1 ID’ , ‘Recipient 2 ID’ , (C) }

Results, which the author inserts into the message, before the symmetrically encrypted message proper.

This message can now be broadcast.

(Update 09/22/2018, 18h00 : )

I suppose that a potential question I should answer would be, ‘Why was Dirk not satisfied with official versions of Threshold Encryption?’ The reason would be the fact, that those versions assume, that pieces of a key are being distributed unequally to recipients. And then one side-effect would be, that if one or more recipients’ credentials were compromised, the entire set of keys would also be so.

Additionally, other, more-conventional methods which exist, by which two or more recipients can combine their credentials, in order to decrypt a message successfully, also require that at one point in time, one recipient have access to two or more data-sets, to do so. My approach explained in this posting has as advantage, that although the product (D1)(D2) can be computed, each of these private exponents can be applied sequentially, without one of the recipients ever knowing both.


 

Erratum:

In its original form, this method is not secure, because The Euclidean Algorithm is capable of computing the GCD between two large prime numbers in polynomial time, even if the GCD is say, 1024 bits long. Because each recipient knows their modulus, for use with each other recipient, if two such moduli were known to have the current recipient’s prime factor in common, that recipient could compute the prime factor, and could divide each modulus by it. That way, the individual recipient could break the system – And decrypt a message alone, which was supposed to require two recipients to decrypt.

To turn this approach into a secure one, the central party must actually store a completely different modulus for each recipient-pair, which is composed of new prime factors afresh.


 

But I suppose that a way in which some implementers might want to extend my own concept of Broadcast Encryption, would be to allow triplets of recipients to decrypt a message, instead of always pairs. In that case, I feel that the best way to proceed, is still, to determine a modulus, based on ‘the first 2′ recipients out of any 3. But in that case, (E3) and a matching (D3) must be defined, where (E3) may be 17489.

Additionally, each potential recipient would then need to have a database, with (n-1)(n-2)/2 entries, of the form:

{ ‘Recipient 2 ID’ , ‘Recipient 3 ID’ , (D1|D2|D3) , (1|2|3) [, (p)(q) ] }

And, any messages would potentially need to contain (n)(n-1)(n-2)/6 entries of the form:

{ ‘Recipient 1 ID’ , ‘Recipient 2 ID’ , ‘Recipient 3 ID’ , (C) }

In addition, (p) and (q) would need to have been filtered by the central party, before being issued to the recipients, so that neither (p-1) nor (q-1) are divisible by any one out of (E1), (E2), or (E3).

With my scheme, if the central party was to find out that one or more of its recipients have been compromised, the central party could simply stop encrypting future messages to those recipients, as part of any pair, or as part of any triplet.

Dirk

 

Print Friendly, PDF & Email

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

This site uses Akismet to reduce spam. Learn how your comment data is processed.