Source-linked AI summary
Certified Randomness without Structure Against Shallow-Query Adversaries
Dakshita Khurana, Bhaskar Roberts, Avishay Tal
TL;DR
The paper asks whether the Yamakawa-Zhandry certifiable-randomness guarantee can avoid the unproven Aaronson-Ambainis conjecture. It proves the guarantee unconditionally for low-depth quantum adversaries, using a proof based on query depth and heavy-query contradictions, with scope limited to o(log λ) adaptive rounds.
Problem
The open question is whether Yamakawa-Zhandry’s certifiable-randomness guarantee can be established without the unproven Aaronson-Ambainis conjecture.
Method
The proof exploits limited adaptive query depth by combining a heavy-query consequence for successful low-entropy adversaries with a bound ruling out heavily queried correct codewords.
Results
Any adversary making o(log λ) rounds of arbitrarily wide parallel queries that causes acceptance with noticeable probability must sample outputs with Ω(λ^c/2) bits of min-entropy.
Takeaways & Limitations
The Yamakawa-Zhandry protocol’s certifiable-randomness guarantee holds unconditionally against computationally unbounded adversaries within the stated sub-logarithmic query-depth regime.
Takeaways & Limitations
The technique is limited to o(log λ) adaptive rounds; extending the guarantee to ω(log λ) or polynomially many rounds remains open and currently relies on the Aaronson-Ambainis conjecture.
Abstract
from arXiv · showhide
In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample their preimage from a high-entropy distribution over possible answers. If true, this would give a certifiable randomness protocol in the quantum random oracle model. As partial evidence for their conjecture, Yamakawa and Zhandry proved the security of their certifiable randomness protocol assuming the Aaronson-Ambainis conjecture. We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture, against low query-depth quantum adversaries: specifically, adversaries that make up to o(\log λ) adaptive quantum queries to the random oracle.
1 Introduction
The paper addresses whether the Yamakawa-Zhandry certifiable-randomness guarantee can be proved unconditionally, and answers yes for quantum adversaries with o(log λ) adaptive query rounds.
- 1 Introduction: The QROM candidate protocol is non-interactive, efficiently publicly verifiable, and uses only a single quantum device.It is presented as avoiding the demanding spatial restrictions of device-independent protocols and the assumptions or efficiency costs of earlier computational approaches.
- 1 Introduction: Yamakawa and Zhandry’s protocol asks a prover to find a valid codeword satisfying H_i(x_i) = 0 across all coordinates, using one round of parallel quantum queries.The corresponding classical problem remains hard even for algorithms making sub-exponentially many queries.
- 1 Introduction: The conjectured guarantee is that every successful prover samples from a high-min-entropy distribution, making verifier acceptance certify output unpredictability.The honest quantum algorithm samples uniformly from a large set of valid codewords.
- 1 Introduction: The prior Yamakawa-Zhandry security proof relied on the unproven Aaronson-Ambainis conjecture, which asserts that low-degree bounded polynomials have a highly influential coordinate.This left open whether the randomness guarantee could be established from first principles.
- 1 Introduction: The paper proves the guarantee unconditionally for computationally unbounded quantum adversaries making at most o(log λ) adaptive query rounds.Each round may contain polynomially many parallel quantum queries; only the number of sequential rounds is bounded.
- 1 Introduction: Any adversary making o(log λ) rounds of arbitrarily wide parallel queries that is accepted with noticeable probability must output a distribution with Ω(λ^c/2) bits of min-entropy.Because the honest algorithm uses one parallel-query round, the result covers sub-logarithmically many adaptive rounds beyond that requirement.
2 Technical Overview
The proof establishes certifiable randomness for the Yamakawa–Zhandry protocol against adversaries with o(log λ) adaptive query layers by showing that low-entropy outputs require heavy querying, which shallow adversaries cannot achieve.
- The Yamakawa-Zhandry Problem: The Yamakawa–Zhandry problem asks for a codeword whose symbols all hash to zero, and list-recoverability limits how many codewords can match partially known zero-hash symbols.A classical adversary must leave unchecked positions, which independently hash to zero only with exponentially small probability.
- The Yamakawa-Zhandry Problem: The honest quantum algorithm solves the problem with a single layer of parallel queries and measures a random valid codeword.The output is inherently random because it is sampled from a large set of valid codewords rather than targeted in advance.
- Certified Randomness: The result removes the Aaronson–Ambainis conjecture for shallow-query adversaries, while extending the guarantee to ω(log λ) or polynomially many adaptive rounds remains open.The threshold bootstrapping technique breaks down beyond O(log λ) rounds because its thresholds grow doubly exponentially.
- Certified Randomness: A low-entropy adversary must assign non-negligible query weight to all but a small number of symbols in its output codeword.The Heavy Query Lemma derives this requirement by reprogramming low-weight positions and using the swapping lemma to show that the adversary would otherwise remain likely to output an invalidated answer.
- Certified Randomness: For o(log λ) adaptive query layers, no correct codeword is heavily queried with overwhelming probability, contradicting the requirement for any successful low-entropy adversary.The proof combines the heavy-query requirement with a counting argument over reprogrammed bad oracles.
3 Preliminaries
This section defines certifiable min-entropy protocols and presents the Yamakawa-Zhandry-based candidate construction. It also formalizes bounded-depth, parallel-query adversaries and the query-weight tools used to analyze them.
- Certifiable Min-Entropy: A certifiable min-entropy protocol requires accepting proofs to retain high min-entropy after conditioning on the random oracle.The verifier outputs a string or rejection, while the prover and verifier have quantum oracle access.
- Certifiable Min-Entropy: (D,h∞)-certifiable min-entropy quantifies security against unbounded adversaries making D layers of W parallel quantum queries.The query width W is polynomially bounded, and the guarantee applies to the verifier’s output conditioned on acceptance.
- The Yamakawa-Zhandry Protocol: The candidate protocol asks an adversary to find a codeword x in a list-recoverable code C satisfying H(x)=0 under a random oracle.The oracle is coordinate-wise, with H(x)=(H1(x1),...,Hn(xn)); the prover and verifier use parallel queries and check zero preimages.
- The Yamakawa-Zhandry Protocol: Distinct codewords differ on at least (1−α)n symbols, while list recovery bounds the number of codewords consistent with most coordinate-wise candidate sets.The list-recovery parameters include ℓ=2^(λ^c) and L=2^Õ(λ^c′).
- Query-Bounded Algorithms: The construction satisfies the protocol’s syntax and correctness properties, and its security analysis models algorithms through query weights across sequential layers.Query weights are nonnegative, cumulative weights cannot decrease, and the swapping lemma compares oracle executions when differing positions receive little query weight.
- Query-Bounded Algorithms: Parallel-query algorithms are represented by query registers, interleaved unitaries, and a measurement, with each layer containing W oracle queries.The swapping argument reduces parallel layers to a single-query analysis by viewing a layer as one query to an oracle applying H in parallel.
4 Ruling Out 𝑜(log 𝜆)-Depth Strategies
The paper proves that the Yamakawa-Zhandry construction provides certifiable min-entropy against adversaries with o(log λ) adaptive query rounds. The proof combines a heavy-query lemma with a counting argument showing that low-depth adversaries cannot heavily query any correct codeword.
- Main result: The construction satisfies (D,h∞)-certifiable min-entropy for D(λ)=o(log λ) and h∞(λ)=o(λ^c/2).Here c is a constant determined by the list-recoverable code.
- Step 1: Heavy querying: A successful low-entropy adversary must assign non-negligible query weight to almost all but s symbols of its output.The heavy-query condition formalizes the requirement that the adversary checks most symbols before committing to a correct answer.
- Step 1: Heavy querying: The proof constructs bad oracles by flipping selected codeword-symbol outputs from 0 to 1, making the candidate answer incorrect while preserving heavy querying.The selected symbols are chosen among those receiving the smallest cumulative query weight before the first strongly-heavy query.
- Step 2: Low-depth contradiction: With overwhelming probability over the random oracle, no correct codeword is heavily queried by an o(log λ)-depth adversary.Assuming the contrary yields both a non-negligible and negligible probability for the same event, producing a contradiction.
- Step 2: Low-depth contradiction: List recoverability bounds the number of codewords heavily queried under a bad oracle by L=2 ˜O(λ^c′), enabling the counting argument.The same bound limits how many good pairs can map to any bad oracle.
5 AI Disclosure
The paper reports that AI assisted with clarity and polish in Sections 1 and 2, while the work’s techniques were developed without AI assistance.
- AI was used to improve clarity and polish in Sections 1 and 2.
- The techniques in the work were developed by human trial-and-error without AI assistance.