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.|
|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|
|Pages:||239 - 268|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Annual International Cryptology Conference|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.