PaperlayerView exact revision on arXiv

Source-linked AI summary

Unconditional Certified Randomness without Structure

Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja, Bhaskar Roberts, Joseph Slote, Avishay Tal

arXiv:2608.31112v1quant-phcs.CR

TL;DR

Prior certified-randomness protocols relative to a random oracle either assumed the Aaronson–Ambainis conjecture or proved security only against low query-depth adversaries. This paper uses a slight variant of the Yamakawa–Zhandry problem to give an unconditional protocol with min-entropy guarantees against subexponentially many adaptive quantum queries.

  • Problem

    Prior random-oracle certified-randomness work assumed the Aaronson–Ambainis conjecture or covered only low query-depth adversaries, leaving unconditional security for adaptive quantum queries open.

    Source: §1 · p. 4

  • Method

    The paper proves a slight variant of the Yamakawa–Zhandry problem using hybrid arguments and oracle reprogramming with a relaxed guarantee for heavily queried coordinates.

    Source: §1.1 · pp. 4–5

  • Results

    For every c ∈ (0, 1/2), the protocol guarantees min-entropy Ω(n^c) against adversaries making at most 2^{o(n^c)} adaptive queries.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The resulting certified-randomness protocol is single-prover, non-interactive, and publicly verifiable.

    Source: §1.1 · p. 4

    The query-norm polytope argument preserves only Θ(√n) heavily queried symbols, short of the linear-coordinate agreement needed by the original Yamakawa–Zhandry code.

    Source: The query-norm polytope · p. 12

Abstract

from arXiv · show

We obtain a certified randomness protocol in the quantum random oracle model. The protocol is non-interactive and publicly verifiable with a classical verifier, and is based on Yamakawa and Zhandry's proof of quantumness [JACM'24]. We prove unconditional security of this protocol against adversaries making subexponentially-many adaptive quantum queries to the random oracle. Prior work on certified randomness relative to a random oracle additionally assumed the Aaronson--Ambainis conjecture or proved security only against low query-depth adversaries.

1 Introduction

Motivated by limitations of existing certified-randomness protocols and the Aaronson–Ambainis conjecture dependence of the Yamakawa–Zhandry approach, this work gives an unconditional QROM protocol with a slight variant of the YZ problem. The protocol is single-prover, non-interactive, and publicly verifiable.

1 Introduction

  • The original YZ algorithm’s essentially uniform output yields certified randomness assuming the Aaronson–Ambainis conjecture, motivating an unconditional protocol retaining its desirable features.The YZ quantum advantage is described as structure-less, arising from a random oracle without additional algebraic or computational structure; this work advances understanding of its inherent randomness.Source: §1 · pp. 3–4, §1.1 · p. 5

1.1 Our result

  • The biased YZ variant changes the code and oracle distribution: each H_i outputs 1 independently with probability p=1/Θ(√n), and this oracle can be simulated in the standard QROM without loss.The biased oracle can also be constructed directly in the QROM.Source: §1.1 · p. 4
  • For every c∈(0,1/2), the protocol certifies Ω(n^c) min-entropy against even computationally unbounded adversaries making at most 2^o(n^c) adaptive quantum queries.With overwhelming probability over the random oracle, any adversary accepted with noticeable probability has output min-entropy at least Ω(n^c), conditioned on acceptance.Source: §1.1 · p. 4
  • The prover returns a solution to the biased YZ problem, and the verifier outputs it after checking validity, giving a simple certified min-entropy protocol.The guarantee is information-theoretic subject to a bound on the prover’s quantum queries.Source: §1.1 · p. 4
  • The proof lifts the original YZ min-entropy result’s o(log n)-layer adaptivity restriction to subexponentially many adaptive queries by using a slight problem variant.The cited prior result handled polynomially many queries in at most o(log n) adaptive layers.Source: §1.1 · p. 5
  • The proof introduces relaxed oracle reprogramming for heavily queried coordinates and uses query norms and a query-norm polytope to constrain changes between oracles.Strings with heavy query weight on many symbols retain significant query weight under many reprogrammings.Source: §1.1 · p. 5

2 Overview

The overview develops a proof strategy for a standard-QROM min-entropy guarantee, framing the challenge of controlling adaptive queries under oracle reprogramming and connecting query-norm reprogramming with code changes, list recovery, Fourier decoding, and oracle biasing.

2.1 The Yamakawa–Zhandry search problem

  • The YZ search problem asks for a codeword x whose coordinates all hash to zero; for an appropriate list-recoverable code, the YZ algorithm finds one with a single layer of parallel quantum queries [YZ24].The algorithm outputs samples essentially uniformly over correct strings.Source: §2.1 · p. 5, §2.2 · p. 6

2.2 The min-entropy proof strategy at a high level

  • The proof uses query norm to show that low-entropy provers heavily query correct answers, while query-bounded provers cannot heavily query any correct answer.Together, the claims yield the stated lower bound; the approach extends beyond, whose result handled o(log n) adaptive layers.Source: §2.2 · pp. 6–7

2.2.1 Proving Claim A: Low-entropy provers heavily query correct answers

  • Reprogramming lightly queried coordinates creates many oracles on which a low-entropy prover still returns its correct answer with noticeable probability, implying that such answers are heavily queried for almost all oracles.The argument bounds the fraction of bad oracles by counting distinct oracle-answer pairs.Source: §2.2.1 · p. 8

2.2.2 Proving Claim B: Query-bounded provers cannot heavily query a correct answer

  • A bipartite counting argument reduces the bad-oracle fraction to a degree ratio, using heavy-coordinate reprogramming to give each bad oracle exponentially many alternatives despite adaptive queries.The reprogrammed oracles retain at least Ω(√n) heavily queried coordinates for the answer.Source: §2.2.2 · p. 9
  • The proof strengthens the code’s list-recovery parameters and biases the random oracle to restore the honest YZ algorithm’s success, requiring weighted counting for both claims.The original code’s parameters were inadequate for the vanishing O(1/√n) fraction of lists needed by the argument.Source: §2.2.2 · p. 10

2.3 Reprogramming heavy coordinates and the query-norm polytope

  • Local stability of query norms yields a polytope of constraints showing that reprogramming cannot eliminate all noticeable query norm from a set of queried inputs; protecting O(k^2) inputs can preserve k such inputs.The argument derives local stability by applying the swapping lemma to intermediate computation states.Source: §2.3 · p. 11, The query-norm polytope · pp. 11–12
  • The polytope lemma yields exponentially many reprogrammed oracles retaining noticeable query norm on Θ(√n) symbols, short of the original code’s linear-agreement requirement.The authors leave open whether 2^{Ω(n)} reprogrammed oracles can preserve Ω(n) heavily queried inputs while leaving a linear number freely reprogrammable; the polytope framework might reduce this to high-dimensional geometry.Source: The query-norm polytope · pp. 12–13

2.4 Modifying the code and biasing the oracle

  • The modified code’s low-agreement list recovery needs only Θ(√n) approximately known symbols, matching the heavy symbols preserved by reprogramming.The list contains at most L=2^{O(n^c log n)} codewords meeting the agreement condition.Source: §2.4 · p. 13, The query-norm polytope · p. 13
  • Biasing the oracle makes Fourier error nonzero on only O(√n) coordinates with overwhelming probability, restoring dual-code decoding within its unique-decoding radius.The error is nonzero in any given coordinate with probability O(p)=O(1/√n); without the bias, it affects at least a constant fraction of coordinates and prevents decoding.Source: §2.4 · p. 13

2.5 Security of the updated construction

  • For Q=2^{o(n^c)} queries, any adversary causing noticeable acceptance must produce accepting outputs with min-entropy at least h∞=o(n^c).The two reprogramming arguments make a predictable correct answer imply heavy querying on almost all its symbols, which is incompatible with the bound on such codewords except with negligible probability.Source: §2.5 · pp. 14–15
  • The min-entropy guarantee holds in the standard QROM by representing the uniform oracle as the biased oracle plus residual information, proving security for each fixed residual oracle, and averaging.This establishes the guarantee conditioned on the entire uniform oracle, not only on the biased bit oracle.Source: §2.5 · p. 15

3 Preliminaries

This section defines the quantum random oracle model and query-bounded algorithm notions, then states bounds on query norms and the effect of changing an oracle.

3 Preliminaries

  • Euclidean distance between two states upper-bounds their trace distance, by the Fuchs–van de Graaf inequality [NC12, Ch. 9].Source: §3 · p. 15

3.1 Quantum Random Oracle Model

  • In the QROM, a quantum algorithm can query a uniformly random function on a superposition of inputs and receive a coherent response.The oracle takes binary-string inputs of any finite length and returns uniformly random binary strings of a desired length.Source: §3.1 · p. 16
  • For finite S, H independently outputs 1 with probability p = 2^-d; using query access to regular random oracle F, truncate its output to d bits and set H(x)=1 iff it is 1^d.Source: §3.1 · p. 16

3.2 Query-Bounded Algorithms

  • At most Q^2/α^2 inputs can have query norm at least α for an algorithm making Q queries.Query norm is the square root of query weight.Source: §3.2 · pp. 16–17
  • The adapted swapping lemma says adversary states under oracles H and H′ are close in Euclidean distance when query norm is small on their differing inputs [EJPV98, Lemma 2] [BBBV97, Theorem 3.3].The lemma considers the set X of inputs on which the two oracles differ.Source: §3.2 · p. 18

4 Reprogramming Lemmas

Section 4 develops a reprogramming technique for use in the min-entropy proof: when query norm is spread over a set of inputs, many reprogrammings preserve substantial query norm on that set. Its key ingredient is local stability: changing coordinates with small query norms barely changes norms on other coordinates.

4.1 Local Stability

  • Changing oracle coordinates with small query norms barely changes query norms on other coordinates, a local-stability property derived from the swapping lemma.The section treats query norms as measurements on the algorithm’s state.Source: §4.1 · p. 19

4.2 The Query Norm Polytope

  • The query norm polytope describes the linear inequality constraints on query norms attainable by a quantum query algorithm across different oracles.The section’s proof of the reprogramming result relies on local stability of query norms.Source: §4.2 · p. 20
  • When every input in M has query norm at least β, Lemma 4.3 finds a subset A_k so every allowed reprogramming leaves at least k inputs with query norm above a threshold depending on β, Q, and |M|.The section states that there are 2^Ω(|M|) ways to reprogram while retaining significant query norm on inputs in M.Source: §4.2 · p. 20

5 Error-Correcting Codes

The section constructs folded Reed–Solomon codes for the certifiable min-entropy construction, choosing parameters to support list recovery when only O(√n) symbols are approximately known. It then establishes the code-family properties needed by that construction.

5.1 Definitions

  • The section defines folded Reed–Solomon codes and list recovery, using definitions and proof strategies adapted from [YZ24, Section 4].List recovery bounds the number of codewords consistent with lists of possible symbols at each position.Source: §5 · p. 23, §5.1 · pp. 23–24

5.2 Construction

  • The construction selects folded Reed–Solomon parameters including m=n+2, N=mn, and q=(n+1)^2 to obtain the code family.The family is set as C_λ = FRS with the selected parameters; the section states that these choices are intended to satisfy Lemma 5.2.Source: §5.2 · p. 24

5.3 Properties

  • The resulting folded linear codes support list recovery with list size L=2^{O(λ^c log λ)} for sufficiently large λ.The lemma concerns noise distributions assigning zero probability at least 1−1/(40√n), and the construction targets recovery when only O(√n) symbols are approximately known.Source: §5.3 · pp. 25–26
  • A deterministic polynomial-time decoder uniquely recovers any dual-codeword x from x+e when e is a good error with weight at most τ=⌊(k+1)/2⌋.The dual code is an m-folded generalized Reed–Solomon code, and the stated recovery condition is Decode_C⊥(x+e)=x for every x in the dual and every good error.Source: §5.3 · pp. 27–28

6 Certifiable Min-Entropy Protocol

This section defines certifiable min-entropy protocols in the QROM and presents two constructions using an error-correcting code and a biased random oracle. It proves the correctness of Construction 6.2, including completing the proof of Claim 6.8 by establishing Equation (14).

6.1 Definition

  • A certifiable min-entropy protocol is a publicly verifiable proof system with a quantum prover and classical verifier, where accepted proofs have high min-entropy conditioned on the random oracle.Conditioning on the oracle ensures the proof contributes randomness beyond the oracle’s own randomness.Source: §6.1 · p. 28

6.2 Construction

  • The certifiable min-entropy constructions yield different amounts: Construction 6.2 provides o(λ^c) bits, whereas Construction 6.4 provides any poly(λ) bits of min-entropy.The approach uses Section 5.2 error-correcting codes that allow list recovery when only O(√n) symbols are approximately known, and a biased random oracle to reduce dual-basis noise.Source: §6 · p. 28, §6.2 · p. 30

6.3 Proof of Correctness

  • Construction 6.2 is correct: the prover aborts with negligible probability, and the honest proof is accepted except with negligible probability.The proof uses a decoding-based analysis of the prover’s states to show that an honestly generated proof meets the verifier’s acceptance conditions.Source: §6.3 · p. 33
  • The derivation combines (16), (17), and conditional independence.Source: §6.3 · p. 37
  • For Equation (14), the proof defines B to indicate whether e belongs to BadErrors.B is 1 for e in BadErrors and 0 otherwise.Source: §6.3 · p. 38
  • The proof uses bV(x) = 0 outside C⊥, the convolution theorem, and Parseval’s theorem to complete an equality.Other steps invoke Claim 6.9, Parseval’s and convolution theorems, and inequality (13).Source: §6.3 · pp. 38–39
  • Claims 6.11 and 6.12, together with the definition of V, provide the final step establishing Equation (14) and Claim 6.8.Source: §6.3 · p. 39

7 Proof of the Min-Entropy Property

Theorem 7.1 shows that Construction 6.2 has certifiable min-entropy against adversaries making subexponentially many queries, and Corollary 7.2 gives the same guarantee when the construction is instantiated in the QROM. The proof relates successful low-entropy outputs to how much query norm the adversary must spend on their symbols.

7 Proof of the Min-Entropy Property

  • Construction 6.2 has (Q,h∞)-certifiable min-entropy for Q = 2^o(λ^c) and h∞(λ) = o(λ^c), where c < 1/2; the same guarantee holds in the QROM.Theorem 7.1 applies to the biased-random-oracle construction, and Corollary 7.2 states that its QROM instantiation retains the guarantee.Source: §7 · p. 40

7.1 Low-entropy adversaries heavily query correct answers.

  • If an adversary outputs a correct answer with high probability, it must give non-negligible query norm to most of that answer’s symbols; the probability of an output with s low-query symbols is at most 2 · (1 − p)^s.The argument reprograms selected answer-symbol oracle outputs from 0 to 1 and bounds the probability of the resulting set of oracle-output pairs.Source: §7.1 · p. 40

7.2 Query-bounded adversaries cannot heavily query a correct answer.

  • For query complexity Q = 2^{o(λ^c)}, with overwhelming probability over H, the adversary does not heavily query any correct answer; heavy querying means many symbols each receive large query norm.Source: §7.2 · p. 42

7.3 Finishing the proof.

  • For every h satisfying Events 1 and 2, Lemma 7.7 gives an x_h satisfying Event 3; the cited conditional probability is at least 2^{-h∞(λ)}>0, and Lemma 7.3 yields a contradiction to β(λ) being non-negligible.Source: §7.3 · pp. 46–47

8 AI Disclosure

ChatGPT 5.6 helped refine FRS-code parameter choices, while all techniques used in the paper were human-generated; AI brainstorming produced ideas that were not used.

AI Disclosure

  • ChatGPT 5.6 was used to refine parameter choices for the family of FRS codes; all other techniques in the work were human-generated.Source: §8 · p. 47
  • AI brainstorming produced interesting approaches and a counterexample to stronger variants of Question 1, but none were used and the question remains open.Source: §8 · p. 47

A Proof of Corollary 7.2

The proof transfers Theorem 7.1’s min-entropy guarantee to algorithms using a standard random oracle to instantiate the biased oracle. The transfer preserves the asymptotic parameters despite a factor-of-two query overhead.

A Proof of Corollary 7.2

  • For p = 2^-d, the encoding sets H_F(x) = 1 exactly when F(x) = 1^d, yielding the p-biased oracle; the reverse map includes the extra randomness not determined by H_F.F is uniform over regular random oracles, and Pr[H_F(x) = 1] = 2^-d = p.Source: A Proof of Corollary 7.2 · pp. 50–51
  • For fixed r, each query to F_{h,r} is simulated using two queries to h, so a Q-query algorithm yields an H-oracle algorithm making at most 2Q queries.The simulation computes h(x), answers the query, and uncomputes h.Source: A Proof of Corollary 7.2 · p. 51
  • The min-entropy guarantee transfers to standard-random-oracle algorithms with identical asymptotic parameters; the factor-of-two query overhead does not change the asymptotic statement.The proof applies to an algorithm making Q(λ) = 2^o(λ^c) queries, with h∞(λ) = o(λ^c).Source: A Proof of Corollary 7.2 · pp. 50, 52

Related papers

Loading 2608.31112v1…