Towards RSA-OAEP without Random Oracles

19.11.2018, 16:00 – 17:00

2018/11/19 16:00-17:00

Speaker: Prof. Dr. Adam O’Neill | Location: Mornewegstraße 32 (S4|14), Room 5.3.01, Darmstadt

Organizer: Prof. Dr. Marc Fischlin


We give the first positive results about instantiability of the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and variants *under chosen-ciphertext attack*. 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. First, we show that 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. Ours are the first ``partial instantiation'' results for RSA-OAEP. We obtain them by exploiting (generalizations of) algebraic properties of RSA proven by Barthe, Pointcheval, and B\'aguelin (CCS 2012). Second, we show that both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called ``$t$-clear'' and ``$s$-clear'' RSA-OAEP. In particular, we are the first show positive results for $s$-clear RSA-OAEP, and our results for it yield the most efficient RSA-based IND-CCA2 secure scheme (under plausible assumptions) in the standard model to date. We obtain them by leveraging a new hierarchy of 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. Notably, we explain how our full instantiation results avoid impossibility results of Shoup (J.~Cryptology 2002), Kiltz and Pietrzak (EUROCRYPT 2009), and Bitansky et al. (STOC 2014).

Short bio

Adam O‘Neill is an Assistant Professor at the Computer Science Department at Georgetown University, Washington DC. For Fall 2018 he is an Mercator Fellow at Technische Universität Darmstadt, in the Cryptoplexity Group headed by Marc Fischlin. Starting Spring 2019 he will be an Assistant Professor at the College of Information and Computer Sciences, University of Massachusetts Amherst.