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.
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.