Source-linked AI summary
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, Thomas Vidick
TL;DR
The paper asks whether a classical verifier can test and extract randomness from a single untrusted quantum device without quantum communication or multiple entangled devices. It develops post-quantum trapdoor claw-free functions with an adaptive hardcore bit property, constructs them from LWE, and uses them for qubit certification and certifiable randomness. The protocols characterize the device's behavior and can generate statistically near-uniform output under stated cryptographic assumptions.
Problem
Existing approaches to testing and randomness certification rely on quantum verifier capabilities, multiple entangled devices, or exponential-time classical verification rather than a single-device classical-verifier model.
Method
The paper uses post-quantum noisy trapdoor claw-free functions with an adaptive hardcore bit property, constructs them from LWE, and uses them to constrain the device's state and measurements.
Results
The protocols provide classical polynomial-time verification of quantumness and certifiable randomness, with the output characterized as statistically close to uniform under the stated assumptions.
Takeaways & Limitations
A single efficient quantum device can support cryptographic tests of quantumness and information-theoretic randomness certification when it cannot break the underlying post-quantum cryptography.
Takeaways & Limitations
The approach requires efficient trapdoor-free validity testing and some fault tolerance; its robustness assumes the device answers challenges with a sufficiently large constant success probability.
Abstract
from arXiv · showhide
We consider a new model for the testing of untrusted quantum devices, consisting of a single polynomial-time bounded quantum device interacting with a classical polynomial-time verifier. In this model we propose solutions to two tasks - a protocol for efficient classical verification that the untrusted device is "truly quantum," and a protocol for producing certifiable randomness from a single untrusted quantum device. Our solution relies on the existence of a new cryptographic primitive for constraining the power of an untrusted quantum device: post-quantum secure trapdoor claw-free functions which must satisfy an adaptive hardcore bit property. We show how to construct this primitive based on the hardness of the learning with errors (LWE) problem.
1 Introduction
The paper introduces a single-device model in which a classical polynomial-time verifier tests quantumness and certifies randomness using post-quantum trapdoor claw-free functions with an adaptive hardcore bit property. It constructs the needed primitive from LWE and analyzes its use for qubit certification and statistically random output.
- Model: The model uses a purely classical verifier interacting with a single polynomial-time quantum machine, enabling post-quantum cryptographic techniques.The device's efficiency permits reliance on primitives implementable classically but secure against efficient quantum algorithms.
- Goals: The protocols address efficient classical verification of quantumness and certifiable randomness from one untrusted quantum device.The qubit certification test is contrasted with earlier approaches requiring exponential classical verification or multiple entangled devices.
- Cryptographic primitive: The construction uses noisy trapdoor claw-free functions, whose adaptive hardcore bit property prevents producing a preimage together with a chosen equation about the claw.The chosen string may depend on the function and its image, making the property adaptive.
- Cryptographic primitive: LWE leakage resilience and a Fourier-analytic argument support security even when the device adaptively selects a binary inner product after observing an LWE sample.The argument exploits the difference between binary inner products and samples over Z_q to retain entropy in the secret.
- Limitations: The proposal remains bounded by efficient trapdoor-free validity checks and near-term fault-tolerance requirements, although robustness allows a sufficiently large constant success probability.The adaptive hardcore bit proof requires testing the validity of d′ without the trapdoor, while practical use requires some fault tolerance.
- Certifiable randomness: The randomness analysis characterizes the device as measuring a |+⟩ qubit in standard or Hadamard bases, yielding output containing close to one bit of true randomness.This characterization is obtained up to a global change of basis and connects cryptographic security to information-theoretic randomness.
2 Preliminaries
This section introduces notation, computational indistinguishability, LWE, trapdoors, lossy sampling, and entropy measures used in the paper.
- Notation: The paper defines standard notation for integers, distributions, densities, distances, quantum states, operators, and polynomially bounded or negligible functions.
- Indistinguishability: Computational indistinguishability is defined for both distributions and sub-normalized quantum states against polynomial-time quantum procedures or observables.
- Learning with Errors: LWE asks whether noisy linear samples (A, As + e mod q) can be distinguished from uniform samples, under a quantum-hardness assumption allowing quantum advice.
- LWE tools: LWE additionally supports efficient trapdoor generation and inversion, while a lossy sampler produces matrices computationally indistinguishable from uniform under the LWE assumption.
- Entropy: The paper introduces conditional Rényi, min-entropy, and smooth min-entropy, using Rényi entropies because they have stronger chain-rule-like properties for proofs.
3 Trapdoor claw-free hash functions
This section defines noisy trapdoor claw-free functions and explains how relaxed, density-valued requirements support the paper’s quantum protocols.
- Core properties: A trapdoor claw-free pair consists of injective functions with a common range, efficiently invertible with a trapdoor but hard to find colliding preimages without it.
- Adaptive hardcore bit: The adaptive hardcore bit property hides the inner product d · (J(x0) ⊕ J(x1)) for randomly selected admissible d, even when one preimage is known.
- LWE-based relaxation: The construction relaxes ideal requirements by letting functions return probability densities whose supports coincide for claws and are disjoint otherwise.
- LWE-based relaxation: For the LWE instantiation, the required range superposition is prepared only approximately, within negligible trace distance, while support membership and inversion remain efficient.
- Operational requirements: The function family includes matching preimages, efficient range-superposition preparation, support checking, and trapdoor inversion on supported outputs.
4 A Trapdoor Claw-Free family based on LWE
The section constructs an LWE-based noisy trapdoor claw-free family and states that it satisfies the required properties under an LWE hardness assumption. It also discusses parameter choices balancing statistical security, computational hardness, and efficiency.
- Parameter conditions: The construction requires B_L < B_V < B_P, with both ratios B_P/B_V and B_P/B_L super-polynomial in λ.These parameter relationships are part of condition (A.4).
- Construction and security: FLWE uses keys k = (A, As + e), with domains X = Z_q^n and densities defined for both function branches.The key uniquely identifies s for the chosen parameters, making the branch densities well-defined.
- Construction and security: The family FLWE is a noisy trapdoor claw-free family under the hardness assumption LWEℓ,q,D.This holds for parameters satisfying conditions (A.1)–(A.4).
- Parameter conditions: Choosing ℓ ≈ λ^2 yields exponential LWE hardness when log(q/B_L) = O(λ), while larger statistical-security parameters can reduce efficiency.The suggested setting targets 2^-λ statistical security but may impose stronger lattice-hardness assumptions.
4.1 Efficient Function Generation
Function generation samples a trapdoor-equipped matrix, a binary secret, and an error vector, then publishes an LWE sample while retaining the matrix trapdoor.
- Key generation: GENFLWE samples A ∈ Z_q^(m×n) with trapdoor information t_A using GENTRAP.The trapdoor supports inversion for sufficiently small error vectors.
- Key generation: GENFLWE samples a uniform binary secret s ∈ {0,1}^n and an error vector e from the distribution D_Zq,BV.The error coordinates are sampled independently.
- Key generation: GENFLWE returns the public key k = (A, As + e) and trapdoor t_k = t_A.The public component is an LWE sample, while the trapdoor remains available for inversion.
4.2 Trapdoor Injective Pair
The trapdoor enables inversion of outputs, and the two function branches form an injective pair whose matching inputs differ by the secret s.
- Injective pair: The trapdoor and injective-pair properties establish the branch structure required for the claw-free construction.The supplied proof section verifies these properties through inversion and the matching relation.
- Trapdoor inversion: The inversion procedure uses t_A to recover s_0 and e_0 from y = As_0 + e_0, then returns s_0 − b·s.Correct inversion is guaranteed when the error norm is within the trapdoor bound.
- Injective pair: The matching relation f_k,0(x_0) = f_k,1(x_1) holds exactly when x_1 = x_0 − s.Thus the relation set R_k is a perfect matching.
4.3 Efficient Range Superposition
The construction supports efficient evaluation and range-superposition sampling while controlling the statistical distance between noisy branch distributions. Trapdoor inversion remains valid under strengthened error bounds.
- Efficient inversion: The strengthened bound on B_P ensures INVFLWE recovers x on inputs from the relevant output support.The bound follows from controlling the norm of e_0 + e by 2B_P.
- Efficient evaluation: CHKFLWE checks whether y is within B_P of Ax for b = 0 or of Ax + (As + e) for b = 1.It returns 1 exactly when the corresponding residual norm passes the threshold.
- Distribution closeness: The two branch densities differ by an error shift, and their Hellinger distance is negligible when B_P/B_V is super-polynomial.For b = 0 the densities are identical; for b = 1 their shifts differ by e.
- Range superposition: SAMPFLWE prepares a uniform superposition over x and computes the noisy branch output, then uncomputes the auxiliary error register.The required Gaussian-like superposition can be prepared efficiently using standard sampling techniques.
4.4 Adaptive Hardcore Bit
The section establishes the adaptive hardcore bit property by reducing adaptive parity prediction to computational indistinguishability under LWE. Moderate matrices provide the statistical building block needed to show that secret parities remain hidden even after adaptive choices.
- LWE reduction: The central difficulty is that the adversary chooses d′ after seeing the LWE sample As + e, unlike standard leakage-resilience statements with independently chosen leakage.The proof therefore needs adaptive leakage resilience rather than ordinary hardcore-bit security.
- Conclusion: The proof combines the moderate-matrix parity lemma with LWE indistinguishability to establish the computational indistinguishability required by the adaptive hardcore property.Lemma 4.3 is obtained by relating the protocol’s inner product to an efficiently computable parity of s and applying Lemma 4.4.
- Adaptive hardcore bit: The proof restricts the secret s to binary form and rewrites the relevant XOR inner product as d′ · s, so predicting any such bit reveals a secret parity.The reduction uses an efficiently computable map I_b,x from d to d′.
5 Protocol description
The paper presents a multi-round randomness expansion protocol in which a classical verifier alternates infrequent tests with generation rounds using an NTCF key and trapdoor. An analysis-only simplified protocol captures the proof structure, while the intended honest prover is efficient and accepted with probability negligibly close to one.
- Protocol 2: Protocol 2 simplifies prover answers and checks and adds a good-subspace challenge, serving as an analysis tool rather than a protocol intended for literal execution.Its simplified outputs directly encode verifier decisions and valid-preimage cases.
- Protocol 1: Protocol 1 uses N rounds, a test probability q, and an acceptance threshold 1 − γ; accepted executions output the prover’s generation-round bits.The parameter q is intended to scale as poly(λ)/N, making test rounds less frequent than generation rounds.
- Protocol 1: The verifier generates an NTCF public key and private trapdoor, sends the key to the prover, and uses the trapdoor to invert each reported image y.A fresh key is sampled after every test round.
- Protocol 1: Test rounds challenge the prover for an equation response, whereas generation rounds request a candidate preimage and record its bit as output.The equation response is checked against the claw relation and a designated valid set.
- Honest prover: The honest prover can be implemented in polynomial time and is accepted with probability negligibly close to 1 for a randomly generated NTCF key.Failure occurs only when the sampled d falls outside the designated set, which happens with negligible probability.
6 Devices
The paper models arbitrary provers as quantum devices with states and challenge-dependent measurements, then introduces simplified devices for analyzing the protocol. The simplified model isolates good-subspace measurement compatibility and quantifies incompatibility through overlap.
- General devices: A general device consists of an initial state and, for each image y, projective measurements for equation responses and candidate preimages.The accepted preimage outcomes are the two designated claw preimages associated with y.
- General devices: The device model reproduces Protocol 1 by measuring the y register first and then selecting the equation or preimage measurement according to the verifier’s challenge.The device’s post-measurement states are conditioned on the complete transcript and verifier outcomes.
- Efficiency: Efficiency requires polynomial-size circuits to prepare the state and implement both measurement families, and the honest prover’s associated device satisfies these requirements.The projectivity assumption is without loss of generality by Naimark’s theorem.
- Simplified devices: A simplified device replaces the full protocol responses with operators for the equation, preimage, and good-subspace tests, while requiring the good-subspace operators to commute with the other measurements.The equation and preimage measurements need not commute with each other.
- Overlap: The overlap quantity measures incompatibility between the simplified device’s measurements within the good subspace and supports the later randomness analysis.The construction also tracks transcript-conditioned post-measurement states across rounds.
7 Single-round analysis
The single-round analysis reduces an efficient device to a simplified device whose measurements retain the original behavior while satisfying a bounded-overlap condition derived from the adaptive hardcore-bit property.
- Measurement incompatibility: Computational indistinguishability of σ0 and σ1 prevents an efficient device from reliably distinguishing correct from wrong equations after a preimage measurement.This follows from the adaptive hardcore-bit property, since such a distinction would yield a valid preimage together with a correct equation.
- Overlap bound: The simplified device’s overlap is bounded for advice states independent of the key, with the bound controlled by a constant depending only on ω.This is the structural property later used to analyze randomness generation in the simplified protocol.
- Simulation: The simplified device simulates the original device, preserving the relevant post-measurement states and transcript behavior.Simulation is defined by equality of the corresponding post-measurement states, and the construction permits local recovery of the original equations or preimages.
- Simplified-device construction: The analysis constructs a simplified device by embedding the equation measurement into a larger space and adding a projection onto a suitable good subspace.The construction uses an isometry Uy and a projection Ky obtained from the principal-angle analysis of the two measurements.
8 Accumulating randomness across multiple rounds
The multi-round analysis transfers randomness guarantees from the simplified protocol to the general protocol using good-subspace control, martingale concentration, and entropy accumulation across accepted rounds.
- Reduction: The analysis first relates randomness from the original protocol to that of its associated simplified device, then analyzes randomness produced in a single simplified-protocol round.The simplified device sometimes adds a projective good-subspace measurement in test rounds.
- Concentration: The proof controls the frequency of bad-subspace outcomes across rounds by combining conditional-expectation arguments with Azuma’s and Prohorov-type martingale bounds.The target is to show that most test rounds lie largely in the good subspace K = K0.
- General protocol guarantee: With q = λ/N and N = Ω(λ2), the main theorem gives an exponentially small error term δ = 2^-Ω(qN) for efficient provers and correlated side information.The accepted output state is analyzed jointly with the verifier’s challenges and the adversary’s system.
- Randomness expansion: Using N slightly sub-exponential in λ yields sub-exponential randomness expansion while the verifier uses only poly(λ, log N) random bits.This efficiency statement assumes key generation uses O(λ^r) random bits.