Adam O'Neill
Boston University

Security Proofs for RSA-OAEP in the Standard Model

RSA-OAEP is a popular ``provably secure'' way to encrypt
with the RSA trapdoor permutation in practice, proposed by Bellare and
Rogaway (Eurocrypt 1994).   Essentially, the scheme first
pre-processes an input plaintext --- namely, by applying two hash
functions in an invertible way to the plaintext concatenated with some
number of random coins --- before applying RSA.   An important caveat
is that the security analysis of the scheme was done in the ``random
oracle (RO) model,'' which, roughly speaking, heuristically models
hash functions as truly random functions available via oracles to all
parties.  Unfortunately, it is known that, in general, a scheme that
is secure in the RO model may necessarily be insecure in the
``standard model'' where hash functions are required to be efficiently
computable (Canetti et al., J. ACM 2004).  Here we endeavor to give a
supplemental analysis of RSA-OAEP in the standard model.

Our main result (with Eike Kiltz and Adam Smith, at Crypto 2010) is a
proof that RSA-OAEP achieves semantic security (i.e., ``passive
security'') in the standard model under reasonable assumptions. We
begin by outlining a general approach to proving semantic security of
RSA-OAEP in the standard model.  We then explain how to implement it
based on the recently proposed notion of ``lossy'' trapdoor functions
by Peikert and Waters (STOC 2008) combined with (some novel extensions
to) a variant of the Leftover Hash Lemma due to Dodis and Smith (STOC
2005).  We deduce that RSA-OAEP is semantically secure if RSA is lossy
and the first hash function used in the pre-processing stage is
$t$-wise independent for appropriate $t$. (No assumption is made on
the second hash function for this result; in particular, neither hash
function is modeled as a random oracle.)  Finally, we show that RSA is
lossy under the ``$\Phi$-Hiding'' Assumption of Cachin, Micali, and
Stadler (Eurocrypt 1999), originally proposed in the context of
private information retrieval.

I will try to save time towards the end of the talk to discuss
on-going efforts to extend this result in various ways, namely to use
hash function families with shorter keys and to address the more
challenging case of chosen-ciphertext attacks (i.e., ``active

Joint work with:
Eike Kiltz and Adam Smith