On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work
On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work
复制标题
关于压缩预言机技术和顺序工作证明的后量子安全性
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Tai
中科院分区：
文献类型：
--
作者：
Kai;S. Fehr;Yu;Tai
我们回顾了所谓的压缩oracle技术，由Zhandry介绍，用于分析量子随机oracle模型（QROM）中的量子算法。首先，我们简要介绍了该技术，它很容易扩展到并行查询QROM，在每个查询轮中，所考虑的算法可以并行地对QROM进行几个查询。QROM的这种变体允许进行更细粒度的查询复杂性分析。
We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM). To start off with, we offer a concise exposition of the technique, which easily extends to the parallel-query QROM, where in each query-round the considered algorithm may make several queries to the QROM in parallel. This variant of the QROM allows for a more fine-grained query-complexity analysis.
Our main technical contribution is a framework that simplifies the use of (the parallel-query generalization of) the compressed oracle technique for proving query complexity results. With our framework in place, whenever applicable, it is possible to prove quantum query complexity lower bounds by means of purely classical reasoning. More than that, for typical examples the crucial classical observations that give rise to the classical bounds are sufficient to conclude the corresponding quantum bounds.
We demonstrate this on a few examples, recovering known results (like the optimality of parallel Grover), but also obtaining new results (like the optimality of parallel BHT collision search). Our main target is the hardness of finding a $q$-chain with fewer than $q$ parallel queries, i.e., a sequence $x_0, x_1,ldots, x_q$ with $x_i = H(x_{i-1})$ for all $1 leq i leq q$.
The above problem of finding a hash chain is of fundamental importance in the context of proofs of sequential work. Indeed, as a concrete cryptographic application of our techniques, we prove that the "Simple Proofs of Sequential Work" proposed by Cohen and Pietrzak remains secure against quantum attacks. Such an analysis is not simply a matter of plugging in our new bound; the entire protocol needs to be analyzed in the light of a quantum attack. Thanks to our framework, this can now be done with purely classical reasoning.
关于后量子世界中顺序工作证明的安全性
DOI：
10.4230/lipics.itc.2021.22
发表时间：
2021
期刊：
2nd Conference on Information-Theoretic Cryptography (ITC 2021
影响因子：
--
作者：
Blocki, J;Lee, S;Zhou, S.
通讯作者：
Zhou, S.
DOI：
10.1007/978-3-030-26951-7_9
发表时间：
2019-08
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Mark Zhandry
通讯作者：
Mark Zhandry