Quantum Randomness

Quantum random-number generation (QRNG) converts outcomes of a quantum experiment into classical symbols whose unpredictability is justified under a declared physical and adversarial model. A QRNG claim is therefore not merely that a file looks irregular or that quantum mechanics assigns several possible outcomes. It states which systems may be correlated with the raw data, how much conditional entropy the experiment certifies, which extractor is used, and how close the released string is to an ideal random resource.

The central engineering object is an entropy source, not a stream that has passed a test suite. The source includes the quantum process, preparation and measurement devices, analog electronics, digitizer, timing logic, operating environment, and any state retained between samples. Its raw record $X^n$ is normally biased, correlated, and partly predictable. Certification lower-bounds its smooth min-entropy conditioned on side information; extraction compresses that entropy into a shorter string $Z^\ell$ that is nearly uniform and private.

The task has three steps: identify which uncertainty is private, bound its entropy, and extract a suitable output string. The examples below compare optical noise, public extractor seeds and Bell-certified randomness. A larger raw data file does not necessarily contain more private randomness.

Required background. The Born rule gives quantum measurement probabilities; random variables and entropy provide the probability language. Trace distance measures how distinguishable a real output is from an ideal one.

Private randomness and side information

A balanced string has roughly equal numbers of zeros and ones. An unpredictable string is hard to guess with the specified side information. A private string remains unknown to Eve even after all permitted public information is revealed. These properties differ: a prerecorded sequence of fair coin flips can be balanced and pass output tests while being completely known to whoever recorded it.

A public beacon needs unpredictability before release and an authentic published result; it does not promise secrecy after publication. A key generator needs private bits. A Monte Carlo calculation instead emphasizes distributional accuracy and dependence between samples. The intended use determines which property must be proved.

Why output tests cannot prove unpredictability

Consider a deterministic table containing a billion independently sampled fair bits. A device can replay the table and pass frequency, runs, and correlation tests. Someone holding a copy predicts every output. Conversely, a genuinely random finite string can contain a long run or receive a small $p$-value by chance. Statistical tests can expose selected anomalies; they cannot infer the hidden causal history of one sequence.

This is why NIST SP 800-22 (2010) distinguishes statistical output testing from entropy-source validation and explicitly rejects test suites as a substitute for assessing a cryptographic generator. A defensible claim combines a source model, measurements that check the device remains within that model, an entropy estimate, and appropriate postprocessing.

The ideal private output

Let $Z\in\{0,1\}^\ell$ be the released string, $E$ all adversarial quantum side information, and $C$ all classical information that is permitted to be public: calibration data, extractor seed, test choices revealed after use, and other transcript fields. Ideal private randomness has the classical–quantum state

$$\tau_Z\otimes\rho_{EC}, \qquad \tau_Z=2^{-\ell}\sum_z |z\rangle\!\langle z|.$$

A composable real-world statement is

$$\frac12 \left\| \rho_{ZEC}-\tau_Z\otimes\rho_{EC} \right\|_1 \leq \varepsilon_{\mathrm{rnd}}.$$

Trace Distance explains the operational metric. Roughly, replacing the real output by ideal uniform private bits changes the behavior of any larger protocol by at most the declared error. Separate failure allocations may cover entropy estimation, parameter estimation, extraction, authentication, and implementation checks; composable analyses add them into one budget.

For an aborting generator, let $\Omega$ be acceptance and $d_\Omega$ the same trace distance for the normalized accepted state. The usual full-protocol requirement is $\Pr(\Omega)d_\Omega\le\varepsilon_{\mathrm{rnd}}$, with matching real and ideal abort branches. A rare accepted output need not have distance at most $\varepsilon_{\mathrm{rnd}}$ by itself. Completeness separately bounds abort probability for the specified honest device. Eve may still force abort by blocking or jamming the source.

Born Probabilities Are Not Yet a Security Proof

For a trusted qubit prepared in

$$|+\rangle = \frac{|0\rangle+|1\rangle}{\sqrt 2},$$

a computational-basis measurement gives

$$\Pr(0)=\Pr(1)=\frac12.$$

Under the additional assumptions that the state really is $|+\rangle$, the measurement implements the intended projectors, and no outside system is correlated with the qubit, one outcome is an ideal random bit. The Born rule is the physical origin of its unpredictability within that model.

The same local probabilities do not prove privacy. Suppose Eve prepares

$$\rho_{QE} = \frac12 |0\rangle\!\langle0|_Q\otimes|0\rangle\!\langle0|_E + \frac12 |1\rangle\!\langle1|_Q\otimes|1\rangle\!\langle1|_E.$$

Measuring $Q$ produces a perfectly balanced bit, but Eve can measure $E$ and guess it with certainty. Randomness is always relative to side information and to a trust model. Calling an effect quantum identifies a candidate entropy mechanism; it does not by itself quantify private output.

Min-Entropy and Guessing Probability

For a classical random variable $X$, the min-entropy is

$$H_{\min}(X) = -\log_2\!\left(\max_x p_X(x)\right).$$

It measures worst-case single-shot predictability. A bit with $p(0)=0.55$ has

$$H_{\min}(X)=-\log_2(0.55)\approx0.862$$

bits of min-entropy, not one full bit. Shannon entropy answers a different average coding question and can overstate what is safely extractable in a one-shot adversarial task.

For a classical register $X$ correlated with a quantum system $E$, conditional min-entropy has the operational identity

$$H_{\min}(X\mid E)_\rho = -\log_2 p_{\mathrm{guess}}(X\mid E),$$

where $p_{\mathrm{guess}}$ is Eve’s best probability of identifying $X$ using the optimal measurement on $E$. Conditioning should include every variable the security model grants to Eve, including classical environmental records and the public transcript.

Finite protocols use the smooth conditional min-entropy $H_{\min}^{\varepsilon_s}(X\mid E)$. Smoothing permits optimization over states within a small operational neighborhood of the observed state and is the right quantity for finite-block extraction. It is not permission to discard unfavorable data after looking at them; the smoothing parameter is part of the predeclared failure budget.

For a sequence, one may not silently multiply a one-sample estimate by the number of samples:

$$H_{\min}(X^n\mid E) \ne n H_{\min}(X_1\mid E)$$

in general. Equality or a comparable lower bound needs independence, a Markov condition, a stationary-process analysis, entropy accumulation, or another explicit argument controlling temporal correlations and memory.

Generation, digitization, entropy estimation and extraction are separate steps. A sound optical model does not establish the behavior of an undocumented digitizer, and a correct extractor cannot repair a false entropy estimate. Each claim should identify its raw symbol, conditioned side information and resulting output guarantee.

Trust Models

QRNG labels describe what the proof does not need to characterize. They do not rank devices by one universal security number.

Model	Characterized assumptions	Entropy test
Trusted device	source and measurement, including imperfections	physical model and monitored parameters
Source independent	measurement and its accepted input space	complementary measurements and source-independent bounds
Measurement independent	prepared probe states	prepare-and-measure response statistics
Semi-device-independent	specified dimension, energy or state overlap	a witness under that restriction
One-sided independent	one endpoint’s measurement apparatus	steering correlations
Fully device independent	isolated laboratories, inputs and classical processing	a Bell test with all eligible outcomes

These models do not form a single ladder. An energy bound and a dimension bound restrict different attacks; source-independent and measurement-independent designs characterize opposite parts of the experiment. The relevant comparison is the actual set of assumptions.

Trusted Quantum Sources

Trusted-device generators can operate at high rates because they infer entropy from a detailed model rather than from a Bell violation. Their assurance is only as good as that model and the monitoring that keeps the implementation inside it.

Beam-splitter path choice

An ideal single photon entering one port of a balanced beam splitter transforms, up to convention-dependent phases, as

$$|1\rangle_a|0\rangle_b \longmapsto \frac{ |1\rangle_c|0\rangle_d +i|0\rangle_c|1\rangle_d }{\sqrt2}.$$

A click in output $c$ or $d$ supplies a binary outcome. Real analysis must cover unequal splitting, detector-efficiency mismatch, dark counts, afterpulsing, dead time, double clicks, missed events, source multiphoton probability, and the rule for assigning or rejecting every event. Calibrating away bias is different from proving that accepted clicks were unknown to an adversary.

Arrival time and photon counting

Spontaneous emission, radioactive decay, and photon arrival times provide continuous waiting-time or count distributions. Digitizing an arrival time into bins can yield several raw bits per event, but detector jitter, clock structure, dead time, pileup, and afterpulsing correlate neighboring bins. Conditioning on “exactly one click in this window” also changes the distribution and must be part of the model rather than an undocumented postselection.

Vacuum quadrature measurements

A balanced homodyne receiver can measure a field quadrature of the vacuum (Gabriel et al., 2010). A simple digitized model is

$$Y_i=Q_i+C_i, \qquad X_i=\mathcal Q_{\mathrm{ADC}}(gY_i+o),$$

where $Q_i$ is the modeled quantum contribution, $C_i$ collects classical and electronic contributions, $g$ is gain, $o$ is offset, and $\mathcal Q_{\mathrm{ADC}}$ includes finite range and binning. If conservative analysis grants Eve knowledge or control of $C_i$, entropy must be bounded conditioned on that variable, not estimated from the total variance as though all measured noise were private quantum noise.

Vacuum and laser-phase designs can exploit wide optical and electronic bandwidths. They also make saturation, local-oscillator manipulation, common-mode leakage, ADC nonlinearities, and bandwidth correlations central security parameters. More variance is not automatically more entropy.

Laser phase diffusion

Spontaneous emission gives a reset or gain-switched laser pulse a quantum phase component. Interfering neighboring pulses converts phase difference into intensity, schematically

$$I_i = I_0\left[1+V\cos(\phi_i-\phi_{i-1}+\theta)\right].$$

Fast generators can be built from this mechanism, but the proof must quantify residual phase coherence, pulse-energy variation, interferometer drift, classical phase noise, visibility, digitizer response, and inter-pulse memory. The nonlinear cosine map also makes the raw distribution nonuniform even when the phase is uniform.

Digitization Is Part of the Source

Let $V=gY+o$ be the voltage entering an ADC with bins $B_x$. Conditional on a classical nuisance value $c$, the most likely raw symbol has probability

$$p_{\max}(c) = \max_x \int_{B_x} p_{V\mid C}(v\mid c)\,dv.$$

For this fully specified classical-side-information model,

$$p_{\mathrm{guess}}(X\mid C) = \sum_c p(c)\,p_{\max}(c), \qquad H_{\min}(X\mid C) = -\log_2 p_{\mathrm{guess}}(X\mid C).$$

Continuous or quantum side information requires the corresponding integral or operator formulation, but the lesson is unchanged: the largest conditional bin probability, including overflow bins, controls one-shot entropy. An $m$-bit ADC does not certify $m$ random bits per sample.

The bins include overflow or saturation outcomes. Gain drift, offset drift and nonlinear bin boundaries change their probabilities and therefore the entropy bound. If those quantities are known to Eve, they belong in the conditioning information too.

For a concrete example, let $Q$ be private Gaussian noise of standard deviation $\sigma$, and let a classical offset $C=\pm2\sigma$ be chosen equally often and known to Eve. A one-bit digitizer returns $X=\mathbf1\{Q+C\ge0\}$. The marginal bit is balanced, but knowledge of the offset gives Eve a guessing probability of about $0.97725$. Exercise 8 derives the small conditional entropy despite the increased total variance.

The two curves are the conditional voltage densities for offsets $C=-2\sigma$ and $C=+2\sigma$. The threshold is zero. Averaging the curves gives equal marginal probabilities for the two output bits, but someone who knows the offset predicts the sign with probability $\Phi(2)\approx0.97725$. Here $\Phi$ is the standard normal cumulative distribution. Balance alone hides the lost privacy.

Oversampling is a common rate error. Sampling at $f_s$ far above the effective noise bandwidth $B$ produces correlated values, not $f_s/B$ independent copies of the same entropy. A secure bound must be made on blocks or through a validated spectral or dynamical model. Downsampling can reduce correlation but does not by itself prove independence.

Health Tests and Entropy Certification

Source characterization establishes a physical and statistical model, while startup and continuous tests check selected failures. NIST SP 800-90B (2018) describes entropy-source requirements and repetition-count and adaptive-proportion health tests. A stuck source may trigger them; passing does not prove that every adversarial predictability mechanism is absent.

An alarm that invalidates the entropy model must prevent release of the affected block. Conversely, an honest random source can produce an unusual sequence and trigger a false alarm. Thresholds therefore balance fault detection and completeness; they do not create entropy. General output batteries remain useful for detecting coding mistakes, but do not replace the source analysis.

Randomness Extraction

A seeded extractor is a deterministic function

$$Z=\operatorname{Ext}(X,S)$$

whose guarantee holds when $X$ has enough conditional min-entropy and the seed $S$ is uniform and independent of the joint raw source and side information $(X,E,C)$. Here $C$ denotes the pre-seed transcript. A strong extractor produces output that remains close to uniform even when $S$ is published. The seed therefore need not be secret, but it must not have been chosen as a function of the raw block or adversarial side information in a way excluded by the theorem.

Two-universal hashing, often implemented with a Toeplitz matrix, gives a quantum-proof construction (Tomamichel et al., 2011). Using purified-distance smoothing and the actual side-information marginal on the right, a conservative leftover-hash bound is

$$\frac12 \left\| \rho_{ZSEC} - \tau_Z\otimes\rho_{SEC} \right\|_1 \leq 2\varepsilon_s + \frac12 2^{-\frac12\left[ H_{\min}^{\varepsilon_s}(X\mid E,C)-\ell \right]}.$$

The total displayed error is $2\varepsilon_s+\varepsilon_{\mathrm{ext}}$. An extractor-error allocation $\varepsilon_{\mathrm{ext}}$ permits the schematic length choice

$$\ell \leq H_{\min}^{\varepsilon_s}(X\mid E,C) -2\log_2\!\frac{1}{2\varepsilon_{\mathrm{ext}}}.$$

Exact conventions and finite corrections depend on the theorem used. The key point is invariant: extraction concentrates certified entropy; it does not create it. Given a public seed, hashing a deterministic raw string gives a deterministic output known to anyone who knows that string and seed.

Simple debiasing deserves the same caution. Von Neumann’s pair rule, $01\mapsto0$, $10\mapsto1$, and $00,11\mapsto\varnothing$, removes unknown bias for independent identically distributed coin flips. It does not generally handle memory, adversarial side information, detector asymmetry, or a drifting source. It is not a substitute for a quantum-proof extractor with a stated entropy premise.

Seed handling

Publishing $S$ is allowed by the strong-extractor guarantee, but letting the source adapt to $S$ can destroy the independence premise. Exercise 5 constructs a source with more than three bits of conditional min-entropy whose hash output is nevertheless fixed because it was chosen after the seed. Seed reuse needs a proof that preserves the relevant independence across blocks; domain separation alone does not establish it.

Bell-test inputs have a different role. Each box necessarily learns its own local input before responding. What must be excluded is advance correlation of the choices with the shared devices or Eve, or communication of the remote input before outputs are fixed. A party knowing its legitimate local setting is not itself a loophole.

Finite blocks and output rate

For $n$ raw symbols, a typical proof has the form

$$H_{\min}^{\varepsilon_s}(X^n\mid E,C) \geq n h_{\mathrm{cert}}-\Delta_{\mathrm{fin}},$$

where $h_{\mathrm{cert}}$ is a model-dependent entropy rate and $\Delta_{\mathrm{fin}}$ includes finite estimation, smoothing, nonstationarity, and other proof-specific penalties. The releasable length is then bounded by

$$\ell \leq n h_{\mathrm{cert}} -\Delta_{\mathrm{fin}} -\Delta_{\mathrm{ext}}.$$

If one block takes wall time $T$, the delivered rate is $R_{\mathrm{out}}=\ell/T$ after accounting for discarded startup samples, test rounds, transfer limits, extractor throughput, aborts, and downtime. Quoting the ADC sample rate or the raw interface bitrate as the random-bit rate omits the quantity of interest.

As an illustrative calculation, suppose $10^8$ raw samples have a defensible block rate $h_{\mathrm{cert}}=0.73$ bits per sample after conditioning on all modeled side information, and the finite penalty is $1.5\times10^6$ bits. With $\varepsilon_{\mathrm{ext}}=2^{-64}$, the displayed leftover-hash convention requires about $126$ more bits of compression:

$$\begin{aligned} H_{\min}^{\varepsilon_s}(X^n\mid E,C) &\geq 73{,}000{,}000-1{,}500{,}000,\\ \ell &\leq 71{,}499{,}874. \end{aligned}$$

The difficult premise is the block entropy bound, including correlations and side information. The arithmetic shows how that premise limits the length of the released output. Over many blocks with aborts or variable duration, use total released bits divided by total elapsed time, not the average of successful-block ratios.

Device-Independent Randomness

Entropy accumulation is developed by Dupuis, Fawzi and Renner (2020). A fully device-independent QRNG treats the source and quantum measurement devices as black boxes with classical inputs and outputs. In a bipartite CHSH protocol, the boxes receive $x,y\in\{0,1\}$ and return $a,b\in\{0,1\}$. The correlators

$$E_{xy} = \sum_{a,b} (-1)^{a+b}p(a,b\mid x,y)$$

form the CHSH value

$$S=E_{00}+E_{01}+E_{10}-E_{11}.$$

Local hidden-variable behavior obeys $|S|\leq2$, while quantum mechanics permits $|S|\leq2\sqrt2$. A Bell violation rules out a strategy in which all relevant outputs were fixed and known in advance, provided the causal, input-independence, loss, and laboratory assumptions of the Bell experiment hold.

For a single quantum CHSH round with $2\le|S|\le2\sqrt2$, independent inputs and no communication during measurement, the adversary’s guessing probability for one party’s tested output, conditioned on its input and before revealing the other party’s output, can be bounded by

$$p_{\mathrm{guess}}(A\mid E,x) \leq \frac12 \left( 1+\sqrt{2-\frac{S^2}{4}} \right),$$

and hence

$$H_{\min}(A\mid E,x) \geq 1- \log_2\!\left( 1+\sqrt{2-\frac{S^2}{4}} \right).$$

At $S=2$ this certifies no local randomness; at the Tsirelson value it certifies one bit in the ideal single-round setting. Publicly revealing the other output may reduce this entropy and must be accounted for. Pironio et al. (2010) give the Bell-randomness connection; general quantum-side-information expansion requires a suitable sequential proof, such as Miller and Shi (2017) or Arnon-Friedman, Renner and Vidick (2019). Finite sequential protocols do not apply this formula independently to observed rounds. They predeclare a score, test a random subset or use a probability-estimation method, derive a high-confidence lower score $S_*$, and use entropy accumulation or another general-attack theorem:

$$H_{\min}^{\varepsilon_s}(A_{\mathrm{gen}}^n\mid E,C) \geq n f(S_*)-\Delta_{\mathrm{EA}}.$$

Here $n$ counts the chosen protocol rounds and $f$ includes the generation/test allocation and disclosed information. Acceptance conditioning and its probability must be treated consistently with the abort-inclusive definition above. The extractor then produces the composable output. The exact tradeoff function $f$, test probability, stopping rule, and finite term are protocol-specific.

The DI-QKD page explains trial timing, no-clicks, private inputs, laboratory isolation, sequential memory and device reuse. The same issues constrain DI randomness: deleting no-clicks or leaking a hidden test/generation flag can invalidate the test-to-output inference. QRNG has no second private raw key to reconcile, so its output task differs from shared-key distribution.

Expansion and Amplification

Randomness expansion starts from a short, sufficiently uniform seed, uses some of it to select Bell-test settings, and aims to produce a longer certified string. If $d$ fresh seed bits are consumed and $\ell$ private bits are released, net expansion requires

$$\ell-d>0.$$

Spot-checking protocols choose a small fraction of test rounds and use a fixed generation setting otherwise, reducing seed cost. A gross output larger than the raw setting record is not enough: the calculation must count all fresh randomness consumed under the security theorem and retain the declared soundness error. For example, a direct $\ell\times n$ Toeplitz hash uses $n+\ell-1$ seed bits. If all of those bits are freshly consumed in addition to Bell settings, that implementation alone cannot give positive net expansion. A short-seed extractor (De et al., 2012), justified seed reuse, or an explicitly supplied public-randomness resource changes the calculation; simply calling the seed public does not make its randomness free.

Randomness amplification addresses a different problem. A Santha–Vazirani source, in its classical-side-information form, produces bits $R_i$ satisfying, for some $0<\alpha\leq1/2$,

$$\alpha \leq \Pr(R_i=0\mid R_{<i},\Lambda) \leq 1-\alpha.$$

Here $\Lambda$ is a classical side-information variable; conditioning directly on a quantum register is not a classical conditional probability. Quantum-side-information versions require an appropriate operator formulation. When $\alpha$ is small, each input may be highly biased and correlated with the past and side information, though not completely fixed. Deterministic classical processing cannot generally turn such a source into nearly uniform bits. Colbeck and Renner (2012) and Gallego et al. (2013) develop Bell-based amplification of weak randomness under protocol-specific quantum or no-signaling, causal-independence, device, and acceptance assumptions. That is a physical cryptographic task, not ordinary extractor postprocessing.

Expansion assumes a sufficiently uniform seed and asks for more random bits; amplification weakens the initial-randomness assumption and asks for better bits. Neither is a promise that arbitrary weak or adversarial sources can be repaired without additional physical assumptions.

A deterministic random bit generator can efficiently stretch a secret seed under computational assumptions. It does not increase information-theoretic entropy. Similarly, a public beacon can provide timely unpredictable values whose authenticity matters after release, but publication gives no privacy from the public. These uses should be distinguished from private quantum randomness.

Exercises

1. Balanced but completely predictable

A device emits $010101\ldots$ forever. Compute the empirical frequency of each bit and the min-entropy of the next bit for an observer who knows the rule.

Solution

Over every even-length block, the empirical frequencies are $\hat p(0)=\hat p(1)=1/2$. The next bit is nevertheless fixed by the position, so the informed observer guesses with probability one. Therefore

$$H_{\min}(X_{i+1}\mid i)= -\log_2 1=0.$$

Frequency balance is not unpredictability.

2. Local uncertainty versus privacy

Compare measurement of $|+\rangle_Q$ with measurement of the correlated state

$$\rho_{QE} = \frac12\sum_{x=0}^1 |x\rangle\!\langle x|_Q\otimes|x\rangle\!\langle x|_E.$$

Find $H_{\min}(X)$ and $H_{\min}(X\mid E)$ in each case, assuming the first qubit has no side information.

Solution

Both measurements have a uniform local distribution, so $H_{\min}(X)=1$ bit. For the isolated $|+\rangle$ preparation, Eve has no correlated system and $p_{\mathrm{guess}}(X\mid E)=1/2$, giving $H_{\min}(X\mid E)=1$. For the correlated state, measuring $E$ in the computational basis reveals $X$ exactly, so $p_{\mathrm{guess}}(X\mid E)=1$ and $H_{\min}(X\mid E)=0$.

3. Extraction budget for a biased source

Assume, as an explicit model, that $n=10^6$ independent bits have $p(0)=0.55$ and no side information. Ignore parameter-estimation penalties and take $\varepsilon_{\mathrm{ext}}=2^{-40}$. Using the displayed leftover-hash length rule with zero smoothing, estimate the maximum output length.

Solution

One sample has min-entropy $-\log_2(0.55)\approx0.862496$. Independence gives

$$H_{\min}(X^n) \approx 862{,}496\ \text{bits}.$$

The extractor penalty is

$$2\log_2\frac{1}{2\varepsilon_{\mathrm{ext}}} =2\log_2(2^{39})=78.$$

Thus $\ell\leq862{,}418$ bits under these deliberately simplified premises. In a real source, estimating the bias and proving independence would add finite penalties.

4. Oversampling

A homodyne receiver is digitized at $1\ \mathrm{GS/s}$ but has effective noise bandwidth $100\ \mathrm{MHz}$. Explain why assigning one independent entropy contribution to every ADC sample is unjustified, and name two valid routes to a block entropy bound.

Solution

The analog filter and detector response spread one fluctuation over several samples, creating temporal correlation. A one-sample distribution does not determine $H_{\min}(X^n\mid E)$. One may use a validated stationary spectral or dynamical model that bounds the conditional entropy rate, or analyze empirical blocks with a theorem that permits the observed memory. Conservative downsampling can support either model, but merely selecting every tenth sample does not prove independence.

5. A public seed chosen too early

Let the seed $S$ be uniform on four-bit rows, and let $h_S(X)=S\cdot X$ modulo two for $X\in\{0,1\}^4$. After seeing $S$, a source chooses $X$ uniformly from the kernel $\{x:S\cdot x=0\}$. Find $H_{\min}(X\mid S)$ and the output distribution. Which extractor assumption fails?

Solution

For the zero row, all sixteen strings are in the kernel. Each of the other fifteen rows has an eight-element kernel. Therefore

$$p_{\mathrm{guess}}(X\mid S)=\frac1{16}\frac1{16}+\frac{15}{16}\frac18=\frac{31}{256}, \qquad H_{\min}(X\mid S)\approx3.046.$$

Nevertheless $h_S(X)=0$ always. Its distance from a uniform output bit, even conditioned on $S$, is one-half. The hash family is two-universal: for any nonzero difference $x\oplus x'$, half the rows give the same output on $x,x'$. The failure is that $S$ is not independent of the source $X$. A large entropy bound after conditioning on $S$ does not restore the independence required by the seeded-hashing theorem.

6. CHSH randomness bound

Use the displayed single-round bound to estimate the certified min-entropy of one party’s output at $S=2.5$. Check the local and Tsirelson limits.

Solution

At $S=2.5$,

$$\begin{aligned} p_{\mathrm{guess}} &\leq \frac12\left(1+\sqrt{2-\frac{2.5^2}{4}}\right)\\ &\approx0.83072, \end{aligned}$$

so

$$H_{\min}(A\mid E,x) \gtrsim -\log_2(0.83072) \approx0.267\ \text{bits}.$$

At $S=2$, the bound gives $p_{\mathrm{guess}}=1$ and zero entropy. At $S=2\sqrt2$, it gives $p_{\mathrm{guess}}=1/2$ and one bit. A finite experiment must replace the observed score by a confidence-adjusted score and include the sequential finite-size penalty.

7. Expansion or amplification?

Classify each task: (a) 1,000 ideal seed bits lead to 10,000 certified bits; (b) highly biased Santha–Vazirani inputs lead to nearly uniform outputs; (c) a Toeplitz hash compresses a trusted raw block with known min-entropy.

Solution

(a) is randomness expansion if all fresh seed use is counted and the net output is positive. (b) is randomness amplification because the quality assumption on the initial source is weakened. (c) is randomness extraction: it converts already certified entropy into nearly uniform bits and does not generate or amplify the physical entropy premise.

8. More variance, less private entropy

Let $Q\sim\mathcal N(0,\sigma^2)$ be private noise independent of $C$, with $C=\pm2\sigma$ equally likely and known to Eve. The digitizer outputs $X=\mathbf1\{Q+C\ge0\}$. Find the marginal bit distribution, total voltage variance, Eve’s guessing probability and conditional min-entropy. Compare with $C=0$.

Solution

For $C=2\sigma$, $\Pr(X=1\mid C)=\Phi(2)$; for $C=-2\sigma$, $\Pr(X=0\mid C)=\Phi(2)$. Symmetry makes the marginal bit fair. Independence gives

$$\operatorname{Var}(Q+C)=\sigma^2+4\sigma^2=5\sigma^2.$$

Eve predicts the sign of the offset, with

$$p_{\mathrm{guess}}(X\mid C)=\Phi(2)\approx0.97725, \qquad H_{\min}(X\mid C)\approx0.0332\ \text{bits}.$$

With $C=0$, the trusted private Gaussian gives a fair sign bit and one bit of entropy. Adding a known random offset increased the voltage variance fivefold while making the digitized bit much more predictable. This is a classical-side-information example; a full quantum model must also bound any residual quantum information held by Eve.

References

• R. Arnon-Friedman, R. Renner, and T. Vidick, “Simple and tight device-independent security proofs,” SIAM Journal on Computing 48, 181–225 (2019), doi:10.1137/18M1174726.
• R. Colbeck and R. Renner, “Free randomness can be amplified,” Nature Physics 8, 450–453 (2012), doi:10.1038/nphys2300.
• A. De, C. Portmann, T. Vidick, and R. Renner, “Trevisan’s extractor in the presence of quantum side information,” SIAM Journal on Computing 41, 915–940 (2012), doi:10.1137/100813683.
• F. Dupuis, O. Fawzi, and R. Renner, “Entropy accumulation,” Communications in Mathematical Physics 379, 867–913 (2020), doi:10.1007/s00220-020-03839-5.
• C. Gabriel et al., “A generator for unique quantum random numbers based on vacuum states,” Nature Photonics 4, 711–715 (2010), doi:10.1038/nphoton.2010.197.
• R. Gallego et al., “Full randomness from arbitrarily deterministic events,” Nature Communications 4, 2654 (2013), doi:10.1038/ncomms3654.
• C. A. Miller and Y. Shi, “Universal security for randomness expansion from the spot-checking protocol,” SIAM Journal on Computing 46, 1304–1335 (2017), doi:10.1137/15M1044333.
• NIST, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, SP 800-22 Rev. 1a (2010; revision decision 2022), doi:10.6028/NIST.SP.800-22r1a.
• NIST, Recommendation for the Entropy Sources Used for Random Bit Generation, SP 800-90B (2018; errata noted 2025), doi:10.6028/NIST.SP.800-90B.
• S. Pironio et al., “Random numbers certified by Bell’s theorem,” Nature 464, 1021–1024 (2010), doi:10.1038/nature09008.
• M. Tomamichel, C. Schaffner, A. Smith, and R. Renner, “Leftover hashing against quantum side information,” IEEE Transactions on Information Theory 57, 5524–5535 (2011), doi:10.1109/TIT.2011.2158473.