Verifiable Quantum Advantage without Structure

1 Introduction

• Existing quantum speedup examples rely on significant structure, while classical hardness for known non-oracular NP examples is conjectural and entails assumptions stronger than P ≠ NP.Non-black-box methods can undermine hardness inferred from oracle problems; known examples are not believed to be NP-complete and their hardness can yield public-key encryption.Source: §1 · p. 3

1.1 Our Results

• A random oracle gives a non-interactive, publicly verifiable proof of quantumness secure against computationally unbounded uniform classical provers making polynomially many queries, and yields an NP search problem in QPT but not PPT.Against non-uniform adversaries, the proof uses two messages; non-interactivity is unavailable because an oracle-dependent proof could be hardcoded.Source: §1.1 · p. 4
• A random-oracle compressing function is classically collision resistant against polynomial-query, computationally unbounded adversaries but not quantumly one-way; analogous separations hold for signatures and CPA-secure public-key encryption, assuming a classically secure scheme.Earlier analogous constructions required LWE for signatures or highly structured oracles for CPA-secure encryption.Source: §1.1 · p. 5
• Assuming Conjecture 1.1, the paper obtains certifiable-randomness protocols for uniform and non-uniform devices, and replacing the random oracle with a hash such as SHA2 gives candidate Minicrypt examples.The protocols use one message for a uniform device and two for a non-uniform device; adding a verifier message makes them public coin and publicly verifiable. The hash-based security is plausible, not unconditional.Source: §1.1 · pp. 5–6

1.2 Discussion

• The paper’s NP-search focus enables publicly checkable solutions and, in its construction, oblivious problem sampling; this contrasts with sampling tasks lacking verifiable outputs and private-coin protocols.For uniform adversaries, the verifier’s message can be omitted entirely.Source: §1.2 · p. 6

1.3 Overview

• Restricting a random function’s coordinatewise outputs to codewords yields a function that is classically one-way and for which a quantum algorithm can sample preimages.The stated classical hardness includes the difficulty of finding a codeword mapped to 0^n; the quantum sampler works for any output y.Source: §1.3 · p. 7
• The quantum preimage finder constructs a state over codeword preimages by reversing reversible transformations, using linear-code Fourier transforms and the convolution theorem.The overview imposes that the alphabet is a vector space over Fq and the code is linear; measuring the constructed state yields a random preimage.Source: §1.3 · pp. 8–9
• The quantum inversion algorithm decodes a noisy codeword using folded Reed–Solomon list decoding, then exploits coding structure and oracle randomness to overcome negligible decoding failures.The decoded error model has symbols that are zero with probability 1/2 and otherwise random; the decoding map can fail to be unitary without the additional argument.Source: §1.3 · pp. 9–10
• Under Conjecture 1.1, efficiently generated pre-images must be random rather than deterministic, enabling a verifier to certify polynomial min-entropy and extract uniform bits.The verifier checks that a submitted pre-image maps to the chosen output; the argument uses one-wayness even against sub-exponential-query algorithms to obtain polynomial min-entropy.Source: §1.3 · p. 10
• For non-uniform attackers, salting gives two-message public-coin proofs of quantumness, while careful arguments yield proofs of randomness with a small verifier message in the classical-advice setting.Extending randomness proofs to non-uniform adversaries with quantum advice remains open.Source: §1.3 · p. 10
• Worst-case correctness is obtained by setting O = O′ ⊕ P, with a solution-supplied k-wise independent function P, and amplifying classical hardness across instances to handle all P.The quantum algorithm can solve each individual instance with high probability.Source: §1.3 · p. 11
• The construction yields a relational problem with classically verifiable witnesses that quantum queries can find for every input, while classical queries cannot find them efficiently on average.The relation uses an N = 2n-bit input and witnesses of length m = poly(n).Source: §1.3 · p. 11

1.5 Organization

• Sections 2–4 cover preliminaries, definitions and basic relations, and the error-correcting-code properties used later.Section 2 includes quantum-computation preliminaries.Source: §1.5 · p. 11
• Sections 5–6 present a technical lemma for protocol correctness and the proof of quantumness.The lemma may be more broadly useful.Source: §1.5 · p. 11
• Sections 7–8 use the proof of quantumness for cryptographic-primitive counterexamples and give proofs of randomness.Source: §1.5 · p. 11

2 Preliminaries

• The preliminaries fix notation for sets, distributions, statistical distance, min-entropy, quantum-state approximation, and proportionality.Source: §2 · pp. 11–12

2.1 Finite Fields

• Finite-field preliminaries set F_q for prime-power q and define vector encodings, inner products, trace, Hamming weight, and coordinate restriction.Source: §2.1 · p. 12

2.2 Quantum Fourier Transform over Finite Fields

• The quantum Fourier transform over F_q is approximable in polynomial time, and the transform over Σ is defined as a tensor product of transforms over F_q.The section also reviews Parseval’s equality and states lemmas for product functions and convolution.Source: §2.2 · pp. 12–14

2.3 Other Lemmas

• The remaining lemmas include a Chernoff bound and a hash-function lemma for quantum-query algorithms using 2q-wise independent hashes.Source: §2.3 · p. 15

3 Cryptographic Definitions in the Random Oracle Model

• The paper distinguishes classical and quantum random-oracle queries and classical-advice variants, and does not consider quantum auxiliary inputs.Source: §3 · p. 16
• The section defines oracle-aided one-way functions and collision resistance, including classical- and quantum-query adversaries and auxiliary-input variants.Keyless collision resistance cannot provide security against non-uniform adversaries because collisions can be hardcoded as advice.Source: §3 · pp. 16–17
• Proofs of quantumness use a quantum prover and classical verifier, with soundness against unbounded classical-query adversaries; keyless soundness cannot hold against non-uniform adversaries.Source: §3 · pp. 17–18
• The paper introduces certifiable entropy and randomness definitions because conditioning only on acceptance can leave a deterministic device’s output with zero entropy.Source: §3 · p. 18
• The definitions require protocol output to retain min-entropy or be uniform even conditioned on the random oracle, separating protocol-derived entropy from oracle randomness.For proofs of min-entropy, correctness and the min-entropy condition imply that honest verification outputs have at least h bits of min-entropy for an overwhelming fraction of oracle-key pairs.Source: §3 · pp. 18–19
• A proof of randomness outputs exactly h bits and requires succinct verifier randomness and statistical closeness to uniform when acceptance occurs with inverse-polynomial probability.Source: §3 · p. 19
• An extractor converts proofs of min-entropy into proofs of randomness while preserving keylessness, and public verifiability can be retained with a final verifier message.Source: §3 · pp. 19–20

3.1 From Uniform to Non-Uniform Security

• Salting lifts one-wayness, collision resistance, and proof-of-quantumness soundness to classical-advice adversaries when winning is efficiently verifiable, while min-entropy and randomness need a separate small-salt argument.Source: §3.1 · p. 20

4.1 Definitions

• The definitions cover folded linear codes, their duals, and list recoverability; list recoverability here bounds the qualifying codeword list without requiring that it be efficiently computed.An m-folded version groups coordinates into blocks of size m, and any folded linear code can be represented as such a folding of a linear code.Source: §4.1 · pp. 21–22

4.2 Suitable Codes

• For any constants 0 < c < c′ < 1, an explicit folded linear code family has |Σ| = 2^λΘ(1), n = Θ(λ), |Cλ| ≥ 2^(n+λ), and (ζ, ℓ, L)-list recoverability with ζ = Ω(1), ℓ = 2^λc, and L = 2^Õ(λc′).The stated instantiation is folded Reed–Solomon; the proof uses list recoverability results for folded Reed–Solomon codes and list decoding of their duals.Source: §4.2 · p. 22

4.3 Proof of Lemma 4.2

• The code lemma’s third property is used only in the one-way-function counterexample, not in the proof-of-quantumness construction.The section also describes dual-code list decoding as part of establishing the code requirements.Source: §4.3 · p. 22, §4.2 · p. 22

4.3.1 Preparation

• The preparation reviews generalized Reed–Solomon codes, their duals, and classical polynomial-time list decoding, then gives the folded Reed–Solomon list-recovery result used in the construction.The cited list-recovery result is attributed to [Rud07, Sec. 3.6], with a corresponding journal presentation in.Source: §4.3.1 · p. 23

4.3.2 Construction

• The construction sets Cλ to a folded Reed–Solomon code and verifies that its parameters give the required length, alphabet size, and code size.For list recoverability, the proof applies the folded Reed–Solomon list-recovery lemma and checks its parameter inequalities for sufficiently large λ.Source: §4.3.2 · p. 24
• For the stated range of j, no codeword has Hamming weight n−j, since its polynomial would have at least mj≥k+1 roots and therefore be zero.That contradicts the assumed positive weight n−j.Source: §4.3.2 · p. 26
• For any S⊆[n] of size j, x_S is uniformly distributed over Σ^j, using that a degree-at-most-k polynomial is determined by its values on k+1 points.The supplied passage truncates the condition following “when x.”Source: §4.3.2 · p. 26

• The lemma supports the correctness proof of the proof of quantumness and is inspired by the quantum step of Regev’s reduction from LWE to worst-case lattice problems.Source: §5 · p. 27
• For a function F, GOOD pairs satisfy F(x + e) = x, while BAD is their complement.Source: §5 · p. 27
• The lemma’s setup also introduces the unitaries Uadd and UF.Source: §5 · p. 27
• The proof derives inequalities from Equations (19) and (20), uses Equation (21), Equation (22), and the convolution theorem, and completes Lemma 5.1.Source: §5 · pp. 27–28

6 Proofs of Quantumness

• A keyed proof of quantumness relative to a random oracle satisfies soundness in the AI-CROM.Source: §6 · p. 28
• The keyless construction is correct with overwhelming probability over the random oracle, and an honestly generated proof passes verification with probability 1 − negl(λ).Source: §6 · pp. 29, 31, definition · p. 37
• The keyless proof is (2λc, 2^-Omega(λ))-sound in the CROM.Theorem 6.1 establishes the keyless random-oracle construction, and Lemma 6.9 gives its soundness bound.Source: §6 · p. 28, definition · p. 36

definition.

• A modified protocol achieves correctness for any oracle H while preserving soundness on random H.The stated motivation is that query-complexity definitions commonly require success for all possible oracle inputs.Source: definition · p. 37

definition

• The repeated protocol eΠ satisfies correctness with overwhelming probability.The argument applies a union bound over the instances j ∈ [t].Source: definition · p. 38
• In the CROM, eΠ has (2λc, |K| · 2^-Ω(tλ))-soundness, by extending the repetition soundness argument and union-bounding over K.The shifted random oracle for each fixed K behaves as another random oracle.Source: definition · p. 38
• Because |K| = 2^poly(λ) for a polynomial independent of t, choosing polynomial t makes the soundness error 2^-Ω(λ).Source: definition · p. 38

7.1 Counterexample for One-Way Functions

• One-way functions are secure in the CROM but not one-way in the QROM, and the direct construction is not even distributionally one-way in the QROM.A quantum oracle user can find an almost uniformly distributed valid preimage.Source: §7.1 · pp. 38–40

7.2 Counterexample for Collision-Resistant Hash Functions.

• Compressing functions are collision-resistant in the CROM but not even one-way in the QROM, via a generic construction based on proofs of quantumness.The theorem also gives keyed functions secure in the AI-CROM but not one-way against oracle-independent adversaries in the QROM.Source: §7.2 · pp. 40–41

7.3 Counterexamples for Public Key Primitives

• Given a PKE scheme that is IND-CPA secure in the CROM, the construction yields one that is IND-CCA secure there but not IND-CPA secure in the QROM; signatures are EUF-CMA secure in the CROM but not EUF-NMA secure in the QROM.These results remove the additional artificial classical oracles and complexity assumptions used in similar prior theorems.Source: §7.3 · p. 41

7.4 A Remark on Pseudorandom Generators

• A CROM-secure, QROM-insecure one-way function does not automatically yield a PRG with the same separation, because a PRG construction may remain secure despite an insecure building-block function.The authors conjecture that CROM and QROM security for PRGs against polynomial-query, unbounded-time adversaries are equivalent, but note that the Aaronson-Ambainis conjecture does not directly settle this because distinguishers receive oracle-correlated PRG values.Source: §7.4 · pp. 41–42

8 Proofs of Randomness

• Conjecture 8.1 posits that a quantum-query algorithm's output probability can be approximated by a deterministic classical algorithm using polynomially many queries in the quantum query count and approximation parameters.The conjecture concerns a random oracle and does not include side information correlated with that oracle.Source: §8 · p. 42
• Assuming Conjecture 8.1, the paper establishes keyless proofs of randomness in the QROM and keyed proofs in the AI-QROM.The section constructs proofs of min-entropy as an intermediate step.Source: §8 · p. 43
• Assuming Conjecture 8.1, a keyless proof of quantumness with soundness yields keyless proofs of min-entropy in the QROM.The argument uses the conjecture to show that an adversary producing low-entropy proofs could be converted into a classical adversary that breaks soundness.Source: §8 · pp. 43–44
• The proof handles low-probability proof outputs by approximating output probabilities and randomly choosing a threshold, avoiding ambiguity when several proofs have similar probabilities.The threshold is selected from (ϵ_A/2, ϵ_A); a counting argument limits how often multiple proofs can lie near it.Source: §8 · pp. 44–45

9 Proof of Theorem 3.11

• The stated transformation turns a QROM proof of min-entropy or randomness into an AI-QROM proof of the corresponding property.It modifies Prove and Verify to use the oracle slice indexed by k1, with Prove0 and Verify0 operating on that slice.Source: §9 · p. 47
• The proof controls entropy by bounding each output probability’s multiplicative change under resampling, since negligible additive distributional error may not preserve entropy.For the E1 resampling distribution, the most likely output changes negligibly, so the adversary’s min-entropy increases by at most a negligible amount.Source: §9 · pp. 48–49
• Resampling uses E1, concentrated on zero modified salts, and E2, supported on at least d salts; the adversary’s output distributions under them are identical when k ≥ 4q.E1 leaves H unchanged with high probability, while E2 resamples enough slices to help make the tested slice independent of the advice.Source: §9 · pp. 49–50
• Under E2, for most salts outside the resampled set, the tested oracle slice is statistically close to uniform even given the advice and resampled oracle.Resampling erases information about the selected slice from H′, yielding the stated closeness bound.Source: §9 · pp. 51–52
• The reduction uses the resampled oracle and the adversary to obtain a non-uniform adversary that breaks the underlying QROM proof with non-negligible probability.For a suitable choice of the fixed oracle, advice, resampled set, and salt, the constructed adversary inherits low output entropy and breaks (Prove0, Verify0).Source: §9 · p. 53
• After setting B’s oracle to H0, the probability that its min-entropy is below h + 1 remains non-negligible because the oracle change affects that probability only negligibly.H0 and H′(k1||·) are statistically close even given a(H), S, k1, and H′(k1||·).Source: §9 · p. 53
• This completes the proof of Theorem 3.11.Source: §9 · p. 53