Simple and tight device-independent security proofs

1 Introduction

• Device-independent security aims to base guarantees on observed statistics rather than device trust, addressing risks from implementation assumptions and side-channel attacks.Bell games distinguish quantum devices from classical strategies when observed success exceeds the classical bound.Source: §1 · pp. 1–2
• The i.i.d. assumption rules out device memory and time-dependent behavior; without it, rounds may correlate and entropy accumulation is harder to characterize.Earlier direct analyses of the general case required more complex techniques and statistical analysis.Source: §1 · p. 3

1.1 Results and contributions

• The framework's reduction is virtually lossless, and its leading entropy constant matches the optimal i.i.d. constant even against general quantum adversaries.The authors also provide explicit formulas for the leading and second-order constants c1 and c2.Source: §1.1 · pp. 3–4
• DIQKD tolerates up to 7.1% error while producing a positive key rate, and CHSH randomness expansion reaches essentially the classical-adversary optimal rate against quantum adversaries.The DIQKD rate approaches the optimal i.i.d. result of; the randomness expansion rate is essentially that of.Source: §1.1 · p. 4
• Sequential observations obey a Markov property that lets the entropy accumulation theorem replace the smooth-min-entropy chain rule and support a modular protocol.For each application, a min-tradeoff function lower-bounds single-round conditional Shannon entropy and accounts for finite-statistics fluctuations.Source: §1.1 · pp. 4–5

1.2 Related and subsequent work

• Early DIQKD work had zero noise tolerance and zero key rate; later i.i.d. results obtained positive rates, while non-i.i.d. proofs remained complex and comparatively weak.The CHSH protocol of achieved the best rates under its asymptotic i.i.d. assumptions.Source: §1.2 · p. 5
• Randomness expansion had non-i.i.d. security results, but earlier rates were limited by classical-adversary assumptions or noise tolerance.[PAM+10] showed quadratic expansion against classical adversaries; established exponential expansion against quantum adversaries without noise tolerance, and later allowed positive noise.Source: §1.2 · p. 5
• The framework has since been applied to additional cryptographic tasks and experimental randomness generation, with application rates depending on finding a suitable min-tradeoff function.The second-order terms in the entropy accumulation theorem were later improved in [DF18].Source: §1.2 · p. 6

2.1 General notation

• The paper uses base-2 logarithms, [n] for the round indices, and register subscripts to identify the systems supporting quantum states.It also defines the empirical frequency distribution of a sequence over a finite alphabet.Source: §2.1 · p. 6

2.2 Entropies and Markov chains

• Conditional von Neumann entropy is defined by the difference of joint and marginal entropies, while a quantum Markov chain expresses conditional independence.The smooth conditional min-entropy maximizes min-entropy over nearby states.Source: §2.2 · pp. 6–7

2.3 Non-local games

• A non-local game tests whether separated players’ outputs meet a winning criterion; the paper’s CHSH variant has quantum winning probability about 0.85 versus 0.75 classically.The variant adds a third input for Bob, on which matching outputs are required.Source: §2.3 · pp. 7–8

2.4 Untrusted device

• The untrusted device may retain memory and change its strategy between rounds, while Alice and Bob control when its components communicate.The model disallows signalling from their components to Eve and assumes secure locations, trusted randomness and classical processing, an authenticated public channel when needed, and valid quantum physics.Source: §2.4 · pp. 8–9

DIQKD.

• A DIQKD protocol produces keys for Alice and Bob while requiring correctness, secrecy against Eve, and bounded abort probability for an honest implementation.The stated secrecy definition is not rigorously established as composable for DI protocols, and the device generally cannot be reused afterward.Source: DIQKD · pp. 9–10

Randomness expansion.

• Randomness expansion converts a uniformly random input string into a statistically near-uniform output conditioned on the input and Eve’s side information.The security definition is not proven composable in general.Source: Randomness expansion · p. 10

2.6 The entropy accumulation theorem

• The entropy accumulation theorem bounds total entropy using per-round tradeoff functions for sequential channels satisfying its conditions.When a suitable per-round bound holds, the total entropy is roughly n times that bound, yielding a reduction to the i.i.d. setting.Source: §2.6 · pp. 11–12

3 Device-independent entropy accumulation protocol

• Protocol 1 serves as a mathematical tool: its EAT-channel construction yields a final state matching, or readily related to, the actual protocol’s state for entropy analysis.The goal is a smooth min-entropy bound on Alice and Bob’s raw data conditioned on Eve’s information.Source: §3 · p. 12

3.1 The protocol

• Each round randomly selects test or generation inputs, records device outputs, scores test-round wins, and aborts if the accumulated score misses the expected threshold.The generation inputs are chosen within the test-input set so the device cannot infer the test-round flag from Alice’s generation input.Source: §3.1 · pp. 12–13

3.2 Completeness

• For an honest i.i.d. implementation, the round scores are i.i.d. with mean ωexpγ, and Hoeffding’s inequality bounds the probability of abort.The protocol’s completeness result states that this abort probability is at most εc.Source: §3.2 · p. 14

3.3 Soundness

• For any device, the EAT gives a lower bound on entropy conditioned on non-abort when a min-tradeoff function bounds per-round conditional entropy.The required tradeoff is evaluated against the observed score distribution; using min-entropy in place of entropy can make the resulting bound non-tight.Source: §3.3 · pp. 14–15

4 A bound for the CHSH game

• As n grows, ηopt approaches the optimal one-round Shannon entropy rate, which is an upper bound on the entropy that can be accumulated.The optimal rate follows from the quantum asymptotic equipartition property.Source: §4 · p. 17
• The CHSH bound uses a differentiable min-tradeoff function, cutting g and joining it to a linear branch to keep the gradient bounded.The construction incurs an entropy loss for p with p(1) > p_t(1).Source: §4 · pp. 18–19
• Values of p(1)/γ at or below 3/4 are irrelevant to protocol operation because they lead to abort; the function’s extension there is for mathematical completeness.Source: §4 · pp. 16, 19
• Corollary 12 retains the entropy bound when output-flipping symmetrisation is omitted, avoiding a step that costs substantial randomness.The symmetrisation step is helpful in the proof, but its randomness cost can be problematic for applications such as randomness expansion.Source: §4 · pp. 15, 20

5.1 The protocol

• Protocol 2 uses CHSH rounds to generate raw data, then applies error correction, Bob-side parameter estimation, and privacy amplification to produce final keys.The post-processing choices are selected to optimize key rate, and the analysis can be adapted to other choices.Source: §5.1 · pp. 20–21

5.2 The honest implementation

• The honest implementation assumes i.i.d. states and measurements, characterized by CHSH winning probability ωexp and quantum bit error rate Q.The passage gives a two-qubit Werner state as one possible realization of this implementation.Source: §5.2 · p. 22

5.3 Completeness

• For an honest device, the protocol’s abort probability is bounded by the entropy-accumulation protocol’s completeness error plus εEC.Completeness follows from the honest i.i.d. implementation and the completeness result for the entropy accumulation protocol.Source: §5.3 · p. 22

5.4 Soundness

• Protocol 2 is (εEC + εPA + εs)-correct-and-secret with key length ℓ, unless it aborts with probability greater than 1 − εEA − εEC.The soundness error comprises at most εEC for error-correction failure and εPA + εs for privacy amplification.Source: §5.4 · pp. 24–25

5.5 Key rate analysis

• The key-rate analysis evaluates ℓ/n under an honest i.i.d. Werner-state implementation and compares it with device-dependent finite-resource and restricted-attack DIQKD rates.The provided passages describe the analysis setup and comparison targets but do not give resulting key-rate values.Source: §5.5 · p. 25
• The honest-device implementation is an assumption only about honest behavior; it does not restrict adversarial actions or device imperfections, and the analysis can be adapted to other implementations.Source: §5.5 · p. 25

5.5.1 Leakage due to error correction

• Error-correction leakage is upper-bounded by evaluating smooth conditional entropy on an honest i.i.d. implementation, using a non-asymptotic equipartition bound.For the honest implementation, the per-round maximum entropy is 1, while conditional entropy combines generation-round error Q and test-round guessing probability ωexp.Source: §5.5.1 · pp. 25–26

5.5.2 Key rate curves

• The presented key-rate curves come from a modified protocol that fixes the expected, rather than exact, number of rounds and improves rates.Its completeness and soundness proofs follow the same lines as those for the original protocol.Source: §5.5.2 · p. 26
• For Q = 0.5%, 2.5%, and 5%, the achieved rates are approximately r = 87%, 53%, and 22%, respectively.The rates are significantly higher than in previous works and practically comparable to device-dependent QKD; the device-dependent protocols can achieve positive rates with fewer rounds. Further parameter optimization might enable positive rates here at ¯n = 10^4–10^6.Source: Figure 6 · p. 27, §5.5.2 · p. 27
• At ¯n = 10^15, the key-rate curve essentially matches the optimal asymptotic i.i.d. rate, and the protocol tolerates noise up to Q = 7.1%.The asymptotic i.i.d. rate is an upper bound on the general-adversary rate, so this agreement makes the rate optimal for sufficiently many rounds.Source: Figure 5 · p. 26, §5.5.2 · p. 27

6 Randomness expansion

• The protocol uses deterministic generation-round inputs and focuses on CHSH, with test rounds estimating Bell violation before extraction produces the output string.The protocol chooses generation inputs from Xg={0} and Yg={0}; its final step applies an extractor to AB.Source: §6 · pp. 28–29
• 8h(γ)n uniformly random bits suffice to sample the round-selection variables within statistical distance εSA of i.i.d. Bernoulli(γ) bits, with abort probability at most εSA.The protocol also requires shared knowledge of which rounds are generation rounds.Source: §6 · p. 28
• The extractor lemma sets seed length d=⌈δn⌉ and output length m=⌈k−9 log k⌉ for inputs with the stated entropy condition.The extraction step uses a Trevisan-based construction chosen to maximize output while limiting seed use.Source: §6 · p. 29
• Theorem 20 gives an [(8h(γ)+δ)n]→[n·ηopt(εs−εSA,εEA)−9 log n] randomness expansion protocol.The generated string has length at least n·ηopt(εs,εEA)−9 log n.Source: §6 · pp. 29–30
• With δ=γ, the required random bits scale as roughly 9γn; 10γn bits suffice for protocol execution with success probability at least 1−e−˜Ω(γ3)n.In expectation, (h(γ)+γ)n+2 bits suffice.Source: §6 · pp. 29–30
• For γ→1, ηopt rates hold against quantum adversaries, are much better than, and are compared with classical-adversary rates in.For small constant γ, Theorem 20 guarantees a constant expansion factor; block grouping can extend linear randomness production to smaller γ choices.Source: §6 · p. 30

7 Open questions

• The rate curves approach and essentially coincide with optimal curves as n increases, but their convergence speed and numerical analysis for n=10^4−10^6 could be improved.The explicit n-dependence is described as close to optimal, and better numerical analysis could make implementations more feasible.Source: §7 · p. 30
• Applying the proof to other Bell inequalities needs a good min-tradeoff bound, preferably using von Neumann entropy directly, but no general technique for such tight bounds is known.Min-entropy bounds are known in many cases, but often yield far from optimal rate curves.Source: §7 · p. 31
• The key-rate optimality claim is limited to the considered protocol structure; whether two-way classical post-processing can achieve better rates remains open.Source: §7 · p. 31

A Summary of Parameters, constants, and variables

• Table 1 is a reference for parameters and constants used throughout the paper.Source: Table 1 · p. 32
• Together, the tables cover constants and parameters as well as the paper’s random variables and quantum systems.Source: Table 1 · p. 32, Table 2 · p. 33
• Table 2 is a reference for random variables and quantum systems used throughout the paper.Source: Table 2 · p. 33

B An improved dependency on the test probability γ

• The appendix applies the entropy accumulation theorem in a slightly different way from the main text.Source: B An improved dependency on the test… · p. 33
• This alternative use yields an entropy rate with better dependency on the test probability γ than Equation (8).Source: B An improved dependency on the test… · p. 33
• The improved entropy rate is used to calculate DIQKD key rates in Section 5.5.2.Source: B An improved dependency on the test… · p. 33

• Each block ends when a test round occurs or when it reaches smax rounds, so blocks can have different lengths but never exceed the cap.The protocol fixes the number of blocks m rather than the number of rounds; the expected round count is m times the expected block length.Source: §B.1 · p. 33
• For each block, the test result is recorded as 0 or 1, while a block without a test is recorded as ⊥, which occurs with probability (1 − γ)^smax.The block’s test is its final round.Source: §B.1 · p. 33
• A test is chosen with probability γ in each round; test and generation rounds use their respective input sets, and Bob’s generation-round output is set to ⊥.The device is used with those inputs and Alice and Bob record their outputs.Source: §B.1 · p. 34
• The parties abort if the sum of block test scores falls below [ωexp(1 − (1 − γ)^smax) − δest] · m.The protocol defines ωexp as the honest implementation’s expected winning probability and δest as the estimation confidence-interval width.Source: §B.1 · p. 34

• The EAT channels Mj combine Protocol 4’s block actions with the device’s quantum channels and satisfy the required conditions.The block-output distribution is over {0, 1, ⊥}, and each output vector can vary in length up to smax.Source: §B.2 · p. 34
• Block output vectors are treated as length smax vectors padded with ⊥, and unperformed rounds do not contribute to their entropy.A round is performed only until a test occurs or the block reaches its maximum length.Source: §B.2 · pp. 34–35
• The block entropy is lower-bounded by summing single-round entropy bounds, with each round’s winning probability constrained by the block channel.The optimization considers distributions with probability mass on 0 and 1 totaling 1 − (1 − γ)^smax.Source: §B.2 · pp. 34–35
• The minimum in the tradeoff-function optimization is attained when all ωi are equal, yielding a block bound equal to expected block length times the one-round entropy.For smax = 1, this recovers the min-tradeoff function from the main text.Source: §B.2 · pp. 35–36

• The entropy rate is defined per block, and the total entropy is given from that block-level rate.The passage states that the total amount of entropy is then given, but its formula is not included here.Source: §B.3 · p. 36
• Choosing smax = ceil(1/γ) gives better entropy-rate scaling than the main-text rate.Source: §B.3 · p. 36
• The second-order term’s scaling is also characterized approximately for this choice of smax.The supplied passage does not include the approximate scaling expression.Source: §B.3 · p. 36

• The derivation bounds the random total round count N, which is the sum of independent, identically distributed block lengths.The text notes that N is unlikely to be much larger than its expected value.Source: §B.4 · p. 36
• The smooth max-entropy bound is conditioned on N ≤ n̄ + t, and the asymptotic equipartition property uses the maximal length n̄ + t.The modified bound includes a term γ(n̄ + t) plus 2 log 7.Source: §B.4 · p. 37
• Error-correction leakage is bounded by (n̄ + t) · [(1 − γ) h(Q) + γh(ωexp)] + 4 log.Source: §B.4 · p. 37
• The parameter εt is optimized for key rate, and the resulting rates are presented in Figures 5 and 6 of the main text.The leakage term is also modified for the variable-length setting.Source: §B.4 · p. 37