RSA is homomorphic wrt multiplication and therefore it is not IND-CCA2. But how to show it. What are the steps to win IND-CCA2 game?

How is the probability of winning calculated?

  • 2
    $\begingroup$ Anything unclear after pondering wikipedia's entry on IND-CCA2 at length? Also: "RSA is homomorphic" holds for textbook RSA, but not RSA encryption as practiced (e.g. RSA-OAEP). And textbook RSA is not even IND-CPA, thus considering it's IND-CCA2 security is a bit strange. The question might not be about RSA in particular. $\endgroup$ – fgrieu May 23 '20 at 10:10

yes, plain textbook RSA is only OW-CPA (not even IND-CPA).

You can construct an adversary $\mathcal{A}$ which wins in the IND-CCA2 game:

  1. $\mathcal{A}$ sends $m_0=0$ and $m_1=1$ as challenge ciphertexts to be encrypted

$\mathcal{A}$ receives the ciphertext $c_b = Enc(pk, m_b) = (m_b) ^ e \mod N$ for some uniform random $b \in \{0,1\}$.

  1. $\mathcal{A}$ uses the homomorphic property of RSA to obtain a ciphertext for $2\cdot m_b$:

$\mathcal{A}$ computes $c_b' = (2^e \cdot c_b) \mod N = (2 \cdot m_b) ^ e \mod N$

  1. $\mathcal{A}$ sends $c_b'$ to the decryption oracle. and receives the decryption which is either 0 (then $b$ was 0) or 2 (then $b$ was 1).

  2. $\mathcal{A}$ outputs $b$.

$\mathcal{A}$ can query the decryption oracle on the ciphertext $c_b'$ since this ciphertext wasn't received by $\mathcal{A}$ from the encryption oracle.

The decryption oracle doesn't do any integrity checks, so it will successfully decrypt the ciphertext.

If I didn't miss anything, the probability of $\mathcal{A}$ winning this game is 1.

You could also beak RSA IND-CPA security by testing which message was encrypted (by encrypting both messages yourself). This works because textbook-RSA encryption is deterministic. A scheme that isn't IND-CPA secure, can't be IND-CCA secure.

I hope I could help!


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.