Cryptology ePrint Archive: Report 2013/424
Instantiating Random Oracles via UCEs
Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi
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.
Category / Keywords: Random oracles, deterministic encryption, hardcore predicates, message-locked encryption, obfuscation, garbled circuits, related-key attack, key-dependent messages, proofs of storage, OAEP
Publication Info: A preliminary version of this paper appears in the proceedings of CRYPTO 2013. This is the full version.
Date: received 28 Jun 2013, last revised 31 Jul 2013
Contact author: tvhoang at ucdavis edu
Available format(s): PDF | BibTeX Citation
Version: 20130801:043135 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]