Source-linked AI summary
On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work
Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, Tai-Ning Liao
TL;DR
Quantum queries in superposition make ordinary random-oracle security arguments difficult to apply, and compressed-oracle proofs can be cumbersome. The paper extends that technique to parallel queries and develops a framework for classical reasoning about quantum query bounds; it applies the approach to q-chain hardness and the quantum security of Simple PoSW.
Problem
In the QROM, an adversary queries in superposition, so security reductions cannot inspect its queries as they can in the ordinary random-oracle model.
Source: §1 · p. 2Method
The paper extends the compressed-oracle technique to parallel queries and develops a framework that, when applicable, proves quantum query lower bounds through classical reasoning.
Source: §1 · p. 2Results
Finding a q-chain with fewer than q queries has success probability at most O(k^3q^3/2^m), and the paper proves quantum security for Cohen and Pietrzak’s Simple PoSW.
Source: §1 · p. 3Takeaways & Limitations
The framework supports classical proofs of quantum query bounds and of the Simple PoSW’s post-quantum security.
Source: §1 · pp. 2–3The extension to general ℓ-locality is available only for strong recognizability.
Source: §5.2.3 · p. 20
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends the compressed-oracle technique to parallel quantum queries and presents a framework that, when applicable, turns quantum query lower-bound proofs into classical reasoning. It applies this approach to parallel search bounds, q-chain hardness, and the quantum security of Simple Proofs of Sequential Work.
1 Introduction
- The paper gives a rigorous compressed-oracle exposition using Fourier transforms over arbitrary finite Abelian groups, addressing a technique whose proofs can be cumbersome and quantum-information-intensive.The technique considers a quantum purification of the random function and analyzes the oracle’s internal state in the Fourier domain.Source: §1 · p. 2
- The parallel-query QROM distinguishes q query rounds from k parallel queries per round, enabling finer analysis of how well tasks can be parallelized.Queries within a round are non-adaptive, unlike sequential queries that may depend on previously learned hash values.Source: §1 · p. 2
- When applicable, the framework reduces quantum query lower-bound proofs to classical reasoning, often by extracting a classical property from the classical bound’s proof.The framework abstracts away the quantum aspects through meta-theorems.Source: §1 · p. 2
- The examples recover optimal parallel Grover search and establish optimality for parallel BHT collision search, a result the authors say they had not seen previously.The passage contrasts the bounds with coarse-grained query bounds and notes that the cited element-distinctness bound does not apply to hash functions with many collisions.Source: §1 · p. 2
- Finding a q-chain with fewer than q queries has success probability at most O(k^3q^3/2^m) in the quantum setting.The proof reuses an observation from the classical lower-bound argument within the framework.Source: §1 · p. 3
- The framework proves post-quantum security of Cohen and Pietrzak’s Simple PoSW, but requires analyzing the entire protocol rather than merely applying the chain bound.The resulting security proof uses purely classical reasoning.Source: §1 · p. 3
2 Warm-up: Proving Classical Query Complexity Lower Bounds
The warm-up shows how classical query-complexity arguments can be organized around partial oracle databases and then reused in the quantum setting. It applies this approach to preimage, chain, and collision search in the parallel-query model.
2 Warm-up: Proving Classical Query Complexity Lower Bounds
- The warm-up uses classical lower-bound proofs to show how their key observations can be reused in the framework for quantum query bounds.The authors note that some classical arguments are more elaborate than necessary to make their structure align with the framework.Source: §2 · p. 3, §2.3 · p. 4
2.1 The Lazy-Sampling Technique
- Lazy sampling answers new queries with random values stored in a partial database, while repeated queries return the stored value without changing the observable oracle behavior.The database starts as the constant-⊥ function and is updated as queries arrive.Source: §2.1 · p. 4
2.2 Efficient Representation
- The database can be represented as a list of defined input-output pairs, whose size stays bounded for bounded queries and whose updates are efficient.The encoding stores pairs for inputs x with D(x) ≠ ⊥.Source: §2.2 · p. 4
2.3 Proving Classical Lower Bounds
- The parallel-query preimage analysis confirms that running k parallel executions of Grover is optimal.The argument extends the preimage reasoning to k queries made in each interaction round.Source: §2.3 · p. 5
- For a relation y ◁ x, classical success finding a (q+1)-chain within q k-parallel queries is O(k^2q^2T/|Y|).Here T bounds the number of y values related to a given x.Source: §2.3 · pp. 5–6
- The framework lifts the chain argument to a quantum bound, with T=1 for equality or prefix relations and T=m−n for continuous substrings.The quantum analysis uses the same local properties as the classical reasoning.Source: §2.3 · p. 6
- A new collision can arise when parallel query outputs match one another or match an output already stored in the database.The classical analysis tracks both the pairwise matches among new outputs and matches with prior database values.Source: §2.3 · pp. 6–7
- For quantum collision search, the framework handles the 2-local pairwise-match condition by deriving 1-local properties before bounding success.The section reports a corresponding quantum collision bound for q k-parallel queries.Source: §2.3 · p. 7
3 Notation
This section establishes the operator, basis, and function-representation conventions used in the paper. It also specifies how databases and their quantum representations are written.
3.1 Operators and Their Norms
- States are vectors or density operators, and a state is supported by a subspace when its support lies there; operators on a subspace extend by acting as zero on its orthogonal complement.The section also sets the operator-norm convention and notes its upper bound by the Frobenius norm.Source: §3.1 · pp. 7–8
3.2 The Computational and the Fourier Basis
- The computational basis of C[Y] is labeled by elements of the finite Abelian group Y, while the Fourier basis is indexed by its dual group.The paper treats Y and its dual as distinct sets, even when they are isomorphic.Source: §3.2 · p. 8
3.3 Functions and Their (Quantum) Representations
- A function H is represented by the tensor product of basis states |H(x)⟩ indexed by inputs x; databases similarly use entries from Y together with ⊥.The notation also defines database updates that assign a tuple of values at selected inputs and leave other entries unchanged.Source: §3.3 · pp. 8–9
4 Zhandry’s Compressed Oracle - Refurbished
The section presents a compressed-oracle construction, relates it to the standard random oracle, works out its query transition matrix, and extends it to parallel queries. The construction represents the oracle through a purified function state analyzed in the Fourier basis.
4 Zhandry’s Compressed Oracle - Refurbished
- The section gives a concise, self-contained, mathematically rigorous introduction to the compressed-oracle technique.It adopts an abstract Fourier-transform presentation for arbitrary finite Abelian groups.Source: §4 · p. 9
4.1 The Compressed Oracle
- After q queries, the compressed oracle is supported on databases with at most q nonempty entries.Compression represents zero Fourier values by ⊥.Source: §4.1 · p. 9
4.2 Linking the Compressed and the Original Oracle
- Corollary 4.2 compares the probability of a relation holding for an algorithm's output with the standard random oracle and with a measured compressed oracle.It defines the two probabilities using the same output relation and inputs.Source: §4.2 · p. 10
4.3 Working Out the Transition Matrix
- For a nonzero Fourier query, the compressed-oracle unitary has the computational-basis matrix shown in Figure 1; a zero Fourier query acts as identity.The matrix describes the oracle's evolution under a query.Source: §4.3 · p. 11, Figure 1 · p. 12
4.4 The Parallel-Query (Compressed) Oracle
- A k-parallel query applies k oracle calls in parallel, and the compressed-oracle update is the product of the corresponding commuting single-query updates.Each update acts on its input's database register; the updates commute even when inputs coincide.Source: §4.4 · p. 13
5 A Framework for Proving Quantum Query Lower Bounds
This section develops a framework for proving quantum query lower bounds by analyzing transitions between database properties and bounding their quantum transition capacity using local recognizability and classical reasoning. It applies the framework to chain and collision finding and extends it to input-restricted transitions under local-property conditions.
5 A Framework for Proving Quantum Query Lower Bounds
- The framework lifts classical-style reasoning to the quantum random oracle model by reducing query lower bounds to bounds on quantum transition capacities.The next section’s techniques bound these capacities using classical reasoning, allowing quantum query lower bounds to follow from classical arguments.Source: §5 · p. 13, §5.1 · p. 16
5.1 Setting Up the Framework
- Bounding each transition capacity in a sequence of database properties bounds a quantum algorithm’s success probability; a variant handles algorithms that output only x when the relation depends on H(x).The direct-output theorem assumes the algorithm outputs both x and y; the variant avoids that assumption but requires an additional transition capacity to be analyzed.Source: §5.1 · p. 15
5.2 Bounding Quantum Transition Capacities Using Classical Reasoning Only
- Local properties, whose truth depends on oracle values at one or a few points, let analyses recognize database transitions and exploit the compressed oracle’s behavior at individual points.The section introduces strong and weak recognizability as two ways to use local properties to bound transition capacities.Source: §5.2 · p. 16
5.2.1 Reasoning via Strong Recognizability
- Strong recognizability by 1-local properties yields a transition-capacity bound, and the section applies this approach to finding a 0-preimage.The example identifies 0-preimage search with a uniformly strongly recognized property; the supplied passages do not provide the bound’s formula.Source: §5.2.1 · p. 17
5.2.2 Reasoning via Weak Recognizability
- Weak recognizability is a broader alternative to strong recognizability, but it results in a slightly worse bound.The section defines uniform and non-uniform versions of weak recognizability using local properties.Source: §5.2.2 · p. 18
- Theorem 5.25 bounds the probability that any k-parallel q-query oracle algorithm outputs x0,...,xq+1 with H(xi) ◁ xi+1 for every i=0,...,q, where T is the maximum fan-in and M is the range size.Source: §5.2.2 · p. 19
5.2.3 General ℓ-Locality and Collision Finding
- For properties with locality ℓ greater than 1, the framework removes the ℓ=1 limitation, but its more intricate bound is available only under strong recognizability.Source: §5.2.3 · p. 20
5.3 Some Rules for the Quantum Transition Capacity
- Quantum transition capacity is symmetric and admits intersection, restriction, and parallel-conditioning rules that let bounds be split across properties or query-coordinate sets.The rules support decomposing more complex transitions into cases that can be analyzed individually.Source: §5.3 · pp. 22–24
- The definition requires k-non-uniform weak recognizability by ℓ-local properties for every disjoint-entry tuple in X^k and every database D.The properties' supports lie among the tuple entries.Source: §5.3 · p. 24
- Theorem 5.36 treats input-restricted transitions recognizable by 1-local properties supported on a single tuple entry or empty set.Its maximization ranges over tuples in X^k.Source: §5.3 · p. 24
6 Post-Quantum Proof of Sequential Works
This section analyzes post-quantum security for Cohen and Pietrzak’s Simple PoSW after Fiat–Shamir, using the paper’s framework and classical reasoning. The analysis extracts an answerable subtree from the prover’s database, bounds its leaves, and applies Theorem 5.36 to database-transition arguments, including a labeling-support property and transitions restricted to LbQ inputs.
6 Post-Quantum Proof of Sequential Works
- For post-quantum security, the proof analyzes the non-interactive Simple PoSW after Fiat–Shamir, using the framework to make the argument purely classical.The framework’s transition analysis considers moving from a database without success, collisions, or an s-chain to one with success, a collision, or an (s+1)-chain.Source: §6 · p. 24, §6.2 · pp. 27–28
6.1 Simple Proof of Sequential Works
- The protocol asks the prover to compute the DAG’s root label and open authentication paths for challenge leaves, which the verifier checks for labeling consistency.The non-interactive version uses the random oracle for both labels and the challenge.Source: §6.1 · p. 26
- With no collisions, ExtractD produces a consistently labeled subtree rooted at the claimed label, containing every openable leaf; leaves outside it have no valid labeling of their ancestors.This extraction formalizes which challenge leaves can be answered from the database.Source: §6.1 · p. 27
- A database D with no (q + 1)-chain has the property that any subtree T admitting a consistent labeling with respect to D contains at most (q + 2)/2 leaves.Source: §6.1 · p. 27
6.2 Post-Quantum Security of Simple PoSW
- Theorem 6.8 bounds a quantum prover’s acceptance probability for Simple PoSW when w ≥ tn and the prover makes q queries in k-parallel rounds.The supplied passage omits the bound’s formula, so its value cannot be reported here.Source: §6.2 · p. 27
- The proof concludes a claimed bound by applying Theorem 5.36 after establishing the relevant database-transition argument.The preceding argument considers databases whose longest hash chain has length at most q and uses a consistent labeling.Source: §6.2 · p. 29
- Labeling support depends on where a database is defined, so LSupp(D) is contained in LSupp(Dx,0) for any x in X^k.The inclusion holds because LSupp does not depend on the function values beyond their being non-⊥.Source: §6.2 · p. 29
- For transitions with input restricted to LbQ, the authors define 1-local properties and show they weakly recognize the considered transition; the claimed bound follows by applying Theorem 5.36.Source: §6.2 · pp. 29–30
A Efficient Simulation of the Compressed Oracle
The compressed oracle’s evolution and useful database checks can be efficiently simulated using a classical list encoding. Switching between encodings lets a quantum circuit implement both operations.
A Efficient Simulation of the Compressed Oracle
- The classical list encoding stores defined (x, D(x)) pairs in sorted order and pads the list with ⊥ entries.For lists of bounded size, the update function inserts a new pair or replaces an existing value; it is identity in the specified zero-value case.Source: A Efficient Simulation of the… · p. 31
- For databases with at most Q defined entries, the modified update function handles overflow by acting as identity and is an efficiently computable permutation.This permits its corresponding unitary to be implemented by a polynomial-sized quantum circuit.Source: A Efficient Simulation of the… · pp. 31–32
- The compressed-oracle evolution can be efficiently computed while fewer than Q queries have been made.The described encoding assumptions include Y = {0,1}^m and an efficiently computable total order on X.Source: A Efficient Simulation of the… · pp. 31–32
- The two database encodings can be switched efficiently, so a suitable encoding supports both compressed-oracle evolution and computation of classical database functions.Examples of extractable information include whether a specified input is in the database and whether the database contains a 0-preimage.Source: A Efficient Simulation of the… · p. 32
B PoSW Definition
A non-interactive PoSW lets a prover present an efficiently verifiable proof of N sequential computation steps. The paper analyzes quantum attackers’ probability of generating a valid proof with fewer than N queries.
B PoSW Definition
- A PoSW proof is intended to attest to N sequential computation steps, while resisting an adversary with parallel computation that uses much less than N steps.The scheme is considered in the random oracle model and after applying Fiat–Shamir.Source: B PoSW Definition · p. 32
- The verifier sends a random statement χ; the prover computes proof φ and state φP, then receives γ = H(χ, φ) and returns (φ, τ).The verifier accepts or rejects by evaluating verify(χ, N, φ, γ, τ).Source: B PoSW Definition · p. 33
- The analysis bounds the probability that a k-parallel q-query quantum oracle algorithm with q < N generates a valid proof.The paper does not present formal PoSW security properties here, instead proving concrete upper bounds on this probability.Source: B PoSW Definition · p. 33
C The Extraction Algorithm
The extraction algorithm builds a subtree from a labeling’s support by processing supported non-leaf vertices, then performs a consistency check on supported leaves.
C The Extraction Algorithm
- The algorithm initializes a labeling with ⊥ away from the root, marks every vertex unmarked, and defines the support as vertices whose labels are not ⊥.Its output is a subtree T ⊆ Vn.Source: C The Extraction Algorithm · p. 33
- It repeatedly marks an unmarked supported non-leaf vertex and assigns a label to its right child when the stated x,y condition holds.After this labeling-extraction loop, it sets T to the support and checks consistency for each leaf in T.Source: C The Extraction Algorithm · p. 33
- The construction takes X to be finite by choosing B large enough for the scheme and larger than any query made by a fixed attacker.The cited passage contrasts this with the original paper’s choice X = {0,1}*.Source: C The Extraction Algorithm · p. 33