Skip to main content

How to Record Quantum Queries, and Applications to Quantum Indifferentiability

Author(s): Zhandry, Mark

To refer to this page use:
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”. We do so by giving a new “compressed oracle” which allows for efficient on-the-fly simulation of random oracles, roughly analogous to the usual classical simulation. We then use this new technique to give the first proof of quantum indifferentiability for the Merkle-Damgård 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.
Publication Date: 2019
Citation: Zhandry, Mark. "How to Record Quantum Queries, and Applications to Quantum Indifferentiability." In Annual International Cryptology Conference (2019): pp. 239-268. doi:10.1007/978-3-030-26951-7_9
DOI: 10.1007/978-3-030-26951-7_9
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 239 - 268
Type of Material: Conference Article
Journal/Proceeding Title: Annual International Cryptology Conference
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.