Paper 2018/276

How to Record Quantum Queries, and Applications to Quantum Indifferentiability

Mark Zhandry


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
mzhandry @ princeton edu
2019-03-01: last of 3 revisions
2018-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mark Zhandry},
      title = {How to Record Quantum Queries, and Applications to Quantum Indifferentiability},
      howpublished = {Cryptology ePrint Archive, Paper 2018/276},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.