# Do any one-key-of-many cryptographic schemes exist?

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?

• 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]. $\;$ – user991 Mar 12 '14 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 '14 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. $\;$ – user991 Mar 12 '14 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 '14 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. $\;\;\;$ – user991 Mar 12 '14 at 1:00

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.

• Oh that's awesome! Way more efficient than encrypting the entire message n times. – Claudiu Mar 13 '14 at 22:19
• 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 '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 '14 at 3:16
• @D.W. thats also standardized in PKCS#7 (enveloped-data), see e.g. here – DrLecter Mar 22 '14 at 13:10
• Evil technique; Epk1(k) produces k1 and Epk2(k) produces k2 that decrypt the cyphertext to two different messages, one innocuous and one nasty. – Joshua Jul 15 '16 at 3:18