PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified Randomness with Optimal Rate

Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts

arXiv:2609.38945v1quant-phcs.CR

TL;DR

The paper asks how much min-entropy a deterministic verifier can certify, a question motivated by applications needing verifiable randomness close to uniform. It constructs QROM proofs of maximal and conditional min-entropy, achieving the highest possible guarantee while accommodating the rejection-sampling limit.

  • Problem

    The paper asks for the highest min-entropy threshold certifiable for an n-bit string when the verifier is deterministic.

    Source: §1 · p. 2

  • Method

    The paper constructs a proof of maximal min-entropy in the QROM and uses random oracles as seedless condensers against quantum adversaries.

    Source: §1.1 · pp. 2–3

  • Results

    The construction achieves the maximal guarantee of n−ω(log λ) bits of min-entropy, the highest possible under deterministic verification.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The near-maximal guarantee remains compatible with polynomial-time rejection sampling that can fix O(log λ) output bits.

    Source: §2.2 · p. 8

    The guarantee is n−ω(log λ), not uniform: polynomial-time rejection sampling can fix O(log λ) output bits.

    Source: §2.2 · p. 8

Abstract

from arXiv · show

The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed. We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung. We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.

1 Introduction

Trustless applications need verifiable randomness close to uniform, but deterministic verification makes the highest certifiable min-entropy a central question. The paper gives matching bounds and constructions for maximal min-entropy, including conditional guarantees and a randomness-beacon application.

1 Introduction

  • Existing proofs may certify only a weak source with rate o(1), while seeded extraction improves the rate only by assuming verifier-generated randomness.The paper requires a deterministic verifier to remove that trusted-randomness assumption.Source: §1 · pp. 1–2
  • n−ω(log λ) bits of min-entropy are achievable and maximal; deterministic verification cannot certify n−O(log λ) bits because rejection sampling can fix O(log λ) output bits.The optimal guarantee is therefore near-uniform in rate, but not uniform.Source: §1 · p. 2

1.1 Our Results

  • The maximal-min-entropy proof reuses ’s weak-source proof, then applies a compressing random oracle as a condenser to obtain an n-bit string with min-entropy ≥n−ω(log λ).The construction is in the QROM and adds no assumptions beyond those already used by.Source: §1.1 · pp. 2–3
  • The conditional-min-entropy proof certifies maximal entropy of X given adversarially chosen C and proof Π, using a compressing random oracle on C and a high-entropy source W.Its soundness uses the measure-and-reprogram technique.Source: §1.1 · p. 3

1.2 Application to Randomness Beacons

  • The beacon application certifies each pulse’s entropy conditioned on its label, which can encode the prior pulses and public transcript.The resulting security properties include bounded prediction before publication and union-bound analysis of attacks targeting a bad set.Source: §1.2 · pp. 3–4
  • The proposed beacon is seedless and can run on one untrusted quantum device, but it provides no liveness or entropy guarantee when rejecting proofs are published overwhelmingly often.A deployed beacon needs a separate liveness mechanism, such as an honest fallback prover or a rule selecting the first timely valid pulse.Source: §1.2 · pp. 3–4

1.3 Related Work

  • Unlike extractor approaches that restrict oracle-query behavior to obtain uniformity, this work allows unrestricted adversaries and accepts an n−ω(log λ) entropy guarantee.The paper notes that such adversary restrictions are not typically enforceable against malicious adversaries.Source: §1.3 · p. 6

2 Technical Overview

The section defines proofs of maximal conditional min-entropy, constructs one by compressing a high-min-entropy string with a random oracle, and outlines its soundness analysis across light, fixed-heavy, and adaptive-heavy queries. It describes oracle reprogramming and measure-and-reprogram techniques for adaptive queries, establishing conditional independence and bounding success after conditioning on the label.

2.1 Definition

  • For n = ω(log λ), the proof certifies conditional min-entropy at least n−γ(λ) for every γ(λ) = ω(log λ), even when an adversary chooses the label C and proof Π.The verifier derives X conditioned on C; this primitive is called a proof of maximal conditional min-entropy.Source: §2.1 · p. 7

2.2 Construction

  • The construction first uses MinEnt with oracle H to obtain W with min-entropy at least 4n, then outputs X = G(C, W) when verification accepts.The construction uses two oracles for convenience; the passage says they can be implemented with one random oracle over a larger domain.Source: §2.2 · p. 7
  • The work shows random-oracle seedless condensation achieves maximal min-entropy against quantum adversaries, unlike prior classical-adversary results.Ordinary and multisource extractor theorems do not cover sources and labels correlated with information from adaptive quantum queries to G; measure-and-reprogram [DFM20] motivates the proof intuition. The guarantee is n−γ bits of average conditional min-entropy, not uniform randomness, and is compatible with an attack fixing O(log λ) output bits.Source: §2.2 · pp. 7–8

2.3 Soundness Proof

  • The soundness proof begins under simplifying adversary constraints, including light queries to G and a fixed label, then removes two constraints in later cases.The overview places these relaxations across Sections 2.3.1–2.3.4.Source: §2.3 · p. 8

2.3.1 Case 1: Light Queries

  • For lightly queried inputs, reprogramming to G′ changes behavior insignificantly; the output is independent of G⁻¹(x), with expected mass 2⁻ⁿ and mass at most 2⁻ⁿ+O(log λ) with high probability over G.Source: §2.3.1 · p. 9

2.3.2 Case 2: Heavy queries on a fixed set

  • For a fixed set of heavily queried inputs, the proof keeps G and G′ identical on that set and independently samples their preimages on lightly queried inputs.The passage’s intuition is that the set is small enough for W’s min-entropy to make its probability mass negligible.Source: §2.3.2 · p. 12

2.3.3 Case 3: Heavy queries on an adaptive set

  • When the adversary chooses heavily queried inputs adaptively, the set can correlate with D(w), so the proof samples D, D′, and the set lazily.It waits to sample each D(w) until w is about to receive heavy query weight, then reprograms E0 as needed.Source: §2.3.3 · p. 12
  • Reprogramming before each heavy query preserves the adversary’s behavior with high probability, since earlier light query weight on changed inputs has little effect.The proof applies the swapping lemma after each query.Source: §2.3.3 · p. 13
  • Conditioned on (E0, ∆, D|∆), G′ is independent of D, allowing the security proof to proceed along the lines of Section 2.3.1.The conditioning variables are sampled before D(w) and D′(w) for w outside ∆.Source: §2.3.3 · p. 13

2.3.4 Case 4: Adaptive Labels

  • After making the selected slice independent of C, the proof reduces to Case 3, where lazy sampling handles adaptively chosen heavy sets and the earlier point-probability bound applies.The difficulty is that X and C may be correlated, so maximal H∞(X) alone does not rule out small Havg∞(X|C).Source: §2.3.4 · pp. 13–14
  • The block measure-and-reprogram lemma [DFM20] moves the adversary to an ideal world where it chooses C before querying G(C, ·), whose slice is freshly sampled as Θ.Θ is independent of both C and the simulator’s residual state, and the ideal-world simulator cannot do significantly worse on a specified success event.Source: §2.3.4 · pp. 13–14
  • Rare labels contribute only a small total probability mass that can be absorbed into the error term; non-rare labels satisfy the bound needed for the point-probability argument.The passage defines rare labels by a probability threshold and bounds their combined mass.Source: §2.3.4 · p. 14

3 Preliminaries

The preliminaries establish probability tools, the quantum random oracle model, and analysis tools for quantum oracle queries. They also define proofs of min-entropy and state a strong-soundness result for a construction.

3.1 Probability

  • The section introduces min-entropy and average conditional min-entropy, and states Hoeffding’s inequality for sums of bounded independent variables.It also explains notation for conditional entropy and probability.Source: §3.1 · pp. 14–15

3.2 Quantum Random Oracle Model

  • The QROM gives quantum algorithms coherent query access to a uniformly random function, including queries in superposition.Finite-domain oracles and multiple independent oracles can be represented using natural encodings.Source: §3.2 · p. 15

3.3 Oracle-Aided Quantum Algorithms

  • Query weight tracks an algorithm’s query probability at particular inputs, and the swapping lemma bounds state distance when the algorithm gives little weight to inputs where two oracles differ.The section introduces these tools for analyzing oracle-aided quantum algorithms.Source: §3.3 · pp. 15–16

3.4 Proof of Min-Entropy

  • A proof of min-entropy generates a string and certifies that it was produced by a procedure with high min-entropy.The definition requires correctness and strong soundness against quantum-query adversaries.Source: §3.4 · p. 17
  • Theorem 2 establishes a random-oracle proof of min-entropy with strong soundness by tightening the analysis of [CKM+26, Construction 6.4].The prior analysis established a weaker soundness condition.Source: §3.4 · p. 17

4.1 Definition

Definition 4 specifies a keyless, non-interactive, publicly verifiable proof of maximal conditional min-entropy relative to a random oracle. Its correctness and soundness requirements govern the output for a label and requested bitlength.

4.1 Definition

  • The prover takes a security parameter, output length, and label, and returns a classical proof; the verifier takes the same parameters and proof and returns an n-bit string or rejects.Both algorithms make polynomially many quantum-oracle queries, while verification is deterministic classical polynomial time.Source: §4.1 · p. 19
  • Correctness requires the protocol to satisfy its acceptance condition for every polynomially bounded output length and label.The definition states that the associated error is negligible.Source: §4.1 · p. 19
  • Soundness is required for output lengths n = ω(log λ), polynomially bounded labels and query budgets, and entropy loss γ(λ) = ω(log λ).The definition considers unbounded-time adversaries making polynomially many quantum queries and requires a negligible bound.Source: §4.1 · p. 19

4.2 Construction

The construction wraps an unlabelled proof of min-entropy with an outer random oracle keyed by the label. The resulting construction satisfies the syntax and correctness requirements for maximal conditional min-entropy.

4.2 Construction

  • Construction 1 instantiates the inner min-entropy proof at amplified parameters and uses independent inner and outer random oracles.The outer oracle maps a label and inner output to the requested output string; the two oracles can be implemented with one global oracle using domain separation.Source: §4.2 · p. 20
  • The verifier runs the inner verifier and, if it accepts, outputs the outer-oracle value indexed by the label and inner output.If the inner verifier rejects, the construction rejects as well.Source: §4.2 · p. 20
  • Theorem 3 establishes that the construction satisfies the syntax and correctness requirements of Definition 4.The outer verifier makes one additional classical query to the outer oracle.Source: §4.2 · p. 20

4.3 Proof of Soundness

This section proves Construction 1 satisfies the stated soundness property. Its proof uses a target-output completion procedure whose paired random functions retain uniform marginals.

4.3 Proof of Soundness

  • Construction 1 is shown to satisfy the soundness property of Definition 4.The section develops the proof through query-weight and completion arguments.Source: §4.3 · p. 20

4.3.1 Query normal form and query weights

  • The query-normal-form setup represents the adversary as making at most q quantum queries to a fresh random function, conditional on auxiliary information R.R may specify auxiliary oracles, classical side information, and an initial mixed state.Source: §4.3.1 · p. 21

4.3.2 The target-x completion procedure

  • The target-x completion procedure couples two functions, making them agree on noticeably queried inputs and resampling independently only on inputs that remain light.The procedure samples correlated functions G and G′ with uniform marginals.Source: §4.3.2 · p. 21

4.3.3 Uniformity of the completed functions

  • Each completed function G and G′ is uniformly random, conditional on every value of the auxiliary variable R.The proof establishes product Bernoulli-p distributions for the completion bits, with p = 2^-n.Source: §4.3.3 · pp. 22–23

4.3.4 Distance between the two completed executions

The section bounds the distance between the two completed executions by viewing the hybrid as a layer-dependent oracle and controlling query weight on inputs before exposure.

4.3.4 Distance between the two completed executions

  • The deterministic distance argument compares the hybrid execution with each completed-function execution and combines the two comparisons by the triangle inequality.The hybrid's time-dependent oracle sequence is represented as a single oracle on an enlarged domain indexed by query layer.Source: §4.3.4 · p. 24
  • Inputs entering a later exposed batch had query weight below the heavy-coordinate threshold at every earlier layer.The threshold stated in the proof is 2^-3n/q^2.Source: §4.3.4 · p. 25
  • A one-layer Hoeffding bound and a union bound yield a tail bound for the distance between the completed executions.The one-layer argument conditions on the history before the batch's Bernoulli variables are sampled.Source: §4.3.4 · pp. 25–26

4.3.5 Projection onto one output value

The section bounds projection onto a fixed output by separating heavy inputs from the remaining light inputs in the target-x completion.

4.3.5 Projection onto one output value

  • The completion procedure bounds the size of the heavy set, which supports the heavy-coordinate part of the projection argument.The proof sums the per-layer bound over disjoint exposed sets.Source: §4.3.5 · p. 27
  • The heavy-light projection bound controls the probability mass associated with a fixed output after conditioning on the light set, G′, and R.The proof bounds the heavy-set contribution even if every heavy point satisfies G(w) = x.Source: §4.3.5 · pp. 27–28
  • On light coordinates, the bits used by G are independent Bernoulli variables of mean 2^-n, even after conditioning on the light set, G′, and R.The proof applies Hoeffding’s inequality to bound their weighted contribution.Source: §4.3.5 · p. 28

4.3.6 A tail bound for one fixed output

The section first obtains a tail bound for one fixed output, then extends the argument to hashing after a label is fixed by handling rare labels separately from non-rare ones.

4.3.6 A tail bound for one fixed output

  • The fixed-output argument combines the completion coupling, distance and projection bounds, and a bound on the resulting bad events.The section concludes the fixed-output proof before moving to a labelled, two-stage setting.Source: §4.3.6 · p. 29

4.3.7 Hashing after the label is fixed

  • Joint point-flatness of (C, W) need not imply point-flatness of W conditioned on a rare label, so the proof bounds rare labels by their total probability mass.It applies the fixed-output lemma only to non-rare labels.Source: §4.3.7 · p. 29
  • The labelled construction places the first-stage label and residual state before sampling a fresh function Θ, which is independent of the first stage.The second stage then receives oracle access to Θ and outputs a proof.Source: §4.3.7 · p. 30
  • The section states a fresh-slice bound for the labelled construction using the min-entropy proof and verifier from Theorem 2.The cited corollary instantiates that verifier at Construction 1's parameters.Source: §4.3.7 · p. 33

4.3.8 Block Measure-and-Reprogram

The block measure-and-reprogram lemma handles an adversary that chooses C after quantum access to G by converting the execution into a two-stage form.

4.3.8 Block Measure-and-Reprogram

  • The construction addresses the case where the adversary chooses C only after quantum queries to the labelled oracle G.The earlier analysis assumed C was fixed before fresh Θ was sampled.Source: §4.3.8 · p. 35
  • The block measure-and-reprogram lemma converts this real execution into the required two-stage form.Source: §4.3.8 · p. 35
  • Reprogramming with Θ replaces the entire block {c} × W while leaving G unchanged outside that block.Source: §4.3.8 · p. 35

4.3.9 Oracle-query model and block projectors

The block-projector argument gives a two-stage simulator for quantum oracle access; the adaptive-selector hashing lemma then bounds its success and the probability of violations.

4.3.9 Oracle-query model and block projectors

  • Lemma 18’s simulator fixes a classical label C before receiving fresh Θ, then answers later queries using G0 reprogrammed on C × W.Source: §4.3.9 · p. 35
  • The proof adapts [DFM20] by replacing rank-one query and final-output projectors with block projectors, using oracle agreement on the relevant projector’s orthogonal complement.Source: §4.3.9 · pp. 35–36

4.3.10 The adaptive-selector labelled hashing lemma

  • Lemma 19 lower-bounds simulator success in terms of ρ, δ, u, and Q.Source: §4.3.10 · p. 37
  • Because C is selected before Θ is sampled, Corollary 1 applies, and the probability of a violation is bounded by ρ + 2κ(λ).Source: §4.3.10 · pp. 37–38

4.3.11 Putting everything together

Construction 1 satisfies the stated maximal conditional min-entropy soundness property, yielding an accepted output with near-optimal conditional min-entropy given the adaptive label, except with negligible probability under the stated acceptance condition.

4.3.11 Putting everything together

  • Theorem 4 states that Construction 1 satisfies the soundness property in Definition 4.Source: §4.3.11 · p. 38
  • The proof notes that when γ > n, the entropy event is empty.Source: §4.3.11 · p. 38
  • For every γ(λ) = ω(log λ), accepted output has average conditional min-entropy greater than n − γ(λ) given the adaptive label, except with negligible probability when acceptance has inverse-polynomial probability.Source: §4.3.11 · p. 39
Loading 2609.38945v1…