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 asks that outputs of the function look random given some ``leakage,'' even if the adversary knows the key, as long as the leakage is appropriately restricted.

Category / Keywords: Random oracles, deterministic encryption, hardcore predicates, message-locked encryption, obfuscation, garbled circuits, related-key attack, key-dependent messages, proofs of storage, OAEP

Original Publication (with major differences): IACR-CRYPTO-2013

Date: received 28 Jun 2013, last revised 3 Aug 2015

Contact author: vth005 at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20150804:010049 (All versions of this report)

Short URL: ia.cr/2013/424

Discussion forum: Show discussion | Start new discussion