You are looking at a specific version 20200211:201155 of this paper. See the latest version.

Paper 2018/1170

Toward RSA-OAEP without Random Oracles

Nairen Cao and Adam O'Neill and Mohammad Zaheri

Abstract

We show new partial and full instantiation results under chosen-ciphertext security for the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and two variants. Prior work on such instantiations either showed negative results or settled for ``passive'' security notions like IND-CPA. More precisely, recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round functions are modeled as random oracles (ROs), with RSA. Our main results are: \begin{itemize} \item Either of the two oracles (while still modeling the other as a RO) can be instantiated in RSA-OAEP under IND-CCA2 using mild standard-model assumptions on the round functions and generalizations of algebraic properties of RSA shown by Barthe, Pointcheval, and Báguelin (CCS 2012). The algebraic properties are only shown to hold at practical parameters for small encryption exponent ($e=3$), but we argue they have value for larger $e$ as well. \item Both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called ``$t$-clear'' and ``$s$-clear'' RSA-OAEP. For this we use extractability-style assumptions in the sense of Canetti and Dakdouk (TCC 2010) on the round functions, as well as novel yet plausible ``XOR-type'' assumptions on RSA. While admittedly strong, such assumptions may nevertheless be necessary at this point to make positive progress. \end{itemize} In particular, our full instantiations evade impossibility results of Shoup (J.~Cryptology 2002), Kiltz and Pietrzak (EUROCRYPT 2009), and Bitansky et al. (STOC 2014). Moreover, our results for $s$-clear RSA-OAEP yield the most efficient RSA-based encryption scheme proven IND-CCA2 in the standard model (using bold assumptions on cryptographic hashing) to date.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2020
Keywords
RSA-OAEPPublic-key cryptography
Contact author(s)
mz394 @ georgetown edu
History
2020-02-11: last of 3 revisions
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1170
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.