Is it possible to encrypt a message in such a way that multiple keys can independently decrypt it?

In other words:

Having knowledge of $key_1, key_2 ...key_N$, which are different symmetrical keys, is it possible to generate a ciphertext that can be independently decrypted using either $key_1$ or $key_2$ or $key_N$, in such a way that the length of the ciphertext is less than directly proportional to $N$?

  • Check out non-committing encryption. Is it what you are looking for? – D.W. Feb 7 '15 at 7:37
  • 3
    If you are confused why there are comments and answers from 3 years ago: I have merged an older question into this one as they were identical with this one being much clearer. And merging keeps the old time-stamps and migrates all answers and comments. – SEJPM Mar 17 at 19:16
up vote 5 down vote accepted

At its simplest, to encrypt a message for $n$ different recipients, you could just make $n$ copies of the message, encrypt each one with a different key, and join the encrypted messages together into a single long ciphertext.

Of course, the disadvantage of this scheme is that the ciphertext length grows linearly with the number of recipients. To avoid this, you can use a simple optimization called key wrapping:

  1. For each message $m$ you want to send, generate a random message key $K_m$.

  2. Encrypt the message $m$ with the key $K_m$.

  3. Make $n$ copies of the key $K_m$, and encrypt each of them with one recipient's key.

  4. Join the encrypted keys and the encrypted message together, and send it to the recipients.

Using this scheme, the total length of the ciphertext still grows with each additional recipient, but only by the length of the encrypted message key, which can be reasonably short (say, 32 bytes per key or so, assuming a 16-byte (= 128-bit) key and 16 bytes of encryption overhead).

To decrypt the message, each of the recipients must first choose the correct encrypted message key, decrypt it with their own key to obtain the message key $K_m$, and then decrypt the message with $K_m$. Of course, this requires some way for the recipients to recognize which of the copies of $K_m$ has been encrypted with their own key. There are several ways to accomplish this efficiently:

  • If the recipients have some public ID, such as a username or an address, you could simply tag each encrypted key with the recipient's ID.

  • Alternatively, you could use something like a cryptographic hash of the recipient's key as their ID.

  • If you don't wish to tag the encrypted keys with any kind of ID (say, because you don't want to reveal who the message has been encrypted for), the recipient can simply try to decrypt each of the encrypted keys with their own key. As long as you use an authenticated encryption algorithm (like any of the key-wrap algorithms I linked to above) to encrypt the keys (which you should do anyway), the recipient can be confident that the key which they succeed in decrypting will be the correct one.

This scheme also offers a reasonably convenient way to add new recipients for an existing message, simply by adding new encrypted message keys to the ciphertext (or transmitting them separately). Of course, you need to know the message key $K_m$ to do this, so this can only be done by the sender or by one of the existing recipients (who are also the parties capable of just sharing the decrypted message by other means, if they want).


Note that, above, I've implicitly assumed that you're using symmetric encryption. However, you can also use the same scheme with asymmetric encryption, using each recipient's public key to encrypt the (symmetric) message key $K_m$.

If fact, when used with public-key encryption, this scheme offers a performance advantage that makes it worth using even when there is only one recipient. The reason is that, compared to symmetric encryption, public-key encryption is slow, produces long ciphertexts, and is just generally unsuitable for encrypting large messages. Thus, rather than trying to directly encrypt a long message $m$ with the recipient's public key, it's much more efficient to encrypt the message with a random symmetric key $K_m$, and then encrypt $K_m$ using the recipient's public key.

This is known as hybrid encryption, and it's what essentially all practical public-key encryption systems actually use to encrypt long messages. The ability (given a suitable message format) to encrypt a single message for multiple recipients is then merely a convenient side effect of this optimization.

One way to do it is to generate a random, single-use key $K$ and encrypt (and preferably authenticate) the message with that. Store the (authenticated) encryption of $K$ under each of $key_1, …, key_N$ alongside the message. The required storage is $\Theta(N + \text{message length})$.

This is routinely done when transmitting messages using asymmetric encryption, for example when sending an email encrypted with PGP to multiple recipient. A the message is encrypted and authenticated with a single-use key, and the encrypted email contains the encryption of that key with each recipient's public key in addition to the ciphertext.

  • for more clarity, your answer should read "encryption of K under key1, …, keyN" – user94293 Mar 17 at 12:53

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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