3
$\begingroup$

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

$\endgroup$
5
  • $\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 '16 at 7:57
  • $\begingroup$ @ddddavidee I think the proof in the original paper was flawed. $\endgroup$ – CodesInChaos May 9 '16 at 8:10
  • $\begingroup$ Really? Oh. My. I did not know. $\endgroup$ – ddddavidee May 9 '16 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$ – puzzlepalace May 9 '16 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 '16 at 19:04
4
$\begingroup$

RSA-OAEP

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):

$Encode$:

  • 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$

$Decode$

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

IND-CPA Game

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.

$\endgroup$
3
  • 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 '16 at 20:43
  • $\begingroup$ You are correct, answer has been edited. $\endgroup$ – puzzlepalace May 9 '16 at 21:35
  • 1
    $\begingroup$ the adversary has negligible advantage, not non-negligible advantage $\endgroup$ – jvdh Jul 13 '20 at 8:09

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.