Re: [freehaven-dev] Literature repository, multi-e/single-d cryptoscheme

[dmolnar@belegost.mit.edu]

On Sun, 7 May 2000, Michael J Freedman wrote:

>   A message M is encrypted by keys {e_1 ... e_n}
>   M can be decrypted by any d_i \element {d_1 ... d_n}, 
>       the corresponding private keys.

The most straightforward solution here is to encrypt M a total of n times,
each time with a separate public key e_i. Concatenate together and pass
around. Then any single d_i can decrypt the corresponding encrypted
message and recover the message. I think this is what PGP does. 
 
This has message expansion linear in the number of recipients. Does that
matter? Well, for large messages it's awful. If we use a hybrid
cryptosystem that works like this :

	1) Generate random symmetric key K 128 bits long. 
	2) Encrypt M with K -- E_K(M).
	3) Encrypt K with public keys e_1 -- e_n
	4) Concatenate encrypted Ks and E_K(M)

then we have total size |M| + 128*n bits. Not so bad. 

Applied Crypto also has a section on this with references -- 22.7 ,
p.523 (note that "multiple public-key cryptography" actually seems to be
discussed afterwards, not before)  and protocol I haven't finished reading
yet. 

Thanks, 
-David