Is it possible to encrypt data with two public keys?

Question

Can we encrypt data with two public keys and the encrypted data only needs one private key to decrypt once encrypted?

Answer 1

Yes, we can encrypt with two public keys $\text{Pub}_0$ and $\text{Pub}_1$, then decipher with one private key $\text{Pub}_i$ matching either one of the two public keys. As noted in comment, the simplest method is to encipher to both keys, at the expense of doubling the ciphertext size.

But for large plaintext, we'll be using hybrid encryption, and then there's a bounded size penalty for each recipient. For two keys key pairs $(\text{Pub}_0,\operatorname{Priv}_0)$ and $(\text{Pub}_1,\operatorname{Priv}_1)$, and assuming recipients know if they are recipient $0$ or $1$, the encryption goes:

• draw a random symmetric key $K$
• asymmetrically encrypt $K$ with each public key forming the two $C_i=\operatorname{Enc}(\operatorname{Pub}_i,K)$
• put the results $C_0\mathbin\|C_1$ at start of ciphertext
• symmetrically encrypt the data using $K$ (e.g. with AES-GCM), forming the rest of the ciphertext.

Decryption by recipient $i$ goes

• from the start of the ciphertext $C_0\mathbin\|C_1$ extract $C_i=\operatorname{Enc}(\operatorname{Pub}_i,K)$
• asymmetrically decrypt $K=\operatorname{Dec}(\operatorname{Priv}_i,C_i)$
• symmetrically decrypt the rest of the ciphertext data using $K$, getting the plaintext.

Extensions are possible so that recipients do not need to know their index (by adding a public key identifier to each $C_i$). This is common, e.g. with (Open)PGP/GPG asymmetric encryption, when it sends encrypted to several recipients.

A slightly more complex extension allows that while hiding who are the recipients.