How to encrypt one message for multiple recipients?

Question

What are the fundamentals to accomplish data encryption with exactly two keys (which could be password-based), but needing only one (either one) of the two keys to decrypt the data?

For example, data is encrypted with a user's password and his company's password, and then he or his company can decrypt the data. Neither of them know the other password. Only one copy of the encrypted data is stored.

I don't mean public/private key. Probably via symmetric key cryptography and maybe it involves something like XORing the keys together to use them for encrypting.

Update: I would also like to find a solution that does not involve storing the keys at all.

Answer 1

Generally speaking, what you do is encrypt the data with a randomly generated key, and then append versions of that random key that have been encrypted with every known key. So anybody with a valid key can discover the 'real' key that was used to encrypt the data.

Answer 2

The way this is customarily done is to generate a single symmetric key to encrypt the data. Then you encrypt the symmetric key with each recipient's key or password to that they can decrypt it on their own. S/MIME (actually the Cryptographic Message Syntax on which S/MIME is based) uses this technique.

This way, you only have to store one copy of the encrypted message, but multiple copies of its key.

Answer 3

I think I thought of a solution that would work:

D = data to encrypt
h1 = hash(userpassword)
h2 = hash(companyPassword)
k = h1 concat h2

E = function to encrypt
//C is the encrypted data
C = E_h1(h2) concat E_h2(h1) concat E_k(D)

Then either person can decrypt the hash of the other person, and then combine them to decrypt the rest of the data.

Perhaps there is a better solution than this though?

Answer 4

@Brian,

That solution will work, although it becomes unwieldy when there are more than 2 keys.

Answer 5

Thanks erickson and Brad Wilson, those seem like great methods because you can easily change either password without re-encrypting all data. My suggested solution didn't have that property.

Answer 6

In the more general case, a secret (in this application, a decryption key for the data) can be split into shares such that some threshold number of these shares is required to recover the secret. This is known as secret sharing or with n shares and a threshold of t, a (t,n)-threshold scheme.

One way this can be done is by creating a polynomial of order t-1, setting the secret as the first coefficient, and choosing the rest of the coefficients at random. Then, n random points on this curve are selected and become the shares.