How can I show RSA OAEP IND-CPA secure

Question

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

Answer 1

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.