CryptoDB
How to Record Quantum Queries, and Applications to Quantum Indifferentiability
| Authors: | |
|---|---|
| Download: |
|
| 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. |
Video from CRYPTO 2019
BibTeX
@article{crypto-2019-29888,
title={How to Record Quantum Queries, and Applications to Quantum Indifferentiability},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11693},
pages={239-268},
doi={10.1007/978-3-030-26951-7_9},
author={Mark Zhandry},
year=2019
}