## Instantiating Random Oracles via UCEs

by Mihir Bellare, Viet Tung Hoang, and Sriram Keelveedhi

#### Oded's comments

This work was the last part of Mihir's talk at an MIT Fest that
celebrated Shafi and Silvio's achievements. The first part of
the talk was a very inspiring account of Mihir's experiences
as a student of Silvio at MIT, focusing on issues such as
Science versus Art, Theory versus Practice, and more.

For a couple of decades, the problem of provide a sound justification
to the Random Oracle Methodology has been puzzling the community.
While it is known that a generic justifiaction is not possible
(e.g., there exists (contrived) signature
and encryption schemes which are secure in the Random Oracle Model,
but for which ANY implementation of the random oracle results in
insecure schemes), this does not rule out the existence of
a class of valuable problems and/or schemes for which the said
methodology is sound. Still, coming up with such a class and conditions
on the implementation that guarantee a sound instantiation has eluded
the research community so far (although some results of this falvor
were known before). The condition (on implementation) defined in this
paper is quite complex, but the authors demonstrate its usefulness
by a host of applications.

#### The original abstract

This paper provides a (standard-model) notion of security for
(keyed) hash functions, called UCE, that we show enables instantiation of
random oracles (ROs) in a fairly broad and systematic way. Goals and
schemes we consider include deterministic PKE; message-locked encryption;
hardcore functions; point-function obfuscation; OAEP; encryption secure for
key-dependent messages; encryption secure under related-key attack; proofs
of storage; and adaptively-secure garbled circuits with short tokens. We
can take existing, natural and efficient ROM schemes and show that the
instantiated scheme resulting from replacing the RO with a UCE function is
secure in the standard model. In several cases this results in the first
standard-model schemes for these goals. The definition of UCE-security
itself is quite simple, asking that outputs of the function look random
given some 'leakage', even if the adversary knows the key, as long as the
leakage does not permit the adversary to compute the inputs.

A preliminary version of this paper appears in the
proceedings of CRYPTO 2013. a full version is available
HERE.

Back to
list of Oded's choices.