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?

  • $\begingroup$ 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". $\endgroup$ – 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.


I found the answer, actually gpg allows this when encrypting a message with several recipient and some info can be found here: https://www.gnupg.org/gph/en/manual.html#AEN111

  • 3
    $\begingroup$ Yes, hybrid encryption makes that easy. Answers are supposed to give solution to the problem in the question, and hte current answer hardly does. In the circumstance, any of the following is appropriate: 1) edit the question to reflect that it is known what's asked is possible and done in gnupg, but more details are wanted (but I fear the question would be a duplicate); 2) put such details in the answer (same fear); 3) delete the question. $\endgroup$ – fgrieu Feb 21 '18 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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