TY - JOUR

T1 - Instantiability of RSA-OAEP Under Chosen-Plaintext Attack

AU - Kiltz, Eike

AU - O’Neill, Adam

AU - Smith, Adam

N1 - Funding Information:
Part of this work was done, while E.K. was at CWI, Amsterdam. E.K. is funded by ERC Project ERCC (FP7/615074) and the German Federal Ministry for Education and Research. Part of this work was done while A.O. was at Georgia Institute of Technology, supported in part by NSF award #0545659 and NSF Cyber Trust award #0831184. A.S. was supported in part by NSF awards #0747294, 0729171.
Funding Information:
Eike Kiltz was partially supported by DFG grant KI 795/4-1 and ERC Project ERCC (FP7/615074). Adam Smith was funded by US National Science Foundation award CCF-0747294.
Publisher Copyright:
© 2016, International Association for Cryptologic Research.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash (i.e., round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in the standard model based on simple, non-interactive, and non-interdependent assumptions on RSA and the hash functions. To prove this, we first give a result on a more general notion called “padding-based” encryption, saying that such a scheme is IND-CPA if (1) its underlying padding transform satisfies a “fooling" condition against small-range distinguishers on a class of high-entropy input distributions, and (2) its trapdoor permutation is sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satisfies condition (1) if its hash function is t-wise independent for t roughly proportional to the allowed message length. We clarify that this result requires the hash function to be keyed, and for its key to be included in the public key of RSA-OAEP. We also show that RSA satisfies condition (2) under the Φ -Hiding Assumption of Cachin et al. (Eurocrypt 1999). This is the first positive result about the instantiability of RSA-OAEP. In particular, it increases confidence that chosen-plaintext attacks are unlikely to be found against the scheme. In contrast, RSA-OAEP’s predecessor in PKCS #1 v1.5 was shown to be vulnerable to such attacks by Coron et al. (Eurocrypt 2000).

AB - We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash (i.e., round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in the standard model based on simple, non-interactive, and non-interdependent assumptions on RSA and the hash functions. To prove this, we first give a result on a more general notion called “padding-based” encryption, saying that such a scheme is IND-CPA if (1) its underlying padding transform satisfies a “fooling" condition against small-range distinguishers on a class of high-entropy input distributions, and (2) its trapdoor permutation is sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satisfies condition (1) if its hash function is t-wise independent for t roughly proportional to the allowed message length. We clarify that this result requires the hash function to be keyed, and for its key to be included in the public key of RSA-OAEP. We also show that RSA satisfies condition (2) under the Φ -Hiding Assumption of Cachin et al. (Eurocrypt 1999). This is the first positive result about the instantiability of RSA-OAEP. In particular, it increases confidence that chosen-plaintext attacks are unlikely to be found against the scheme. In contrast, RSA-OAEP’s predecessor in PKCS #1 v1.5 was shown to be vulnerable to such attacks by Coron et al. (Eurocrypt 2000).

UR - http://www.scopus.com/inward/record.url?scp=84988418360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988418360&partnerID=8YFLogxK

U2 - 10.1007/s00145-016-9238-4

DO - 10.1007/s00145-016-9238-4

M3 - Article

AN - SCOPUS:84988418360

SN - 0933-2790

VL - 30

SP - 889

EP - 919

JO - Journal of Cryptology

JF - Journal of Cryptology

IS - 3

ER -