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.
翻译:我们重新审视了Zhandry为分析量子随机随机模型(QROM)中的量子算法而引入的所谓压缩或触角技术。 首先,我们提供一个简明的技术解析框架,该技术可以很容易地延伸至平行查询的QROM, 在每个查询回合中, 考虑的算法可以平行地向QROM提出数个问题。 这个QROM的变式可以进行更细微的查询兼容性分析。 我们的主要技术贡献是一个简化使用( 平行查询的) 用于证明查询复杂结果的压缩或触角技术( QROM ) 的框架。 在我们的链框架中, 只要使用纯经典推理的推理推理方法, 就可以证明数量的复杂性。 在几个例子中, 将已知的结果恢复到平行攻击的最优度( 类似同步的), 并获得新的结果( 如平行的 BHT 碰撞搜索最优性) 。 我们的主要目标, 与直径 直径的 直径 直径= 直径 直径 分析 。