How can I show, that RSA with OAEP is IND-CPA secure by using G,H one way function?

  • $\begingroup$ You might find the proof in the paper cseweb.ucsd.edu/~mihir/papers/oae.pdf (other useful refs are available on the internet, see References paragraph here: en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding) $\endgroup$
    – ddddavidee
    May 9, 2016 at 7:57
  • $\begingroup$ @ddddavidee I think the proof in the original paper was flawed. $\endgroup$ May 9, 2016 at 8:10
  • $\begingroup$ Really? Oh. My. I did not know. $\endgroup$
    – ddddavidee
    May 9, 2016 at 8:13
  • 3
    $\begingroup$ The proof in the original paper was indeed flawed, but it only applied to proving that OAEP is IND-CCA2, it still proved that OAEP is IND-CCA1 (which of course implies IND-CPA). $\endgroup$ May 9, 2016 at 17:16
  • 1
    $\begingroup$ @ddddavidee, would you mind giving a short summary of the idea of the proof (along with a link to the proof) as an answer so we can get this questio rid off our "unanswered questions" list? $\endgroup$
    – SEJPM
    May 9, 2016 at 19:04

1 Answer 1



Recall that RSA-OAEP is defined as follows (with $m$ being the message to encrypt, $G$ and $H$ being random oracles and $(e, N)$ being a standard RSA public key):


  • Select a random $k$-bit integer $r$.
  • Pad out $m$ with $0$s to length $l = |N| - k$.
  • Compute $X = G(r) \oplus m_{padded}$
  • Compute $Y = r \oplus H(X)$
  • Return $X || Y$


  • Compute $r = Y \oplus H(X)$
  • Compute $m_{padded} = X \oplus G(r)$
  • Strip off the $0$s from $m_{padded}$ to recover $m$


The IND-CPA game in this case is as follows:

  • The adversary selects two messages $m_0, m_1$ and submits them to the an encryption oracle.
  • The encryption oracle samples $b \in \{0, 1\}$ and computes $c = \text{RSA-OAEP}(m_b)$.
  • The adversary is free to perform more encryptions. To conclude, the adversary must guess $b$ corresponding to the message that was encrypted.

If the adversary can guess $b$ with non-negligible advantage the scheme is not IND-CPA.

Sketch of proof that RSA-OAEP is IND-CPA

The basic idea of the proof is that in order to recover $m_b$ from $c$ the adversary must be able to recover the entirety of $X$ and $Y$ from $c$ (recall that $c = \text{RSA-OAEP}(m_b) = \text{RSA}(X||Y)$). This is because to recover $m$ we must be able to compute $r = Y \oplus H(X)$. If we are missing even one bit of $X$ then $H(X)$ will give us a uniform random value (remember $H$ is a random oracle), and our $r$ value will be totally wrong (i.e. we learn nothing of the true value of $r$). The same is true of $Y$, if we fail to recover even one bit of $Y$ we will compute $r$ incorrectly, and as $G$ is also a random oracle $m_{padded} = X \oplus G(r)$ will again give us a uniform random value, revealing nothing about the actual value of $m$. Therefore adversary must be able to recover all of $X||Y$ to learn anything about $m$ which under the assumed hardness of the RSA Problem is not considered computationally feasible. Thus the adversary has no better chance than guessing $b$ and has negligible advantage, making the scheme IND-CPA.

  • 1
    $\begingroup$ Please note: textbook RSA by itself is deterministic (if you use it in a traditional sense as $m^e\bmod N$), thus it cannot be IND-CPA (also see theorem 11.4 of Katz/Lindell's Introduction to modern cryptography 2nd edition). However, OAEP does include randomness and this is the crucial part for IND-CPA here. $\endgroup$
    – SEJPM
    May 9, 2016 at 20:43
  • $\begingroup$ You are correct, answer has been edited. $\endgroup$ May 9, 2016 at 21:35
  • 1
    $\begingroup$ the adversary has negligible advantage, not non-negligible advantage $\endgroup$
    – jvdh
    Jul 13, 2020 at 8:09
  • $\begingroup$ Think this question is not specific for RSA, nor for the security of textbook RSA or the encryption algorithm at all. It's a question of protocol and network topology. In any case, there is a time, when you decide to consider a message as authentic. Essential help is having two communication lines, which in the public area have no intersection, so an assumed "man in the middle" will miss at least one part of required messages of key exchange. $\endgroup$ Jan 21, 2022 at 23:55

Your Answer

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

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