PaperlayerView exact revision on arXiv

Source-linked AI summary

A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography

Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, Stephanie Wehner

arXiv:1210.4359v3quant-ph

TL;DR

The paper asks how the joint guessing probability in a monogamy-of-entanglement game scales under parallel repetition. It develops a parallel-repetition analysis showing exponential decay and applies the result to one-sided device-independent BB84 security, while identifying open questions about the theorem’s scope and concentration behavior.

  • Problem

    The paper investigates how success probability scales when two separated players repeatedly guess a third party’s random-basis measurement outcomes, a question complicated by quantum information and entanglement.

  • Method

    The paper introduces monogamy-of-entanglement games and analyzes their parallel repetition, including games with incompatible measurements and approximate guessing.

  • Results

    For incompatible measurements, pwin(G×n) decreases exponentially in n; the result also supports one-sided device-independent BB84 security with noise tolerance up to 1.5%.

  • Takeaways & Limitations

    The optimal BB84-game winning probability can be achieved without entanglement, and the result yields cryptographic applications including one-sided device-independent BB84 security.

  • Takeaways & Limitations

    It remains open which monogamy-of-entanglement games satisfy strong parallel repetition and whether a concentration theorem holds.

Abstract

from arXiv · show

We consider a game in which two separate laboratories collaborate to prepare a quantum system and are then asked to guess the outcome of a measurement performed by a third party in a random basis on that system. Intuitively, by the uncertainty principle and the monogamy of entanglement, the probability that both players simultaneously succeed in guessing the outcome correctly is bounded. We are interested in the question of how the success probability scales when many such games are performed in parallel. We show that any strategy that maximizes the probability to win every game individually is also optimal for the parallel repetition of the game. Our result implies that the optimal guessing probability can be achieved without the use of entanglement. We explore several applications of this result. First, we show that it implies security for standard BB84 quantum key distribution when the receiving party uses fully untrusted measurement devices, i.e. we show that BB84 is one-sided device independent. Second, we show how our result can be used to prove security of a one-round position-verification scheme. Finally, we generalize a well-known uncertainty relation for the guessing probability to quantum side information.

I. INTRODUCTION

The paper introduces a monogamy-of-entanglement game in which two separated players must jointly guess measurements made by a referee, then analyzes parallel repetition and cryptographic applications. Its results establish exponential decay for repeated games, show that entanglement is unnecessary for optimal BB84-game performance, and support one-sided device-independent BB84 security.

  • Monogamy Game: The game has Alice measure a state in a random basis while Bob and Charlie independently guess the outcome; both must be correct to win.Bob and Charlie prepare the state, retain separate shares, and cannot communicate after preparation.
  • Monogamy Game: Quantum uncertainty limits simultaneous prediction of incompatible measurements, while entanglement monogamy constrains how well both players can share predictive power.A maximally entangled Bob–Alice strategy leaves Charlie to guess randomly and is worse than optimal.
  • Monogamy Game: For the BB84 game, the optimal winning probability can be achieved with classical memory only, without entanglement.The paper contrasts this with a maximally entangled Bob–Alice strategy, whose winning probability is at most 1/2.
  • Parallel Repetition: For incompatible-measurement games, parallel repetition makes the winning probability decrease exponentially in n, including when players may make a small fraction of errors.The repeated game requires both players to guess the entire string of outcomes.
  • Applications: The results support one-sided device-independent BB84 security, where no assumption is made about Bob’s measurement device, and provide a finite-key security analysis.The analysis admits noise up to 1.5%, compared with 11% for standard non-device-independent security.
  • Applications: The BB84 security analysis remains theoretical because it assumes every transmitted qubit is received independently of the measurement basis, and its noise tolerance is lower than standard security.The paper also notes that fully device-independent schemes require a long-distance detection-loophole-free Bell violation.

Position Verification

The paper situates position verification amid classical and quantum impossibility results, then presents a one-round scheme with negligible soundness error and limited operational demands.

  • Setting: Position verification asks a prover to convince two verifiers that he controls a specified position under synchronized timing and communication assumptions.The setting assumes known verifier locations, secure communication, distance-proportional message delivery, and instantaneous local computation.
  • Prior limitations: Classical position verification is impossible against colluding adversaries, and unrestricted pre-shared entanglement also rules out secure quantum schemes.Known quantum impossibility constructions require entanglement resources that scale doubly exponentially in the number of transmitted qubits.
  • Prior limitations: Known secure schemes against unentangled or bounded-entanglement adversaries are either multi-round or require honest parties to manipulate large quantum states.This identifies the operational boundary that the paper’s proposed scheme addresses.
  • Contribution: The paper presents the first provably secure one-round scheme with negligible soundness error using only single-qubit operations by honest parties.It proves security against adversaries sharing entanglement linear in the number of qubits transmitted by the honest parties.
  • Proof framework: The security analysis uses the monogamy-game framework and its extension to entropic uncertainty relations with quantum side information.The relevant post-measurement state includes the measurement outcome X, quantum systems B and C, and basis information Θ.

B. The Schatten ∞-Norm

This section introduces the Schatten ∞-norm and develops operator inequalities used to control sums of positive semidefinite operators through block-matrix and permutation constructions.

  • Norm properties: The Schatten ∞-norm equals the largest singular value, and for positive semidefinite operators it equals the largest eigenvalue.It is also related to the norms of L†L and LL† and behaves predictably under block-diagonal direct sums.
  • Operator inequalities: Lemma 1 transfers the operator inequality A†A ≥ B†B through arbitrary linear maps and then bounds the resulting operators using the norm.The proof applies the inequality after left and right multiplication by L and takes operator norms.
  • Operator inequalities: For positive semidefinite A, A′, B, and B′ with A′ ≥ A and B′ ≥ B, the preceding lemma yields a corresponding inequality for their square roots.For projectors, the square roots can be omitted.
  • Main norm bound: Lemma 2 bounds the Schatten norm of a sum of positive semidefinite operators using their pairwise products.Its proof uses a construction due to Kittaneh, extending a less general result used by Schaffner.
  • Proof construction: The proof constructs block matrices from mutually orthogonal permutations, decomposes XX† into permutation-defined terms, and uses unitary block diagonalization.The norm bound then follows from the triangle inequality and unitary invariance.

C. CQ-States, and Min-Entropy

This section defines classical-quantum states and connects conditional min-entropy to the optimal probability of guessing a classical variable from quantum side information.

  • CQ states: A classical-quantum state has a classical register X distributed according to probabilities and a quantum system B conditioned on X.The system B represents potentially quantum side information correlated with the random variable X.
  • Conditioning: For a predicate λ on X, the notation Prρ[λ(X)] denotes its probability, while ρXB|λ(X) denotes the state conditioned on that event.These definitions support later conditioning on events involving classical outcomes.
  • Guessing probability: The conditional min-entropy of X given B is expressed through the maximum probability that a measurement on B correctly guesses X.The optimization ranges over all POVMs indexed by possible values of X.
  • Classical side information: With additional classical side information Θ, the guessing strategy may choose a POVM on B depending on Θ.The corresponding conditional min-entropy is evaluated for the state including Θ.
  • Entropy properties: The min-entropy chain rule lower-bounds Hmin(X|BY) by Hmin(X|B) minus log |Y|.The bound applies when Y is classical and ranges over a finite set.

III. PARALLEL REPETITION OF MONOGAMY GAMES

The section formalizes monogamy-of-entanglement games, their strategies and winning probabilities, and the distinction between independent repetition and general strategies for the repeated game.

  • Game definition: A monogamy game consists of a finite-dimensional system for Alice and a finite list of measurements indexed by a basis or question θ.The outcome set X and question set Θ are finite.
  • Parallel repetition: The n-fold parallel repetition measures tensor-product systems with tensor-product measurement operators across the n coordinates.The repeated construction is itself a monogamy game.
  • Strategies: A strategy specifies a tripartite state and, for each θ, POVMs for Bob and Charlie; pure strategies use pure states and projective measurements.Bob’s and Charlie’s Hilbert spaces may be arbitrary finite-dimensional spaces.
  • Parallel strategies: The repeated strategy obtained by independently repeating a single-game strategy is only one possible strategy for the repeated game.General repeated-game strategies may use an arbitrary joint state across all Alice systems and Bob and Charlie’s systems.
  • Winning probability: The winning probability is the chance that Alice’s, Bob’s, and Charlie’s outcomes agree, maximized over all strategies.Alice chooses θ uniformly, while Bob and Charlie apply their respective θ-dependent POVMs.
  • Strategy reduction: The analysis can restrict attention to pure strategies using purification and Neumark dilation arguments.This reduction replaces mixed states and general POVMs with pure states and projective measurements without changing the relevant optimum.

A. Strong Parallel Repetition for GBB84

For GBB84, the paper proves strong parallel repetition: repeating an optimal single-round strategy independently achieves the optimal n-round winning probability. The proof bounds cross-basis overlaps by the Hamming distance between basis strings and applies this bound to all strategies.

  • The paper analyzes the BB84 monogamy game GBB84 and its n-fold parallel repetition.
  • The single-round strategy prepares a fixed state and has both guessers predict outcome 0 independently of Alice’s basis.Repeating this strategy n times supplies the lower bound for the parallel game.
  • 2^-t bounds the relevant projector overlap when two basis strings differ in t positions, independently of the players’ strategy.The bound follows because the BB84 bases are mutually diagonal on each differing qubit.
  • Bitwise-XOR permutations equalize the Hamming distances between basis strings and their permuted versions, minimizing the resulting upper bound.
  • The resulting upper bound applies to every pure strategy, completing the proof that the repeated single-round strategy is optimal.

B. Arbitrary Games, and Imperfect Guessing

The paper extends the analysis from GBB84 to arbitrary finite-dimensional monogamy games and to games where both guessers may make errors. These extensions yield bounds governed by measurement overlap and permitted-error structures.

  • Arbitrary games: The general monogamy-game framework allows arbitrary finite-dimensional systems, measurement families, and outcome sets.
  • Imperfect guessing: The framework also permits imperfect guessing, replacing exact agreement with error-tolerant winning conditions.
  • Arbitrary games: The generalized proof uses permutations whose Hamming distance from each input is constant, then substitutes their counts into the norm bound.
  • Imperfect guessing: For binary measurements, acceptance is defined by Hamming-distance thresholds d(x,y) ≤ γn and d(x,z) ≤ γ′n.

IV. APPLICATION: ONE-SIDED DEVICE-INDEPENDENT QKD

The paper applies the monogamy-game result to entanglement-based BB84 and proves security even when Bob’s measurement device is arbitrary and potentially malicious. The proof converts Eve’s guessing strategy into a monogamy-game strategy and derives an asymptotic noise tolerance.

  • The entanglement-based BB84 variant delays Bob’s measurement until Alice reveals the basis, and its security implies security for standard BB84 in the one-sided device-independent setting.
  • E-QKD exchanges n qubits, samples t positions for parameter estimation, leaks s error-correction bits, and outputs an ℓ-bit hashed key tolerating error γ.
  • Theorem 5 states security for E-QKD with an arbitrary Bob measurement device, under the restriction that the device does not communicate with Eve after receiving Alice’s signals.
  • With optimal error correction, the asymptotic security error can be negligible when γ ≤ 0.015, corresponding to a noise tolerance of up to 1.5%.The paper notes that a six-state protocol can improve this slightly.
  • The security proof models Eve as measuring her system after learning the basis and sample, then applies the parallel BB84 game to bound her ability to guess Alice’s raw key.Bob’s measurement outcome being close to Alice’s forces Eve’s guessing probability to remain limited.

V. APPLICATION II: A ONE-ROUND POSITION-VERIFICATION SCHEME

The paper constructs a one-round position-verification protocol using single-qubit operations and proves exponentially small soundness error under bounded pre-shared entanglement. The proof reduces successful cheating to the parallel BB84 monogamy game.

  • Parallel repetition gives the one-round scheme exponentially small soundness error against adversaries holding no entangled state when they receive their inputs.
  • The protocol sends an n-qubit BB84 state and its basis to a claimed position, where the prover measures immediately and returns an n-bit string.
  • Honest verifiers accept when the returned string arrives at the expected time and equals the prepared string, with certainty in the noiseless setting.
  • Unbounded entanglement cannot be allowed: n shared EPR pairs already suffice to break this specific scheme.
  • The security proof represents a cheating adversary’s initial operation as an input-independent isometry that distributes systems to the two dishonest parties.After the basis is revealed, each party measures its share and returns a guess.
  • Theorem 3 bounds the adversaries’ success because passing the verification test requires winning a restricted parallel BB84 game.
  • The scheme remains secure against a linear amount of pre-shared entanglement, with exponentially small soundness for at most αn entangled qubits, for example α = 0.2.The paper also extends the result to noise-tolerant acceptance with weaker parameters.

VI. APPLICATION III: ENTROPIC UNCERTAINTY RELATION

The paper generalizes an entropic uncertainty relation from classical to quantum side information for measurements in randomly chosen bases. It also shows that, with multiple measurements, the resulting uncertainty bound need not scale linearly and has limited cryptographic applicability.

  • Background: A party maximally entangled with the measured system can always guess the measurement outcome using an appropriate measurement, so no non-trivial state-independent entropy bound holds in general.A related result applies when two disjoint quantum memories are considered.
  • Generalization: Theorem 8 generalizes the uncertainty relation in (13) to quantum side information for an arbitrary tripartite state and two POVMs.The measurement choice Θ is a uniformly random bit, and the quantities are evaluated on the post-measurement state.
  • Generalization: For n uniformly random measurements, the resulting bound guarantees only one bit of uncertainty.The paper states that an adaptation of the proof of Theorem 8 yields this bound.
  • Limitation: The bound can be approximately achieved by a state maximally entangled between A and B with probability 1/2 and between A and C otherwise.This construction makes both conditional min-entropies low, preventing a stronger result from being expected.
  • Limitation: Unlike the classical-side-information setting, the quantum-side-information bound does not scale linearly in n.The paper contrasts this restriction with uncertainty relations for classical side information and notes limited applicability to quantum cryptography.

VII. CONCLUSION

The paper introduces monogamy-of-entanglement games and establishes parallel-repetition results, including a BB84 example where non-entangled strategies are optimal. It identifies open questions about strong repetition, concentration, noise tolerance, and channel losses in the applications.

  • Main results: The paper introduces monogamy-of-entanglement games and proves a general parallel repetition theorem.For a BB84-based example, it also proves strong parallel repetition and sufficiency of a non-entangled optimal strategy.
  • Open questions: Which monogamy-of-entanglement games satisfy strong parallel repetition remains open.
  • Open questions: It remains open whether a concentration theorem holds for parallel repetitions, bounding the fraction of won executions relative to single-execution success.
  • Applications: Increasing the 1.5% noise tolerance obtained for one-sided device-independent BB84 security remains an open problem.The paper notes that this level may be an artifact of the analysis rather than inherent.
  • Applications: Extending the analysis to channel losses is an open direction, expected to yield higher loss tolerance than fully device-independent QKD.

Appendix A: Pure Strategies are Sufficient

The appendix shows that optimizing over pure strategies is sufficient for the game. It obtains this by purifying mixed states and dilating POVMs into projective measurements without changing the winning probability.

  • Reduction to pure strategies: The supremum over strategies is unchanged when restricted to pure strategies.
  • Purification: Purifying ρABC while appending the purifying register to C does not change the game’s winning probability.
  • Projective measurements: POVMs can be converted into equivalent projective measurement strategies by adding an ancillary Hilbert space and a Neumark dilation unitary.The constructed strategy preserves the winning probability of the original strategy.
  • Security application: Security proofs can use a state close to the protocol’s true output state when the security criterion is preserved under the stated closeness bound.The appendix introduces this principle before proving the corresponding lemma for classical-quantum states.
Loading 1210.4359v3…