Source-linked AI summary
Experimentally Generated Randomness Certified by the Impossibility of Superluminal Signals
Peter Bierhorst, Emanuel Knill, Scott Glancy, Yanbao Zhang, Alan Mink, Stephen Jordan, Andrea Rommal, Yi-Kai Liu, Bradley Christensen, Sae Woo Nam, Martin J. Stevens, Lynden K. Shalm
TL;DR
The paper addresses how to certify unpredictable physical randomness without relying on detailed device models. It uses a loophole-free photonic Bell test with a new protocol optimized for low per-trial violations, extracting 1024 bits uniform within 10^-12. The result supports device-independent randomness generation under independent-setting and non-signaling assumptions, while requiring substantial uniform randomness for settings and a seed.
Problem
Physical random-number generators require detailed assumptions about their underlying physics, making it difficult to establish that outputs are unpredictable.
Method
The paper combines a loophole-free photonic Bell test with a two-stage entropy-production and extraction protocol using a customized Trevisan-based TMPS extractor.
Results
1024 bits were extracted and certified uniform within 10^-12 after the Bell-test protocol passed.
Takeaways & Limitations
Loophole-free Bell-test generators can provide device-independent certified randomness that may increase trust in random sources and cryptographic infrastructure.
Abstract
from arXiv · showhide
From dice to modern complex circuits, there have been many attempts to build increasingly better devices to generate random numbers. Today, randomness is fundamental to security and cryptographic systems, as well as safeguarding privacy. A key challenge with random number generators is that it is hard to ensure that their outputs are unpredictable. For a random number generator based on a physical process, such as a noisy classical system or an elementary quantum measurement, a detailed model describing the underlying physics is required to assert unpredictability. Such a model must make a number of assumptions that may not be valid, thereby compromising the integrity of the device. However, it is possible to exploit the phenomenon of quantum nonlocality with a loophole-free Bell test to build a random number generator that can produce output that is unpredictable to any adversary limited only by general physical principles. With recent technological developments, it is now possible to carry out such a loophole-free Bell test. Here we present certified randomness obtained from a photonic Bell experiment and extract 1024 random bits uniform to within $10^{-12}$. These random bits could not have been predicted within any physical theory that prohibits superluminal signaling and allows one to make independent measurement choices. To certify and quantify the randomness, we describe a new protocol that is optimized for apparatuses characterized by a low per-trial violation of Bell inequalities. We thus enlisted an experimental result that fundamentally challenges the notion of determinism to build a system that can increase trust in random sources. In the future, random number generators based on loophole-free Bell tests may play a role in increasing the security and trust of our cryptographic systems and infrastructure.
5 Department of Physics, University of Wisconsin, Madison, WI, 53706, USA
The experiment uses a loophole-free photonic Bell test and a new certification protocol to generate randomness without detailed device models, under independent-setting and non-signaling assumptions. It extracted 1024 bits uniform within 10^-12, while highlighting practical resource costs and residual assumptions.
- Motivation and assumptions: Loophole-free Bell testing certifies randomness using quantum nonlocality rather than detailed assumptions about the devices’ underlying physics.The experiment relies on high detection efficiency and space-like separation of the measurement stations.
- Motivation and assumptions: The certification assumes measurement settings are independent of the devices and prior classical information, and that each station’s outcome is independent of the other station’s setting.Under these assumptions, the output is unpredictable to an adversary holding pre-existing classical information but isolated from the devices during the protocol.
- Certification protocol: The protocol produces randomness through entropy production from Bell-test trials followed by extraction with a customized Trevisan-based TMPS algorithm.A Bell-violation statistic determines whether the protocol passes; if it passes, the outcome string is processed into a shorter string close to uniform.
- Certification protocol: The new certification method is designed for experiments with small per-trial Bell violations and does not require i.i.d. or asymptotic assumptions.It builds on the Prediction-Based Ratio method and constructs a Bell function whose expectation is bounded for local-realistic distributions.
- Experimental result: 1024 bits were extracted and certified uniform within 10^-12 after the protocol passed its threshold test.The extraction used a seed of length 315,844; the first ten extracted bits were 1110001001.
- Practical constraints: Generating the 1024 certified bits required 1.10 × 10^8 uniform setting-choice bits and 3.16 × 10^5 uniform seed bits.The strong extractor allows the seed bits to remain uniform conditional on passing and be recovered afterward, whereas the setting-choice bits cannot be recovered because passing is probabilistic.
- Practical constraints: The setting entropy cost can be reduced with highly biased settings, while the current protocol remains effective for private randomness when settings and seeds come from a public random source.The authors identify device-independent generation as a route toward greater trust in random sources and cryptographic infrastructure.
- Experimental result: The implementation improved both Bell-violation magnitude and the number of trials needed for statistically significant violation by an order of magnitude.The improvements came from higher detection efficiency, higher per-trial photon-detection probability, and a higher signal-to-background ratio.
S.1 Preliminaries
The preliminaries define random-variable notation, total-variation distance, Bell-test assumptions, and the distinction between local-realistic and non-signaling distributions.
- Capital letters denote random variables, while corresponding lowercase letters denote their possible values.
- Total-variation distance compares distributions of specified random variables, either conditionally or unconditionally.
- The theorem uses independent or imperfectly uniform settings together with conditional independence of each station’s outcome from the other station’s setting.
- Non-signaling distributions include all local-realistic distributions and can also include Popescu–Rohrlich boxes that are not local realistic.
- Local-realistic distributions are convex combinations of conditionally deterministic strategies indexed by local hidden variables.
S.2 Proof of the Entropy Production Theorem
The Entropy Production Theorem converts Bell-function statistics into a bound on outcome probabilities under non-signaling and settings assumptions.
- The theorem applies to past-parametrized Bell functions under Eqs. S7, S8, and S9, with threshold and error parameters constrained explicitly.
- A larger product of conditional Bell-function expectations yields a smaller upper bound on outcome-sequence probabilities and therefore more extractable randomness.
- The one-trial probability bound follows by decomposing a non-signaling distribution into a PR box and a local-realistic distribution.
- Test-martingale normalization gives expectation 1, and Markov’s inequality bounds the probability of an excessively large product by ϵp.
- After the running product exceeds the threshold, setting later Bell functions to 1 prevents subsequent fluctuations or drift from reducing the final product below threshold.
S.3 Choosing the Bell Function T
The Bell function T is selected by numerical optimization to maximize typical Bell-test statistics while satisfying constraints for local-realistic distributions and experimental settings.
- The optimization seeks a Bell function with high typical V, where V is the product of trial-wise Bell functions and ln V accumulates across trials.
- Training data are used to estimate a non-signaling distribution Q, enforcing uniform settings and non-signaling marginal constraints.
- The objective maximizes E(ln(T))Q because V^-1 is a conservative p-value against local realism and typical V is close to exp(nE(ln(T))Q).
- The constraints require E(T)Pλ ≤ 1 for every deterministic local-realistic distribution and set T(0, 0, x, y) = 1 for all settings.
- 1.42×10^-4 bits per trial is obtained for Data Set 5 from E(log2(T))/2m.
- The same construction can accommodate weaker settings randomness by checking extremal settings distributions with probabilities 1/4 + α and 1/4 − α.
S.4 The TMPS Algorithm
The TMPS algorithm is a strong seeded extractor that converts a high-min-entropy outcome string into nearly uniform output while accounting for seed and side-information requirements.
- TMPS implements a strong extractor Ext that maps a q-bit string with min-entropy at least σ and an independent uniform d-bit seed to t output bits.
- The extractor guarantees that the output concatenated with its seed is within TV distance ϵ of uniform.
- The TMPS construction is secure against classical and quantum side information, although the protocol does not directly exploit that security.
- The adapted extractor implementation is available as source code, and its parameter constraints may be improvable because the protocol does not directly use the available side-information security.
S.5 Proof of the Protocol Soundness Theorem
The proof establishes protocol soundness by converting a probabilistic bound on guessing the Bell-test outcomes into extractor guarantees, while preserving relevant marginals and seed independence. It then bounds the output’s distance from an ideal uniform protocol, including conditioning on passing.
- Soundness bound: The direct extractor application to AB is insufficient because settings conditioning, smoothness, and nonunit passing probability can reduce the usable min-entropy.These effects require analysis of settings- and pass-conditioned distributions before extraction.
- Proof strategy: The proof constructs a nearby distribution P∗ whose conditional outcome probabilities satisfy the required bound with probability one.P∗ remains within ϵp of the actual distribution and preserves the ZS marginals, abort-conditioned probabilities, and seed uniformity and independence.
- Proof strategy: The Entropy Production Theorem bounds the probability of excessive conditional guessing of C given Z and passing by ϵp.This bound also applies when the adversary’s information E is included in Z, using the theorem’s uniformity across E=e.
- Extractor step: The extractor is applied to C and an independent random seed S after accounting for settings conditioning and the probability of passing.The required extractor parameters use δ, κ, and ϵext rather than only the nominal smooth min-entropy.
- Extractor step: A lower bound κ on the passing probability is necessary because conditioning on an arbitrarily rare pass event can make the guessing-probability bound unbounded.The protocol soundness theorem therefore assumes P(pass) ≥ κ.
- Soundness bound: The unconditional total-variation distance from an ideal protocol is bounded by max(ϵp + ϵext, κ), while the conservative final error is ϵfin = max(ϵp/κ + ϵext, κ).The conservative choice ensures pass-conditioned output is within ϵp/κ + ϵext of the uniform distribution whenever the passing probability exceeds κ.
S.6 Protocol Application Details
The protocol applies a Bell-test-based entropy-production and extraction procedure to experimental data, using trained Bell functions, thresholds, and soundness parameters. Data Set 5 exceeded its threshold and supported extraction of 1024 bits uniform to within 10^-12, while consistency checks found no suggested signaling inconsistencies.
- Soundness and completeness: The protocol's pass-conditional output distribution is bounded by ϵp/κ + ϵext, with overall soundness error ϵfin = max(ϵp/κ + ϵext, κ).The protocol is complete when real-world systems pass with reasonably high probability, as predicted by quantum mechanics and repeated implementations.
- Protocol: The protocol combines Bell-test entropy production, a pass threshold, and seeded extraction to produce nearly uniform random bits.It aborts when the accumulated Bell statistic fails to exceed vthresh, then applies an extractor to the outcome string.
- Data Set 5: 1024 bits uniform to within 10^-12 remained extractable after choosing the conservative threshold vthresh = 1.5 × 10^32.This threshold corresponds to an approximately 0.9916 passing probability under the stated i.i.d. scenario.
- Data Set 5: V = 2.018 × 10^41 exceeded the selected threshold during the run, so the protocol passed for Data Set 5.The cumulative statistic first exceeded the threshold at trial 41,243,976, after which remaining outcomes could be relabeled to yield T_i = 1.
- Consistency checks: Consistency checks examined four no-signaling equalities, and the reported p-values for all data sets did not suggest inconsistencies.The tests used statistics intended to approach standard normal distributions under i.i.d. trials.
S.7 Performance of Previous Protocols.
Previous randomness-certification protocols were often mismatched to this experiment, required stronger violations or more devices, or offered only asymptotic guarantees. Under the stated assumptions, the PM protocol requires substantially more trials than the experiment provides to certify comparable low-error randomness.
- Several prior protocols cannot be directly applied because they target different measurement scenarios, require multiple devices, or provide only asymptotic security.
- The first protocol secure against quantum side information requires per-trial Bell violations much higher than those achieved by the photonic experiment.
- E(T_c)=0.75009787 exceeds the local-realism bound of 0.75 only slightly, so predictable local-realistic behavior can exceed this statistic at the experimental trial counts with probability roughly 0.047.
- The PM protocol uses a Bell function, threshold, and randomness-rate function, but its extraction condition imposes a lower bound on the required number of trials.
- 1.44 × 10^9 trials are required to achieve error ϵ=10^-12 under the analyzed PM-protocol bound, exceeding the number of trials used for Data Set 5 by more than twofold.
- The PM protocol cannot improve this bound under the stated assumptions because the relevant non-signaling randomness function is already tight for mixtures of deterministic local-realistic behavior and a PR box.