A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device

Model and contributions

• A classical verifier interacting with one polynomial-time quantum device can efficiently test whether it is genuinely quantum and generate certifiably random strings.This model replaces quantum-message or multi-device assumptions with post-quantum cryptographic primitives executable by the verifier.Source: §1 · p. 3

Qubit certification

• The qubit certification protocol uses post-quantum secure trapdoor claw-free functions whose trapdoor lets the verifier recover hidden preimages and enforce a qubit state.The prover can hold two claw preimages in superposition, while standard- versus Hadamard-basis challenges distinguish quantum behavior from classically reproducible sampling.Source: §1 · pp. 3–4

Adaptive hardcore bit

• The security proof requires an adaptive hardcore bit property: even after seeing the LWE sample and image, an efficient device cannot produce a preimage and a correlated bit of the claw difference.The protocol uses rewinding against classical devices, whereas quantum measurement collapse prevents the same device from answering both challenges; verifier checks constrain valid adaptive choices.Source: §1 · pp. 4, 5, 7

LWE construction

• LWE yields noisy trapdoor claw-free functions, and leakage-resilience plus a Fourier-analytic argument preserves the unpredictability of adaptive binary inner products with the secret.The construction exploits the mismatch between arithmetic modulo q and binary XOR/modulo-2 inner products to retain entropy even when the choice depends on the LWE sample.Source: §1 · pp. 5–6

Quantum supremacy

• The resulting proof of quantumness is classically verifiable in polynomial time and is robust to devices that answer challenges successfully with a sufficiently large constant probability.The introduction estimates that 50-bit security may require about 2000 qubits under off-the-shelf LWE bounds, while noting near-term implementation challenges.Source: §1 · p. 7

Certifiable randomness

• The randomness protocol characterizes successful devices as measuring |+⟩ qubits, yielding nearly one bit of information-theoretic randomness per single-round test and extending this guarantee across refreshed multi-round epochs.Random equation tests and refreshed pseudorandom keys prevent reuse attacks, while the full analysis must handle entanglement with an arbitrarily powerful adversary.Source: §1 · pp. 7–9

• The protocol can generate O(N) nearly uniform bits from poly log(N) randomness for the constructed LWE-based NTCF, under sub-exponential quantum hardness assumptions.Under the more conservative polynomial-size quantum hardness assumption, generating NTCF instances requires O(N^ε) random bits for any constant ε > 0.Source: §1 · p. 9
• For N = Ω(λ^2), the informal theorem gives an N-round protocol executable with poly(log(N), λ) random bits under quantum-hard lattice assumptions.The theorem applies to efficient devices and side information correlated with the device’s initial state, on accepted transcripts.Source: §1 · p. 9
• The protocol uses an NTCF family to interact for N rounds with a quantum device, testing preimages and equations before extracting randomness from recorded preimages.The verifier privately retains trapdoor information, issues only poly log(N) equation challenges, and applies a quantum-proof extractor to the remaining recorded bits.Source: §1 · pp. 9–10
• The analysis obtains a linear lower bound on conditional Rényi entropy across N rounds, translating into Ω(N) smoothed min-entropy for N − poly log(N) recorded bits, conditioned on quantum side information and leaked challenges.A quantum-proof randomness extractor then produces bits statistically close to uniform using poly-logarithmically many additional random bits.Source: §1 · pp. 10–11
• The analysis must address that computational soundness can make conditioning induce inefficient device states, unlike prior entropy-accumulation settings [MS14].The proof handles this by decomposing the device into good and bad subspaces and bounding repeated bad-subspace branches through interference-aware martingale reasoning.Source: §1 · pp. 10–11
• Subsequent work used NTCFs for quantum fully homomorphic encryption [Mah17], prescribed-basis measurement certification [Mah18], and remote state preparation [GV19].The paper emphasizes NTCFs as a potentially powerful tool for constraining untrusted quantum devices.Source: §1 · p. 11

2.1 Notation

• The paper fixes notation for modular integers, polynomially bounded and negligible functions, finite-dimensional Hilbert spaces, positive operators, density matrices, and operator and trace norms.Source: §2.1 · p. 12

2.2 Distributions

• It defines distributions, supports, Hellinger and total variation distances, and computational indistinguishability for both distributions and sub-normalized quantum states under efficient quantum tests.Source: §2.2 · pp. 12–13

2.3 The Learning with Errors problem

• LWE is defined as distinguishing noisy linear samples from uniform ones, under a quantum polynomial-time hardness assumption that remains secure with quantum polynomial-size advice; the section also records trapdoor inversion and lossy-mode properties.The trapdoor sampler enables recovery of the secret and error for bounded noise, while lossy samples are computationally indistinguishable from uniform under the LWE assumption.Source: §2.3 · p. 15

2.4 Entropies

• The paper introduces classical and quantum Rényi entropies, min-entropy, and smooth min-entropy, using Rényi entropies because their chain-rule-like properties support the proofs.A theorem relates Rényi and min-entropies up to smoothing, connecting the proof-oriented measures with randomness quantification.Source: §2.4 · pp. 15–16

Ideal functionality

• An ideal family provides two injective, same-range functions with trapdoor inversion, claw-freeness, and an adaptive hardcore bit property.The hardcore condition prevents quantum attackers from producing a valid preimage choice and nonzero string correlated with the xor of matching preimages.Source: §3 · p. 17

Noisy relaxation

• The LWE-based construction relaxes point-valued outputs to probability densities whose supports coincide for matching pairs and are disjoint otherwise.This noisy formulation is intended to retain the properties needed by the protocols despite not exactly satisfying the ideal requirements.Source: §3 · p. 17

Efficient range superposition

• Efficient range superposition requires approximately preparable output states, trapdoor inversion of both matched preimages, and trapdoor-free support checking.The LWE instantiation achieves only negligible-distance approximation to the ideal superposition, while requiring correct inversion throughout the relevant support.Source: §3 · p. 17

Adaptive hardcore bit

• The adaptive hardcore bit definition uses an efficiently invertible injection J into binary strings and trapdoor-checkable good-string sets covering all but negligible probability.It restricts the hardcore guarantee to an efficiently recognizable subset of nonzero strings while preserving quantum computational indistinguishability of the relevant bit relation.Source: §3 · pp. 17–18

Formal definition

• NTCF families require efficient key-and-trapdoor generation, trapdoor inversion on supported outputs, and a perfect matching characterizing all cross-branch collisions.The injective-pair condition also ensures distinct inputs within each branch have disjoint output supports.Source: §3 · pp. 17–18

Construction and security

• FLWE is defined from keys k = (A, As + e) and densities f_k,b over X, with the key uniquely identifying s for the chosen parameters.The construction specifies the function family after fixing parameters satisfying conditions (A.1)–(A.4).Source: §4 · p. 19
• Theorem 4.1 establishes that FLWE is a noisy trapdoor claw-free family for parameters satisfying (A.1)–(A.4), assuming LWE_ℓ,q,D hardness.The proof verifies the four properties required by the noisy trapdoor claw-free family definition.Source: §4 · p. 19

Parameter choices

• Parameter selection can target 2^-λ statistical security by setting B_P/B_L = 2^λ, while choosing ℓ ≈ λ^2 yields exponential LWE hardness in the suggested regime.The resulting q satisfies q = 2^(2λ/poly(λ)), and the hardness estimate depends on ℓ/log(q/B_L).Source: §4 · p. 19
• Alternative parameters can improve efficiency by lowering the statistical-security target, but the suggested setting assumes hardness of sub-exponential lattice approximation.The authors note that q/B_L scales sub-exponentially with ℓ and may instead be chosen more moderately to avoid that assumption.Source: §4 · p. 19

Efficient Function Generation

• GENFLWE uses GENTRAP(1_n, 1_m, q) to sample A ∈ Z_q^{m×n} with trapdoor t_A, requiring m = Ω(n log q).The matrix distribution produced by GENTRAP is negligibly close to the target distribution.Source: §4.1 · p. 20
• Given A, t_A, and b = As + e, INVERT recovers s and e when the supplied norm bound on e holds.The inversion guarantee is enabled by the trapdoor generated for A.Source: §4.1 · p. 20
• The procedure samples s uniformly from {0,1}^n and samples each coordinate of e independently from D_Zq,BV.GENFLWE returns k = (A, As + e) together with t_k = t_A.Source: §4.1 · p. 20

(a) Trapdoor

• The INVFLWE procedure uses the trapdoor to recover s0 and e0, then returns s0 − b · s as the unique correct outcome when the error-norm condition holds; this condition is ensured for all supported outputs by the parameter choice in (A.3).The procedure takes tA, b, and y, applies INVERT to obtain s0 and e0 satisfying y = As0 + e0, and uses Theorem 2.6 for correctness.Source: §4.2 · p. 20

(b) Injective Pair

• The relation Rk of colliding input pairs satisfies x1 = x0 − s, so Rk is a perfect matching.Rk consists of pairs (x0, x1) with fk,0(x0) = fk,1(x1).Source: §4.2 · p. 20

Efficient Range Superposition

• The strengthened trapdoor requirement guarantees that INVFLWE returns x for both input bits under the stated norm bound.Using BV < BP bounds the relevant error term by 2BP, and the strengthened requirement remains satisfied by (A.3).Source: §4.3 · pp. 20–21
• CHKFLWE verifies a candidate y by computing the residual relative to Ax for b = 0 or Ax + (As + e) for b = 1, accepting when its norm is at most BP_m.The procedure returns 1 exactly when the corresponding residual satisfies the threshold.Source: §4.3 · p. 21
• The Hellinger distance between f_k,b(x) and f′_k,b(x) is negligible: the densities coincide for b = 0, while for b = 1 their shifts differ by e.Each coordinate of e is independently drawn from D_mBV, and the conclusion follows when BP/BV is super-polynomial as required by Assumption (A.4).Source: §4.3 · p. 21
• SAMPFLWE prepares the required state efficiently by first creating the specified superposition, then a uniform superposition over x ∈ X, computing with k and b, and uncomputing e0.The first state can be prepared efficiently as described in [Reg09, Lemma 3.12], using a technique by Grover and Rudolph ([GR02]).Source: §4.3 · p. 21

4.4 Adaptive Hardcore Bit

• The construction satisfies condition 4.(a) because membership in Gk,b,x is efficiently checkable and a uniformly sampled d lies outside it except with negligible probability.This follows from injectivity of J, which makes J(x) ⊕ J(x − (−1)^b1) nonzero.Source: §4.4 · p. 22

Then for any quantum polynomial-time procedure

• Under LWE and the stated parameter conditions, the two distributions differing by the adaptive hardcore bit are computationally indistinguishable for every quantum polynomial-time procedure.Lemma 4.4 establishes indistinguishability between Ib,x(d) · s mod 2 and its masked version (δd∈ˆGsb⊕1,b,xr) ⊕ (Ib,x(d) · s mod 2).Source: Then for any quantum polynomial-time… · p. 23

4.4.1 Proof of Lemma 4.3 from Lemma 4.4

• The adaptive hardcore-bit proof defines Ib,x so that the original inner product equals Ib,x(d) · s mod 2, with Ib,x efficiently computable from b, x, and d.Claim 4.5 supplies the equality used to transfer Lemma 4.4 to Lemma 4.3.Source: §4.4.1 · p. 23

4.4.2 A Building block: Moderate matrices

• With probability at least 1 − q^ℓ·2^-n, a uniformly random matrix is moderate, and conditioned on Cs = v, any nonzero adaptive parity of uniform s is close to uniform.The moderate-matrix lemmas provide the statistical foundation for handling vectors chosen after observing C and Cs.Source: §4.4.2 · pp. 24, 26

4.4.3 Proof of Lemma 4.4

• The hybrid proof replaces the LWE matrix with a lossy matrix, removes Fs with negligible statistical error, and then uses the moderate-matrix lemma to replace the adaptive parity by a uniform bit.The final replacement applies when the relevant n/2-bit block of Ib,x(d) is nonzero, as guaranteed for d in the designated set.Source: §4.4.3 · pp. 26–27
• The proof reinserts the term F_s and concludes statistical indistinguishability between D^(3) and D^(4), as well as computational indistinguishability between D^(4) and D_1.Both conclusions are obtained by analogous arguments to earlier hybrid transitions.Source: §4.4.3 · p. 27

5 Protocol description

• Protocol 1 aims to ensure that every computationally bounded prover accepted with non-negligible probability produces transcripts containing information-theoretic randomness.The verifier interacts with an untrusted prover in the main randomness-expansion protocol.Source: §5 · p. 27

5.2 The simplified protocol

• Protocol 2 simplifies prover answers and verifier checks, adds a good-subspace measurement challenge, and serves only as an analysis tool rather than a literal executable protocol.Its simplified responses encode validity directly, but arbitrary provers can succeed; the analysis restricts attention to provers satisfying constraints derived from Protocol 1.Source: §5 · p. 27, §5.2 · pp. 28, 30

5.1 The randomness expansion protocol

• Protocol 1 uses security parameter λ, N rounds, error tolerance γ, and testing probability q, with q scaling as poly(λ)/N.The verifier generates an NTCF public key and private trapdoor, while test rounds occur with probability q and generation rounds with probability 1 − q; the prover is not told the round type.Source: §5.1 · pp. 27–28
• The verifier challenges test rounds uniformly and generation rounds with C = 1, accepts valid responses, aborts below a 1 − γ test success fraction, and outputs generation-round bits.After each test round, the verifier refreshes the NTCF key and communicates the new public key.Source: §5.1 · p. 28

5.3 Completeness

• The honest prover for Protocol 1 is polynomial-time and accepted with probability negligibly close to 1 in each round.It prepares the NTCF superposition, measures to obtain y, and responds through Hadamard-basis or computational-basis measurements depending on the challenge; failure occurs only with negligible probability.Source: §5.3 · pp. 30–31

6.1 General devices

• A general device D = (φ, Π, M) consists of an initial state, challenge-dependent projective measurements, and designated accepting pre-images for generation challenges.The state is defined on private registers, while measurements produce equation or pre-image outcomes indexed by y.Source: §6.1 · p. 32
• An efficient general device prepares its state and implements both measurement families using uniformly generated polynomial-size quantum circuits.The honest prover’s associated device satisfies this efficiency definition.Source: §6.1 · p. 32
• General-device executions are represented by transcripts of round types, challenges, and verifier outputs, together with transcript-conditioned post-measurement states and an accepting set.The transcript retains information relevant to verification and randomness extraction before the verifier decides whether to abort.Source: §6.1 · pp. 32–33

6.2 Simplified devices

• A simplified device augments state and measurement operators with commuting operators K_y, enabling a model for Protocol 2 while allowing M_y and Π_y to remain noncommuting.Its overlap quantifies measurement incompatibility within the designated good subspace.Source: §6.2 · p. 33
• Simplified-device executions sample y according to Tr(φ_y), apply the challenge-dependent projective measurement, and track transcript-conditioned post-measurement states across rounds.The verifier’s sampling probability factors as q(g,c,t)=q(g,c)κ(t).Source: §6.2 · pp. 33–34

7.1 A constraint on the measurements of any efficient device

• Any efficient device’s pre-image and equation measurements produce computationally indistinguishable states for correct and incorrect equations, or else the hardcore-bit property is violated.This establishes strong incompatibility between the measurements used by the device.Source: §7.1 · p. 34

7.2 Angles between incompatible measurements

• A principal-angle lemma bounds the contribution of measurement blocks near overlap one, with additional error controlled by the probability that the state lies outside the measured subspace.The proof uses Jordan’s lemma and, when the state is not fully supported on the measured subspace, the gentle measurement lemma.Source: §7.2 · p. 35, Let 1 · p. 36

7.3 Simulating an efficient device using a simplified device

• For every efficient device, the construction gives a simplified device that simulates it while its measurements generally have angles bounded away from one.The construction applies the angle lemma to define the projection K and relies on the measurement constraint from Lemma 7.1.Source: §7.3 · pp. 36–37
• Simulation preserves the post-measurement states in every round, because the simplified device can locally obtain the same equations or pre-images as the original device.The overlap property follows from the chosen projection, while the remaining condition uses computational indistinguishability of the states from Lemma 7.1.Source: §7.3 · p. 37

8 Accumulating randomness across multiple rounds

• The section analyzes randomness in three stages: reduction to the simplified device, single-round randomness generation, and accumulation across multiple rounds.The simplified protocol serves as the intermediate object connecting the original protocol to the multi-round randomness analysis.Source: §8 · p. 38

8.1 Reduction to the simplified protocol

• The auxiliary projective measurement {K0, K1} detects whether the device state lies in the good subspace, but is conceptual and not performed in the real protocol.In test rounds it is included in the simplified protocol to facilitate the analysis of randomness generation.Source: §8.1 · p. 38
• The reduction shows that, for most test rounds, the original device’s state lies largely in the good subspace, allowing its randomness analysis to be related to that of the simplified protocol.The proof controls bad-subspace outcomes despite possible interference between branches using a general probabilistic lemma and martingale tail bounds.Source: §8.1 · pp. 38, 39, 40, 44

8.2 Randomness accumulation in the simplified protocol

• If the simplified device’s overlap Δ(D) is bounded away from 1 and its state has high overlap with M1, measuring {Π0, Π1, Π2} necessarily perturbs the state and generates randomness.The argument uses a measurement-disturbance trade-off based on uniform convexity of suitable matrix p-norms.Source: §8.2 · p. 45
• The resulting multi-round proposition quantifies randomness in the accepted transcript of Protocol 2 by combining single-round disturbance across generation and test cases.The bound is conditioned on the verifier not aborting, namely on (g, c, t, o, k) ∈ ACC2.Source: §8.2 · p. 46
• In the simplified protocol, an inequality is chained across N rounds while updating the density each round and using the ACC2 frequency condition on accepted sequences.The parameter choice is completed by selecting r = (1 − γ/κ − η).Source: §8.2 · p. 47

8.3 Randomness accumulation in the general protocol

• Proposition 8.12 combines the preceding analyses to establish a general-protocol bound with δ′ = 2^−Ω(κqN), using an elementary-device reduction and entropy smoothing.The proof controls omitted transcript sequences through a Chernoff-bound error and extends the bound to the full state with an additional smoothing cost.Source: §8.3 · pp. 47–48
• Theorem 8.13 gives an exponentially small error δ = 2^−Ω(qN) for Protocol 1 when N = Ω(λ^2) and q = λ/N, for any efficient prover with correlated side information.The theorem applies to an NTCF family and sets the protocol parameters η, γ, and κ appropriately.Source: §8.3 · p. 49
• With GEN(1^λ) using O(λ^r) random bits, the protocol requires poly(λ, log N) verifier randomness; for N slightly sub-exponential in λ, this yields sub-exponential randomness expansion.For the LWE-based NTCF construction, r = 2.Source: §8.3 · p. 49