Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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.

share|improve this question
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}$ – Ricky Demer 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.