2020/10/22 by Kai-Min Chung, Serge Fehr, Chung, Kai-Min +5 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2010.11658
openalex publication_date 2020/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the so-called compressed oracle technique, introduced by Zhandry\nfor analyzing quantum algorithms in the quantum random oracle model (QROM). To\nstart off with, we offer a concise exposition of the technique, which easily\nextends to the parallel-query QROM, where in each query-round the considered\nalgorithm may make several queries to the QROM in parallel. This variant of the\nQROM allows for a more fine-grained query-complexity analysis.\n Our main technical contribution is a framework that simplifies the use of\n(the parallel-query generalization of) the compressed oracle technique for\nproving query complexity results. With our framework in place, whenever\napplicable, it is possible to prove quantum query complexity lower bounds by\nmeans of purely classical reasoning. More than that, for typical examples the\ncrucial classical observations that give rise to the classical bounds are\nsufficient to conclude the corresponding quantum bounds.\n We demonstrate this on a few examples, recovering known results (like the\noptimality of parallel Grover), but also obtaining new results (like the\noptimality of parallel BHT collision search). Our main target is the hardness\nof finding a q-chain with fewer than q parallel queries, i.e., a sequence\nx0, x1,\…, xq with xi = H(xi-1) for all 1 \≤ i \≤ q.\n The above problem of finding a hash chain is of fundamental importance in the\ncontext of proofs of sequential work. Indeed, as a concrete cryptographic\napplication of our techniques, we prove that the "Simple Proofs of Sequential\nWork" proposed by Cohen and Pietrzak remains secure against quantum attacks.\nSuch an analysis is not simply a matter of plugging in our new bound; the\nentire protocol needs to be analyzed in the light of a quantum attack. Thanks\nto our framework, this can now be done with purely classical reasoning.\n