Welcome to the resource topic for 2018/276
Title:
How to Record Quantum Queries, and Applications to Quantum Indifferentiability
Authors: Mark Zhandry
Abstract:The quantum random oracle model (QROM) has become the standard model in which to prove the post-quantum security of random-oracle-based constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary’s queries, a crucial feature of many classical ROM proofs, including all proofs of indifferentiability for hash function domain extension. In this work, we give a new QROM proof technique that overcomes this ``recording barrier’'. Our central observation is that when viewing the adversary’s query and the oracle itself in the Fourier domain, an oracle query switches from writing to the adversary’s space to writing to the oracle itself. This allows a reduction to simulate the oracle by simply recording information about the adversary’s query in the Fourier domain. We then use this new technique to show the indifferentiability of the Merkle-Damgard domain extender for hash functions. We also give a proof of security for the Fujisaki-Okamoto transformation; previous proofs required modifying the scheme to include an additional hash term. Given the threat posed by quantum computers and the push toward quantum-resistant cryptosystems, our work represents an important tool for efficient post-quantum cryptosystems.
ePrint: https://eprint.iacr.org/2018/276
Talk: https://www.youtube.com/watch?v=m935yaOyKX0
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .