Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / RSA-OAEP, Public-key cryptography

Original Publication (with major differences): IACR-PKC-2020

Date: received 29 Nov 2018, last revised 11 Feb 2020

Contact author: mz394 at georgetown edu

Available format(s): PDF | BibTeX Citation

Version: 20200211:201155 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]