Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm pretty sure I understand how public/private key cryptography works. Anybody can encrypt a message using a well-known public key, but only the person who holds the private key can decrypt it.

My question concerns securely sending a message to multiple people. Say there are n public/private key pairs. Is there a way to encrypt a message using the n public keys such that any one of the private key holders can decrypt the message in its entirety, but nobody else can?

Further, unrelated to public/private key cryptography, is there any scheme where there are n shared keys such that anybody who knows the n keys can encrypt a message such that any one of the shared keys can decrypt the message in its entirety, but nobody else can?

share|improve this question
    
The only way I can see to make your shared-key question non-trivial is if either each shared key has a public “encapsulation” or [$\hspace{.02 in}$you do _not_ care about ensuring that each recipient gets the same message and you want the ciphertext length to scale sublinearly with n]. $\;$ –  Ricky Demer Mar 12 at 0:14
    
@RickyDemer: I do want each recipient to get the same message. Why is it trivial as it stands? Say there are five people and with each of them I share a different key, a, b, c, d, e, respectively. They each only know one of the keys. I want to encrypt M into E so that each of the five people can fully decrypt E back to M. And yep I don't want len(E)=5*len(M). What's a trivial way to do that? –  Claudiu Mar 12 at 0:37
    
It's trivially impossible as it stands, since the sender could just use random strings of the appropriate lengths instead of the actual keys for a subset of the recipients. $\;$ –  Ricky Demer Mar 12 at 0:42
    
@RickyDemer: Oh heh trivial in that sense. Hmm so what if he does - why does that make it impossible? Because there's no way a static subset of keys would be able to decrypt an essentially infinite number of possibilities? In any case, can you think of any options where the ciphertext length does scale sublinearly with n but the original message can be retrieved (perhaps from a different part of each decryption)? –  Claudiu Mar 12 at 0:48
    
That makes it impossible because otherwise a passive eavesdropper could decrypt by just using a random key. $\:$ (Never mind about me typing up an answer now; I don't have as much to say as I thought I did.) $\:$ The main possibility that I'm aware of for getting the ciphertext to scale sublinearly with n (even if one doesn't worry a malicious sender) is broadcast encryption. $\:$ Perhaps multicast encryption (in that page's see also) might work too, but the article doesn't go into much detail. $\;\;\;$ –  Ricky Demer Mar 12 at 1:00
show 1 more comment

1 Answer 1

up vote 4 down vote accepted

Yes, absolutely. Here is the standard construction to address this problem. Let $pk_1,\dots,pk_n$ be the public keys of the $n$ recipients. We pick a random symmetric key $k$, encrypt the message $m$ (using authenticated encryption) under key $k$ to get $c=AE_k(m)$, and then encrypt $k$ under each of the public keys. Finally, we form the whole ciphertext as

$$E_{pk_1}(k),E_{pk_2}(k),\dots,E_{pk_n}(k),c.$$

That's what we treat as our ciphertext. Now any of the $n$ recipients can decrypt (they can recover $k$ using their private key, and then use that to decrypt $c$), but no one else can.

The same method works in the shared-key (symmetric-key) setting as well.

This standard construction is standardized in more detail in "RFC 4880: OpenPGP Message Format" and in PKCS#7 (enveloped-data). (Thanks, David Cary and DrLecter!)

You might also enjoy looking into broadcast encryption, which solves a related problem. It basically allows you to transmit a message to millions of receives, without having a huge blowup in the size of the ciphertext (so it achieves much shorter ciphertexts than the simple scheme above), though there are some details and a little bit of additional coordination required.

For digital signatures, you might enjoy looking at ring signatures and group signatures.

share|improve this answer
    
Oh that's awesome! Way more efficient than encrypting the entire message n times. –  Claudiu Mar 13 at 22:19
2  
This is based on a the same idea as encrypting large amounts of data to one recipient, when efficiency is a concern. Hybrid encryption is a very flexible tool. –  tylo Mar 14 at 14:17
    
+1. Perhaps you might also mention: This standard construction is standardized in more detail in "RFC 4880: OpenPGP Message Format". –  David Cary Mar 22 at 3:16
    
@D.W. thats also standardized in PKCS#7 (enveloped-data), see e.g. here –  DrLecter Mar 22 at 13:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.