I am thinking of a variant of RSA. I know that RSA itself is not semantically secure as it is "deterministic". I have a "randomized" variant of RSA in mind.

Suppose that the public key is $<e,n>$. To encrypt a plaintext $p$, this variant first randomly choose a value $v$, and output the ciphertext as: $$E(p)=<v,(v+p)^e \text{ mod }n>$$ The ciphertext consists of 2 parts, the value of $v$ in clear, and the ciphertext of $(v+p) \text{ mod }n$ computed using the original RSA.

Is this variant of RSA semantically secure? How do I prove it?


No it's not.

As a reminer: Semantic security is equivalent to IND-CPA. Semantic security is less commonly used, because most of the time proofs are less intuitive and more difficult.

In the IND-CPA game, the attacker chooses two messages $m_0,m_1$ and sends them to the challenger. The challenger chooses a bit $b$, and sends $Enc(m_b)$ to the attacker. The attacker wins if he can guess $b$ correctly. And we consider the encryption scheme secure, if the advantage of the attacker compared to random guessing is negligible.

So, let's play the CPA game with this variant:

  • The attacker chooses $m_0$ and $m_1$ arbitrary (but not equal)
  • He gets back $Enc(m_b)$. In your scheme that would be some value $v$ and $(v+m)^e \mod n$.
  • Since he knows both $m_0$ and $m_1$, he can check both possibilities by calculating both $(m_0 + v)^e$ and $(m_1 + v)^e$. Comparing that with the challenge, he immediately knows $b$
  • The attacker wins.

If you want to have an IND-CPA RSA variant, there is RSA-OAEP. In the random oracle model and with the RSA assumption, this is proven to be IND-CCA2, which is much stronger than IND-CPA.


If you intercept the message <v,c> and instead transmit <v+x, c> it will decrypt to p-x. So this doesn't seem secure.

Edit: Just to clarify, I was a bit sloppy here. What I was going for is the fact that malleability precludes IND-CCA2. But the question was actually about semantic security and there are in fact semantically secure malleable schemes. (See Wikipedia)

So while the statement "doesn't seem secure" is technically correct for the most widespread definition of "secure" for PKE schemes I did not answer the question at all. Sorry.

  • $\begingroup$ "most widespread definition of "secure" for PKE schemes" I would not agree with that. IND-CPA has its value, especially since it allows (semi-)homomorphic encryption schemes. (the positive side of malleability). Also IND-CPA is a good abstraction for symmetric encryption with proper mode-of-operation (but, that's not PKE). And I don't think there are that many practical IND-CCA2 schemes besides the case of RSA-OAEP. For ElGamal, according to this question even CCA1 seems to be an open question. $\endgroup$ – tylo Oct 27 '16 at 10:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.