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
    Commented Jan 9, 2014 at 9:34
  • $\begingroup$ This is a direction but I'm talking about the cpa experiment. Adding it to the question. $\endgroup$
    – Bush
    Commented Jan 9, 2014 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
    Commented Jan 9, 2014 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
    Commented Jan 9, 2014 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
    Commented Jan 13, 2014 at 6:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.