TY - GEN
T1 - How to Simulate Random Oracles with Auxiliary Input
AU - Dodis, Yevgeniy
AU - Jain, Aayush
AU - Lin, Huijia
AU - Luo, Ji
AU - Wichs, Daniel
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85213043858&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85213043858&partnerID=8YFLogxK
U2 - 10.1109/FOCS61266.2024.00080
DO - 10.1109/FOCS61266.2024.00080
M3 - Conference contribution
AN - SCOPUS:85213043858
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1207
EP - 1230
BT - Proceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024
PB - IEEE Computer Society
T2 - 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024
Y2 - 27 October 2024 through 30 October 2024
ER -