How to Record Quantum Queries, and Applications to Quantum Indifferentiability
How to Record Quantum Queries, and Applications to Quantum Indifferentiability
复制标题
DOI：
10.1007/978-3-030-26951-7_9
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Mark Zhandry
中科院分区：
文献类型：
--
作者：
Mark Zhandry
量子随机预言机模型（QROM）已经成为证明基于随机预言机构造的后量子安全性的标准模型。不幸的是，没有一个已知的证明技术允许减少记录有关对手的查询，许多经典的ROM证明，包括所有证明的不可微性散列函数域extension.In这项工作中，一个至关重要的功能，我们给出了一个新的QROM证明技术，克服了这个“记录障碍”。我们这样做，通过给一个新的“压缩的神谕”，它允许有效的随机神谕的飞行模拟，大致类似于通常的经典模拟。然后，我们使用这种新的技术，给出量子不可微性的第一个证明的Merkle-Damgård域扩展的哈希函数。我们还给出了一个证明的安全性的Fujisaki-Okamoto变换，以前的证明需要修改该计划，包括一个额外的哈希项。考虑到量子计算机带来的威胁和对量子抵抗密码系统的推动，我们的工作代表了有效的后量子密码系统的重要工具。
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.