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 in the QROM either relied on the Aaronson–Ambainis conjecture or handled only limited query adaptivity. This paper modifies the Yamakawa–Zhandry problem with a biased random oracle and proves an unconditional, single-prover, non-interactive, publicly verifiable protocol. For every c∈(0,1/2), it certifies Ω(n^c) min-entropy against adversaries making at most 2^o(n^c) adaptive quantum queries.

  • Problem

    Prior QROM certified-randomness approaches relied on the Aaronson–Ambainis conjecture or restricted adversaries to low query-depth, leaving unconditional security against highly adaptive queries unresolved.

  • Method

    The paper uses a slight Yamakawa–Zhandry variant with a biased random oracle and proves security through hybrid arguments, oracle reprogramming, query norms, and a query-norm polytope.

  • Results

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

  • Takeaways & Limitations

    Certified randomness can be obtained unconditionally in the QROM while retaining single-prover, non-interactive, and publicly verifiable verification.

  • Takeaways & Limitations

    The proof’s polytope argument preserves only Θ(√n) heavily queried symbols, falling short of the linear-coordinate list-recovery condition of the original code.

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

The paper asks whether certified randomness can exist unconditionally in the QROM while retaining single-prover, non-interactive, and publicly verifiable features. It answers affirmatively with a biased variant of the Yamakawa–Zhandry problem and certifies min-entropy against highly adaptive quantum-query adversaries.

  • 1 Introduction: Existing certified-randomness approaches require impractical non-communication assumptions, interaction, private verification, exponential verification, or the Aaronson–Ambainis conjecture.These limitations motivate an unconditional QROM protocol retaining single-prover, non-interactive, and publicly verifiable verification.
  • 1.1 Our result: The resulting protocol is single-prover, non-interactive, and publicly verifiable.The prover returns a biased-YZ solution, and the verifier checks validity using the random oracle before outputting the solution.
  • 1.1 Our result: The paper introduces a biased YZ problem by changing the code and using oracle bits that output 0 with probability 1−p and 1 with probability p, where p=1/Θ(√n).The biased oracle can be constructed directly in the QROM, and the construction is a slight variant of the original YZ problem.
  • 1.1 Our result: For every c∈(0,1/2), the protocol certifies min-entropy at least Ω(n^c) against adversaries making at most 2^o(n^c) adaptive quantum queries.Conditioned on acceptance, even computationally unbounded adversaries with this query bound have output min-entropy at least Ω(n^c) with overwhelming probability over the oracle.
  • 1.1 Our result: The proof removes the prior low-adaptivity restriction using oracle reprogramming, query norms, and a query-norm polytope.The relaxed reprogramming guarantee remains effective when modifying heavily queried coordinates.
  • 1 Introduction: The work studies the only known genuinely structure-less quantum advantage relative to a random oracle without additional algebraic or computational structure.The YZ construction has also motivated subsequent work on Decoded Quantum Interferometry.

2 Overview

The paper adapts the Yamakawa–Zhandry search problem to certify min-entropy against fully adaptive quantum-query adversaries. It combines heavy-coordinate reprogramming, a query-norm framework, improved list recovery, and a biased oracle to obtain unconditional security.

  • The YZ problem: The Yamakawa–Zhandry search problem asks for a codeword x satisfying H_i(x_i) = 0 at every coordinate, given quantum access to H.The YZ algorithm finds such a correct x, and its output is essentially uniform over correct solutions.
  • Query norm: The proof tracks query norm, the square root of query weight, to constrain how an adversary’s oracle queries can be distributed across coordinates and symbols.Heavy querying is defined by many codeword coordinates receiving at least a threshold amount of total query norm.
  • Code modification: The original code’s list recovery is insufficient because the argument preserves only O(1/√n) or Θ(√n) approximately known symbols rather than a linear fraction.The construction therefore modifies the code so list recovery works with only Θ(√n) approximately known symbols.
  • Reprogramming: Heavy-coordinate reprogramming produces exponentially many alternative oracles while preserving noticeable query norm on Θ(√n) symbols of the same codeword.This supplies the lower-degree bound in the reprogramming-based counting argument for Claim B.

3 Preliminaries

This section introduces the quantum random oracle model, quantum query algorithms, and query norms used to analyze oracle-dependent computations.

  • The quantum random oracle provides coherent oracle responses to quantum superpositions of inputs.The underlying oracle is a uniformly random function with arbitrarily long binary inputs and outputs.
  • A quantum query algorithm can make a bounded number Q of oracle queries and measure outcomes after oracle interactions.The algorithm is parameterized by its maximum query count Q.
  • Query norm measures the amplitude magnitude assigned to a classical oracle location during a query, while query weight is its squared probability.Query norm is the square root of query weight.
  • For an algorithm making Q queries, at most Q^2/α^2 inputs can have query norm at least α.This bounds how broadly large query norms can be distributed across oracle locations.
  • The swapping lemma bounds how much an algorithm’s state changes when two oracles differ on a set of inputs.The bound depends on the query mass placed on the differing locations and is proved by unrolling the query-by-query recurrence.

4 Reprogramming Lemmas

This section develops reprogramming tools showing that quantum query norms remain sufficiently stable when oracle values are changed, even across heavily queried coordinates.

  • Local Stability of Query Norms: Local stability shows that changing oracle inputs with small query norms barely changes the query norms of other inputs.The argument views query norms as measurements and derives the property from the swapping lemma.
  • The Query Norm Polytope: The query norm polytope represents simultaneous linear constraints on query norms across different oracle reprogrammings.It is analogous to a linear program without an objective function.
  • Reprogramming Lemma: 2^Ω(|M|) reprogrammings preserve significant query norm on at least |M| inputs when the original algorithm heavily queries every input in M.The result is designed for sets M of size Ω(n) used in the certifiable min-entropy proof.
  • Proof Strategy: The proof proceeds inductively by partitioning M into heavily and lightly queried inputs, using local stability to transfer a heavy coordinate across hybrids.The construction combines the inductive guarantee on Light with an additional heavy input.
  • Proof Strategy: The induction concludes that every oracle in the surviving reprogrammed family has k inputs in M whose query norms exceed the target threshold.The final set is formed by combining the recursively removed coordinates with the Heavy subset.

5 Error-Correcting Codes

This section constructs folded Reed–Solomon codes with list-recovery and dual-decoding properties tailored to the biased YZ problem and its sparse errors.

  • Construction: The code family uses folded Reed–Solomon codes with parameters chosen to support list recovery when only O(√n) symbols are approximately known.The construction adjusts the Yamakawa–Zhandry code family for the new recovery regime.
  • List Recovery: The constructed family is folded linear and list recoverable with list size L=q^s≤2^O(λ^c log λ).The parameters are chosen so the resulting folded Reed–Solomon codes satisfy the required list-recovery conditions.
  • Dual Decoding: The dual code is an m-folded generalized Reed–Solomon code whose unfolded version admits deterministic polynomial-time unique decoding.The decoder runs in time polynomial in N and log q, hence polynomial in λ.
  • Dual Decoding: For every dual codeword x and every GoodErrors vector e, decoding x+e returns x exactly.This follows because the noise weight is within the dual code’s unique-decoding radius.

6 Certifiable Min-Entropy Protocol

This section constructs certifiable min-entropy protocols from list-recoverable codes and a biased random oracle, following the Yamakawa–Zhandry proof-of-quantumness template. The protocols are non-interactive and publicly verifiable, with guarantees ranging from subpolynomial to polynomial min-entropy.

  • Construction: The constructions combine list-recoverable error-correcting codes with a biased random oracle within the Yamakawa–Zhandry proof template.The codes support list recovery when only O(√n) symbols are approximately known, while bias reduces noise in the dual basis.
  • Construction 6.4: Construction 6.4 applies complexity leveraging to Construction 6.2 and provides any polynomial number of min-entropy bits while retaining polynomial runtime and query complexity.Its parameters use a larger internal security parameter related to the desired entropy threshold.
  • Protocol definition: A certifiable min-entropy protocol lets a quantum prover produce a classical proof that a classical verifier maps to an output string or rejects.The min-entropy guarantee is evaluated after conditioning on the sampled random oracle and on acceptance.
  • Construction 6.2: Construction 6.2 achieves (Q,h∞)-certifiable min-entropy for Q=2^o(λ^c) and h∞(λ)=o(λ^c), where c<1/2 is determined by the code.Correctness is established separately, and honest proofs are accepted except with negligible probability.

7 Proof of the Min-Entropy Property

The proof establishes certifiable min-entropy against adversaries making subexponentially many adaptive quantum queries. It combines query-norm arguments, oracle reprogramming, and list recovery to rule out heavily queried accepting outputs.

  • Main result: The main theorem guarantees Ω(λ^c) min-entropy against adversaries making Q=2^o(λ^c) queries, for c<1/2.The same guarantee appears for the biased-oracle construction and its standard-QROM instantiation.
  • Query-norm analysis: If an adversary outputs a correct answer with high probability, it must assign non-negligible query norm to most symbols of that answer.Otherwise, it would output the candidate even when insufficiently checked symbols hash to 1.
  • Oracle reprogramming: Relaxed oracle reprogramming creates many related oracles while preserving significant query weight on heavily queried symbols.The proof analyzes reprogrammings that flip selected oracle coordinates from 0 to 1 and uses swapping arguments to compare output distributions.
  • List recovery: List recoverability bounds the number of codewords that can be heavily queried by any fixed oracle to at most L.At least √n/5 coordinates must have large query norm, allowing the code’s list-recovery property to apply.
  • Counting argument: The reprogramming sets are also bounded in overlap: any oracle belongs to T_h for at most L different source oracles.Otherwise two source instances would yield the same codeword and therefore the same reconstructed oracle, contradicting their distinctness.
  • Conclusion: Combining the events and counting bounds shows that, except with overwhelming probability over H, any noticeable-acceptance adversary has conditional min-entropy at least h∞.The contradiction assumes Q=2^o(λ^c) and h∞=o(λ^c), yielding the theorem’s security statement.

8 AI Disclosure

The authors disclose that ChatGPT 5.6 refined parameter choices for the FRS-code family, while the other techniques were human-generated.

  • AI Disclosure: ChatGPT 5.6 was used to refine parameter choices for the family of FRS codes.The authors state that other techniques in the work were human-generated.

A Proof of Corollary 7.2

This appendix transfers the biased-oracle security guarantee to a standard uniform random oracle through an encoding and simulation argument. The transfer preserves asymptotic parameters, with only a constant-factor increase in query complexity.

  • Instantiation: The biased random oracle can be encoded from a standard uniform oracle by outputting 1 exactly when a truncated d-bit oracle value equals 1^d.This produces Pr[H(x)=1]=2^-d=p.
  • Simulation: The encoding is supplemented with independent randomness so that fixing the auxiliary randomness recovers a standard-oracle simulation.For each fixed auxiliary string r, the resulting oracle query can be simulated using two queries to the biased oracle.
  • Adversary transfer: An F-oracle adversary making Q queries is converted into an H-oracle adversary making Q′=2Q queries with the same output distribution.Validity and conditioned-output distributions are preserved under the simulation.
  • Conclusion: Theorem 7.1’s min-entropy guarantee transfers to standard-oracle algorithms with identical asymptotic parameters.The factor of 2 in query complexity does not change the asymptotic statement.
Loading 2608.31112v1…