Two private key asymmetric encryption - possible?

Question

I am wondering if there exists some asymmetric encryption algorithm that would work with two different private keys, so that the encrypted message can be decrypted by either one of such private keys?

Answer 1

Asymmetric keys are never used for encrypting messages (too slow, has a size limit, etc.), only for encrypting small buffers, like symmetric keys for messages.

When you encrypt a message with an asymm. key, you are in fact encrypting a symmetric key which encrypts the message.

Simply encrypt the same symmetric key with two different asymm. keys and you'd get two different cipherblocks which both contain the same symmetric key for the message, so you can decrypt with either one.

Answer 2

You could use a symmetric encryption and secret sharing scheme on top of that, "splitting the key in half".

More on secret sharing: http://en.wikipedia.org/wiki/Secret_sharing

Steps on how I see it:

1. Encrypt the data using (pseudo) randomly generated key.
2. Distribute the secret using Shamir's secret sharing which is the key to two shares, where as one share will suffice to get the key.

The end result is that one (or more) "keys" are required to get the data.

Answer 3

There is no such algorithm as far as I know, but there is a common solution. The enciphered text is transferred together with a set of cryptograms of the symmetric key used to encipher the text itself. Each such cryptogram of the key is a result of enciphering the original key with the public key of one of recipients. Thus, all recipients knowing their private keys may decipher the key used to encipher the data and then decipher the message itself.