Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
Hint: what are the expected maximum and mean value of the ciphertext after a number of messages? –  fgrieu Jan 9 at 9:34
    
This is a direction but I'm talking about the cpa experiment. Adding it to the question. –  Bush Jan 9 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 at 9:43
3  
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 at 10:10
1  
@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 at 6:35
show 4 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.