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.

  • $\begingroup$ Hint: what are the expected maximum and mean value of the ciphertext after a number of messages? $\endgroup$ – fgrieu Jan 9 '14 at 9:34
  • $\begingroup$ This is a direction but I'm talking about the cpa experiment. Adding it to the question. $\endgroup$ – Bush Jan 9 '14 at 9:37
  • $\begingroup$ Also, changed the adversary to be CPA, it is not matter though because in public key an eavesdropper is also a cpa. $\endgroup$ – Bush Jan 9 '14 at 9:43
  • 3
    $\begingroup$ You may also want to look at the paper Key-Privacy in Public-Key Encryption for positive results. $\hspace{.58 in}$ $\endgroup$ – user991 Jan 9 '14 at 10:10
  • 1
    $\begingroup$ @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. $\endgroup$ – fgrieu Jan 13 '14 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.