Paper 2013/424

Instantiating Random Oracles via UCEs

Mihir Bellare, 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.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2013
Keywords
Random oraclesdeterministic encryptionhardcore predicatesmessage-locked encryptionobfuscationgarbled circuitsrelated-key attackkey-dependent messagesproofs of storageOAEP
Contact author(s)
tvhoang @ engr ucsb edu
History
2015-11-13: last of 8 revisions
2013-07-02: received
See all versions
Short URL
https://ia.cr/2013/424
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/424,
      author = {Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi},
      title = {Instantiating Random Oracles via UCEs},
      howpublished = {Cryptology ePrint Archive, Paper 2013/424},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/424}},
      url = {https://eprint.iacr.org/2013/424}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.