TY - GEN
T1 - OAEP reconsidered
AU - Shoup, Victor
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2001
Y1 - 2001
N2 - The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt '94. It converts any trapdoor permutation scheme into a public-key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack. The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying trapdoor permutation scheme is one way. This paper shows conclusively that this justification is invalid. First, it observes that there appears to be a non-trivial gap in the OAEP security proof. Second, it proves that this gap cannot be filled, in the sense that there can be no standard "black box" security reduction for OAEP. This is done by proving that there exists an oracle relative to which the general OAEP scheme is insecure. The paper also presents a new scheme OAEP+, along with a complete proof of security in the random oracle model. OAEP+ is essentially just as efficient as OAEP, and even has a tighter security reduction. It should be stressed that these results do not imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure. They simply undermine the original justification for its security. In fact, it turns out- essentially by accident, rather than by design-that RSA-OAEP is secure in the random oracle model; however, this fact relies on special algebraic properties of the RSA function, and not on the security of the general OAEP scheme.
AB - The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt '94. It converts any trapdoor permutation scheme into a public-key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack. The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying trapdoor permutation scheme is one way. This paper shows conclusively that this justification is invalid. First, it observes that there appears to be a non-trivial gap in the OAEP security proof. Second, it proves that this gap cannot be filled, in the sense that there can be no standard "black box" security reduction for OAEP. This is done by proving that there exists an oracle relative to which the general OAEP scheme is insecure. The paper also presents a new scheme OAEP+, along with a complete proof of security in the random oracle model. OAEP+ is essentially just as efficient as OAEP, and even has a tighter security reduction. It should be stressed that these results do not imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure. They simply undermine the original justification for its security. In fact, it turns out- essentially by accident, rather than by design-that RSA-OAEP is secure in the random oracle model; however, this fact relies on special algebraic properties of the RSA function, and not on the security of the general OAEP scheme.
UR - http://www.scopus.com/inward/record.url?scp=84880904783&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880904783&partnerID=8YFLogxK
U2 - 10.1007/3-540-44647-8_15
DO - 10.1007/3-540-44647-8_15
M3 - Conference contribution
AN - SCOPUS:84880904783
SN - 3540424563
SN - 9783540424567
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 239
EP - 259
BT - Advances in Cryptology, CRYPTO 2001 - 21st Annual International Cryptology Conference, Proceedings
A2 - Kilian, Joe
PB - Springer Verlag
T2 - 21st Annual International Cryptology Conference, CRYPTO 2001
Y2 - 19 August 2001 through 23 August 2001
ER -