# Can you show how that RSA does/doesn't provide anonymity?

Considering a CPA-secure version of RSA where the ciphertext is just a rundom element from $Z^*_N$. Does that meet the anonymity requirement in which an cpa adversary cannot distinguish between a message encrypted using Alice's public key and a message encrypted using Bob's public key?

EDIT:

My question is related to the experiment in which the adversary is given Alice's public key $pk_A$ and bob's public key $pk_B$ and choose a message $m$ from $Z^*_N$. Then the adversary given the ciphertext created by encryption using $pk_A$ or $pk_B$. The adversary task is to tell what public key has been used.

• Hint: what are the expected maximum and mean value of the ciphertext after a number of messages? – fgrieu Jan 9 '14 at 9:34
• This is a direction but I'm talking about the cpa experiment. Adding it to the question. – Bush Jan 9 '14 at 9:37
• Also, changed the adversary to be CPA, it is not matter though because in public key an eavesdropper is also a cpa. – Bush Jan 9 '14 at 9:43
• You may also want to look at the paper Key-Privacy in Public-Key Encryption for positive results. $\hspace{.58 in}$ – user991 Jan 9 '14 at 10:10
• @Bush: Neither (but now that you have added to the question that the adversary is bound to submit a single message per experiment, mean and maximum are moot). I suggest that you compute a rough approximation of the odds that $(m^e\mod N_A)<(m^e\mod N_B)$ for random $m$, as a function of $N_A$ and $N_B$, the public modulus of Alice and Bob; have a mild illumination to define a strategy for the attacker; and compute the advantage obtained by applying this strategy. – fgrieu Jan 13 '14 at 6:35