How to Simulate Random Oracles with Auxiliary Input

Yevgeniy Dodis, Aayush Jain, Huijia Lin, Ji Luo, Daniel Wichs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The random oracle model (ROM) allows us to opti-mistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh [CRYPTO '07] proposed the auxiliary-input random oracle model (AI-ROM), where a non-uniform attacker additionally gets a bounded amount of advice about the random oracle. Proving security in the AI-ROM is often much more difficult, but a series of works starting with Unruh provided useful technical tools to do so. Although these tools lead to good results in the information-theoretic setting, they are unsatisfactory in the computational setting, where the random oracle is used alongside other computational hardness assumptions. At the most basic level, we did not even know whether it is possible to efficiently simulate random oracle queries given auxiliary input, which has remained as an explicit open problem since the work of Unruh. In this work, we resolve the above open problem and show how to efficiently simulate auxiliary-input random oracles. Moreover, the simulation has low concrete overhead, leading to small losses in exact security. We use it to prove the security of a broad class of computational schemes in the AI-ROM, including the first non-interactive zero-knowledge (NIZK) scheme in the AI-ROM. As a tool of independent interest, we develop a new notion of ultra-secure pseudorandom functions with fast RAM evaluation, which can achieve 2λ security while having sublinear o(λ) evaluation time.

Original languageEnglish (US)
Title of host publicationProceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024
PublisherIEEE Computer Society
Pages1207-1230
Number of pages24
ISBN (Electronic)9798331516741
DOIs
StatePublished - 2024
Event65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024 - Chicago, United States
Duration: Oct 27 2024Oct 30 2024

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024
Country/TerritoryUnited States
CityChicago
Period10/27/2410/30/24

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'How to Simulate Random Oracles with Auxiliary Input'. Together they form a unique fingerprint.

Cite this