semantic security of RSA variant

Question

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?

Answer 1

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.

Answer 2

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.