Consider a protocol, wherein Alice wants to send a message $M$ to many friends $F_1, F_2, \dots F_n$, from whom she has (some form of) public keys ($e_{F_i}$, with private key $d_{F_i}$). She does not want her friend Bob ($B=F_1$) to know that she sent the same message to her friend Charlie ($C=F_2$), and vice versa.

Alice wants to send out one single message, as opposed to distinct messages to every recipient. (Think for example a single email message, or publication on a website, as opposed to distinct emails)

One such scheme would be to encrypt the message with a symmetric key $K$, and attach a dictionary of ($F_i$: $e_{F_i}\{K\}$). In this scheme however, Charlie will notice the presence of a key for Bob (and vice versa).
Even when hiding the index $F_i$ in the dictionary, Charlie might be able to find out that Bob is in the list of recipients.

Is such a scheme possible? Is such a scheme possible, without revealing even the number of recipients?

  • 1
    $\begingroup$ @RubenDeSmet I started to write out an answer but it got a bit too complicated. Instead I think it would be better to give you this link to Asynchronous Ratcheting Tree and answer any questions you may have. (1/n) $\endgroup$ – cypherfox May 8 '18 at 15:19
  • 1
    $\begingroup$ @RubenDeSmet To extend on squeamish-ossifrage' recommendation for hybrid encryption using OpenPGP/GnuPG, the key privacy issues do not apply to Curve25519, which is great if all your friends use Curve25519, which they would have to do for ART anyway. ART is intended for group communications, not this email multicast or whiteboard broadcast. (2/n) $\endgroup$ – cypherfox May 8 '18 at 15:21
  • 1
    $\begingroup$ @RubenDeSmet While writing out my answer I arrived at another alternative you may be interested in. Semiprivate keys, or a simpler to describe as a dual key. One signing key and one encryption key. However, these keys are tightly related which eliminates the issues with encrypt-then-sign. Under this model Alice gives Bob the semiprivate key. Only Bob can decrypt Alice' messages. But Bob may share this key with Carol and Dave. This may not be so exciting so far, but there is another property here that is useful. (3/n) $\endgroup$ – cypherfox May 8 '18 at 15:25
  • 1
    $\begingroup$ @RubenDeSmet With semiprivate keys we have another signing key. This key enables third parties to verify that Alice did sign the message without being able to recover the decryption key to read the message. This is useful for key-value stores for instance. (4/n) $\endgroup$ – cypherfox May 8 '18 at 15:26
  • 1
    $\begingroup$ @RubenDeSmet The only downside to this method is that you cannot selectively revoke consumers. With hybrid encryption and trees you can. Better, with ART you can archieve forward secrecy while each participant can change their keys which derives a new group key. If a user leaves the group, they cannot read new messages. If a new user joins, they cannot read old messages. (5/5) $\endgroup$ – cypherfox May 8 '18 at 15:28

OpenPGP supports an approximation to what you seek, albeit with at best weak privacy guarantees: To transmit the message $m$, Alice picks a session key $k$ and sends $$E_{f_1}(k) \mathbin\| E_{f_2}(k) \mathbin\| \cdots E_{f_n}(k) \mathbin\| \operatorname{AES-CFB'}_k(m),$$ more or less. Here $\operatorname{AES-CFB'}$ is OpenPGP's bespoke variant of CFB mode. See RFC 4880, §5.1 for details of how public keys are identified or not.

Decrypting such a message to many recipients is slower, of course, because it requires trying to decrypt every session key encapsulation $E_{f_i}(k)$ with every private key known to the user. Variants of this scheme with long-term DH-style shared secrets could enable recipients to cache the long-term shared secret under which a per-message session key is encrypted to make this more efficient for many messages.

The privacy guarantees are weak because not every public-key encryption or KEM scheme provides the property called key privacy or key anonymity. For example, it is feasible for an adversary to distinguish a collection of RSAES-PKCS1-v1_5 ciphertexts (or RSAES-OAEP, but OpenPGP uses PKCS#1 v1.5) under a target public key from a collection of ciphertexts under any other public key, by solving the German tank problem.

You could use a nonstandard RSA-KEM encryption procedure as follows: Pick $1 < x < n$ uniformly at random, compute $y = x^3 \bmod n$, reject and start over if $y \geq 2^{\ell - 1}$ where $2^{\ell - 1} < n < 2^\ell$, and otherwise yield $y$ as the encapsulation of $k = H(x)$. The encapsulation $y$ is uniform random in $\{2,3,4,\ldots,2^{\ell - 1} - 1\}$, so it reveals nothing about which $\ell$-bit modulus is used.* This variant is slower than standard RSA-KEM, but the expected number of trials to pick $x$ is under 2, and decryption remains the same as standard RSA-KEM. Bellare et al. suggest a corresponding variant of RSAES-OAEP which they dub RAEP. The security is essentially the same as RSAES-OAEP. Probably the same could be done in OpenPGP with RSAES-PKCS1-v1_5 by trying a different session key, but you are limited to a single recipient in that case.

Other cryptosystems may naturally provide key privacy, such as ECIES and variants where the appendix is a uniform random element of a standard group. But it's not a standard criterion for public-key encryption/KEM schemes, so it takes further scrutiny than standard security advertisements to be confident that any particular cryptosystem you use provides or can be adapted provide key privacy.

* Note that there are many ways to generate RSA keys. In an attempt to generate a 2048-bit modulus $n$, some methods pick 1024-bit primes $p$ and $q$ uniformly at random, and with nonnegligible probability will yield for $n = p\cdot q$ a 2047-bit modulus instead of a 2048-bit one. In this case, by rejecting $y \geq 2^{\lfloor\lg n\rfloor}$ you would partition the anonymity set of recipients into two: the 2047-bit moduli and the 2048-bit moduli. If this concerns you, you could (say) reject $y \geq 2^{2046}$ for any 2047- or 2048-bit moduli. This will increase the rejection rate, but at worst it will double.


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.