# How can one encrypt with RSA (or ElGamal) without revealing whom the ciphertext is intended for?

Imagine Alice wants to encrypt for Bob and post this encryption publicly, so that only Bob can decrypt but no one can other than Alice or Bob tell that the message was encrypted for Bob.

The naive approach leaks some information. If Alice posts $y = x^e \bmod{n}$, then an observer can conclude that the recipient has a public key $n > y$, and can therefore eliminate many guesses as to whom the recipient is. Potentially this advantage can be amplified, depending on the higher-level protocol.

My thought was Alice can generate a random $r$ of size $2^{\textrm{L}}$, where $L$ is the largest allowable key size, and post $y + rn$. Then, Bob can consider the residue mod $n$ when decrypting.

Similarly, in ElGamal, Alice can pick random $r_1$ and $r_2$, then post $\langle c_1 + r_1 p, c_2 + r_2 p \rangle$.

Do these constructions achieve their intended goals?

A use case for this is in PGP encryption. Assuming Alice strips the key id from the outer packet, can she post a PGP encryption without leaking information about her intended recipient?

-
You may take a look at the key privacy property. –  DrLecter May 20 at 20:54
This is a great pointer. For RSA: "Our variant simply repeats the ciphertext computation, each time using new coins, until the ciphertext $y$ satisfies $1 \le y \le 2k−2$, where $k$ is the length of $N$." For PGP, we'd need to assume the same proof works for EME-PCKS#1-v1.5 as works for OAEP. Their construction works with preexisting decryptors, which is nice. Their other claim is that ElGamal already has key privacy. –  Max Krohn May 20 at 21:07
Be careful. For RSA this assumes that all users have a k bit modulus and for ElGamal that all keys are generated with respect to the same group (which is not unreasonable especially for ECC ElGamal). –  DrLecter May 20 at 21:14

Your aim is to have a number $y' = y + rn$ that gives an uniform distribution over any valid key modulus $n'$, so that no keys can be ruled out. For that, you need $y'$ to be uniformly distributed modulo a larger number. How large is the question.

If you have uniform samples from $[0, 2^l-1]$, according to this (pdf, page 20 talking about key generation, but should apply here) they are uniform (enough) modulo $n < 2^k$ if $l = k + 64$. Hence, to have your $y'$ be uniform for keys up to $L$ bits you should draw $y'$ from $[0, 2^{L+64}-1]$.

Your approach gives even larger numbers ($2^{L+lg(n)} > 2^{L-lg(n)+64}$ with a realistic $n$), so that part's covered, but it may leak the minimum size of $n$, since if $r = 2^L$, no key with $n'<n$ could result in so high a number $y'$.

You should instead draw $r$ from $[0, 2^{L-lg(n)+64}-1]$, rounding the exponent so that $y'$ can reach $2^{L+64}-1$, then throw away those $r$ values that give you $y' > 2^{L+64}-1$.

(You could find a better upper bound for that random number generation, but generating uniform random numbers that aren't modulo a power of two is itself tricky. At worst you'll be throwing away half the $r$ values, so that should be easy enough.)

-

As @DrLecter commented, the property you refer is captured by "key privacy."

There are more tricky ways to achieve key privacy (against chosen-ciphertext attacks) based on the RSA encryption scheme. Let us assume $2^{k-1} < N < 2^{k}$.

### Repeating

Repeating to generate a ciphertext $y$ until the result is in the common domain, say, $[0,2^{k-1})$. See Bellare, Boldyreva, Desai, Pointcheval: Key-privacy in public-key encryption (ASIACRYPT 2001).

### Expanding

This is what you referred. Generating a ciphertext $y$ and expand it by $y + rn$ to the common domain, say $[0,2^{k+m})$. Setting $m = 160$ is enough (and 64 and 80 might not). See Desmedt: Securing traceability of ciphertexts: Towards a secure software escrow scheme (EUROCRYPT '95). We can show its key privacy when combined with RSA-OAEP. See Hayashi, Tanaka: Universally Anonymizable Public-Key Encryption (ASIACRYPT 2005) for a formal proof.

### Applying the RSA function twice

The obtained ciphertext is in $[0,2^k)$, where $k = |N|$. See Hayashi, Okamoto, Tanaka: An RSA Family of Trap-Door Permutations with a Common Domain and Its Applications (PKC 2004).

### Sampling twice

Generating two ciphertexts and applying "choose-and-shift" algorithm. The obtained ciphertext is distributed according to the uniform distribution over $[0,2^{k})$. See Hayashi, Tanaka: The Sampling Twice Technique for the RSA-Based Cryptosystems with Anonymity (PKC 2005).

-