# How to cipher with N public keys and decipher with ANY of the N private keys?

X = plaintext

Given N key pairs:

P1 = (P1.private, P1.public)
...
PN = (PN.private, P1.public)


I want to find 2 function Cipher and Decipher such as

Cipher(X, P1.public, P2.public...PN.public) = X encrypted
Decipher(X encrypted, P1.private) = X
...
Decipher(X encrypted, PN.private) = X


Does such scheme exist?

• Looks like you're after threshold decryption, with in this case a threshold of 1. As answered below, you may use hybrid encryption at the cost of a per-recipient wrapping of the symmetric key actually used to encrypt the message. This however, is not flexible for any higher than 1 threshold. Similarly, threshold decryption schemes may exist that are better suited for a low threshold (like 1), or better suited for higher thresholds (t of n), where likely t is approx $n / 2$ or ${2n} / 3$, depending on the protocol you're after. Search for "threshold decryption". – cypherfox Apr 22 '18 at 11:34

Pick your favorite KEM, say RSA-KEM. Let $P_1, P_2, \ldots, P_n$ be the public keys, and $(k, c) = \operatorname{Encap}(P)$ be a random key $k$ and encapsulation $c$ of the key that can be opened by $k = \operatorname{Decap}(S, c)$ if $S$ is the secret key corresponding to $P$.
Let $(k_i, c_i) = \operatorname{Encap}(P_i)$. Pick $k$ uniformly at random and yield $$c = ((c_1, k'_1), (c_2, k'_2), \ldots, (c_n, k'_n)), \quad\text{where}\quad k'_i = k \oplus k_i,$$ as the encapsulation of $k$. Then use $k$ as a key for a DEM, or authenticated encryption, say NaCl crypto_secretbox_xsalsa20poly1305, to transmit your message. The $i^{\mathit{th}}$ recipient can recover $k$ by decapsulating $k_i$ from $c_i$ and computing $k = k'_i \oplus k_i$ and thereby decrypt the message.