Return to Answer

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.}

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.}

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 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.)

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.}

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.}

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 create a nonstandard RSA-based public-key encryption or KEM scheme that chooses ciphertext representative $c + b n$ instead of $c$ whenever $c < 2^{\lceil\lg n\rceil} - n$, where $n$ is the recipient's public RSA modulus, and $b \in \{0,1\}$ is a coin toss giving 0 with probability $n/2^{\lceil\lg n\rceil}$. (Alternatively, flip a coin $\lceil\lg n\rceil$ times and interpret as the binary expansion of an integer $u$ in your favorite bit order: if $u < n$, use $b = 0$; otherwise use $b = 1$.) This might provide key privacy—though the scheme I made up on the spot here for crypto.SE needs further scrutiny to say for sure!^*

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.

_{^* Let $\ell = \lceil\lg n\rceil$, so that $2^{\ell - 1} < 2^\ell - n < n < 2^\ell$. If $c$ is uniform random modulo $n$, then $\Pr[0 \leq c < 2^\ell - n] = \frac{2^\ell - n}{n}$. If $u$ is uniform random modulo $2^\ell$, then $\Pr[0 \leq u < 2^\ell - n] = \frac{2^\ell - n}{2^\ell}$. For $c + b n$ to be uniform random modulo $2^\ell$, we can choose $b \in \{0,1\}$ with \begin{align*} \Pr[b = 0 &\mathrel| 0 \leq c < 2^\ell - n] = p, \\ \Pr[b = 0 &\mathrel| 2^\ell - n \leq c < n] = 1, \\ \end{align*} for some $p$. Note that $\Pr[0 \leq c + b n < n \mathrel| b = 1] = 0$. Clearly $\Pr[0 \leq c + b n < 2^\ell] = 1$. For $c + b n$ to be uniform, we need \begin{align*} \frac{2^\ell - n}{2^\ell} &= \Pr[0 \leq c + b n < 2^\ell - n] \\ &= \Pr[0 \leq c + b n < 2^\ell - n \mathrel| 0 \leq c < 2^\ell - n] \Pr[0 \leq c < 2^\ell - n] \\ &= \Pr[b = 0 \mathrel| 0 \leq c < 2^\ell - n] \Pr[0 \leq c < 2^\ell - n] \\ &= p \cdot \frac{2^\ell - n}{n}, \end{align*} so we must have $\Pr[b = 0 \mathrel| c < 2^\ell - n] = p = n/2^\ell = n/2^{\lceil\lg n\rceil}$.}  

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 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.)

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.}