# How can I show RSA OAEP IND-CPA secure

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

• 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) May 9, 2016 at 7:57
• @ddddavidee I think the proof in the original paper was flawed. May 9, 2016 at 8:10
• Really? Oh. My. I did not know. May 9, 2016 at 8:13
• 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). May 9, 2016 at 17:16
• @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? May 9, 2016 at 19:04

## 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.

• 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. May 9, 2016 at 20:43
• You are correct, answer has been edited. May 9, 2016 at 21:35