PaperlayerView exact revision on arXiv

Source-linked AI summary

Device-Independent Conference Keys from Parity-Extended Games

Suvradip Chakraborty, Ronak Ramachandran, Aniruddha Sen

arXiv:2610.01025v1quant-phcs.CR

TL;DR

DI-CKA has largely used multiparty CHSH-type games, leaving open whether richer games—especially pseudo-telepathy games—could support conference keys and whether security could be proved for all N. This paper extends eligible two-player games through Parity-G constructions and reduces security analysis to the underlying game. Its Parity Magic Square instantiation yields an N-player pseudo-telepathy game and a DI-CKA protocol with higher key rate than Parity-CHSH at low noise.

  • Problem

    Known DI-CKA protocols relied on multiparty CHSH-type games, and available techniques for proving security of general N-party games become infeasible as N grows.

    Source: §1 · p. 2

  • Method

    Parity-G extends eligible two-player games to N players while preserving their classical and quantum values, and carries the underlying game’s entropy lower bounds into the N-party security analysis.

    Source: §1.1 · pp. 2–3

  • Results

    The Parity Magic Square game has quantum value 1 and classical value 8/9 for every N; below ≈5% global depolarizing noise, its protocol has higher key rate.

    Source: §2.3 · p. 6, §3.3 · p. 8, The honest strategy · p. 15

  • Takeaways & Limitations

    For this family of protocols, security analysis does not increase in difficulty with the number of parties, unlike general DI-CKA analyses based on larger semidefinite programs.

    Source: §1.1 · p. 3

    A full comparison with N−1 parallel DI-QKD protocols remains future work because the resulting N-party semidefinite programs are essentially infeasible with current techniques.

    Source: §7.1 · p. 27

Abstract

from arXiv · show

Device-independent conference key agreement (DI-CKA) lets a group of parties establish a shared secret key from untrusted quantum devices, with security certified by non-locality. Existing DI-CKA protocols are each built around a single Bell inequality, typically a multiparty variant of the CHSH game. DI-QKD protocols, in contrast, have been built from a much richer landscape of non-local games, and it has remained unclear how to carry this landscape over to the conference setting. We introduce $\textit{Parity-$G$ games}$, which extend any two-player game $G$ to $N$ players, for every $N$, provided $G$ has an optimal strategy in which one player measures Pauli observables. The extension preserves the quantum and classical values of $G$, and the security of the resulting $N$-party protocol follows from an analysis of the two-player game alone. Our framework recovers the Parity-CHSH game of Ribeiro, Murta and Wehner (Phys. Rev. A, 2018) as a special case. Applied to the Mermin--Peres Magic Square Game, it yields a new $N$-player pseudo-telepathy game, the $\textit{Parity Magic Square Game}$, which ideal devices win in every round. We use it to construct the $\textit{first}$ DI-CKA protocol based on a pseudo-telepathy game. We prove the protocol secure against coherent attacks. It produces up to two key bits per round, and at low noise its key rate exceeds that of the DI-CKA protocol based on the Parity-CHSH game.

1 Introduction

DI-CKA had largely relied on multiparty CHSH-type games, leaving open whether a broader range of non-local games could support conference keys and whether security could be proved for all party counts. The paper introduces Parity-G games, reduces their security analysis to the underlying two-player game, and applies the framework to the Mermin–Peres magic square game.

1 Introduction

  • DI-QKD used several non-local games, but known DI-CKA protocols relied on multiparty CHSH variants and none used a pseudo-telepathy game.The authors also identify the challenge of proving security for general N-party games: available SDP methods become infeasible as N grows.Source: §1 · pp. 1–2

1.1 Our contributions

  • For every N ≥2, Parity-G extends eligible two-player games while preserving their quantum and classical values, with an optimal value attainable using copies of the N-party GHZ state.Eligibility requires an optimal strategy in which one player measures Pauli observables on shared EPR pairs.Source: §1.1 · p. 2
  • The Mermin–Peres instantiation gives a new N-player pseudo-telepathy game and the first DI-CKA protocol based on one, producing up to two key bits per round and secure against coherent attacks.The game has quantum value 1 and classical value 8/9 for every N.Source: §1.1 · p. 2
  • The framework recovers the Parity-CHSH game of Ribeiro, Murta and Wehner as a special case and extends to other two-player games.Source: §1.1 · p. 3
  • For every N, convex lower bounds on Alice’s key-output entropy for the underlying two-player game also hold for its Parity-G extension, keeping the security analysis from growing in difficulty with party count.The authors contrast this with general DI-CKA analyses requiring larger NPA-hierarchy semidefinite programs that quickly become infeasible.Source: §1.1 · p. 3
  • At low noise, the Parity Magic Square protocol has a higher key rate than Parity-CHSH under global depolarizing noise, and the advantage persists under local depolarizing noise.With local depolarizing noise, both protocols’ key rates decrease as N increases.Source: §1.1 · p. 3

2 Technical Overview

The overview introduces parity extensions of two-player games, applies the construction to Magic Square, and outlines a conference-key protocol whose security analysis reduces to a two-player game. It reports that the protocol’s relative key rate depends on the noise regime.

2.1 N-Player Parity-Extensions of 2-Player Games

  • For a Pauli game—one with an optimal strategy using shared |Φ+⟩ states and one player’s Pauli measurements—the Parity-G extension preserves its classical and quantum values and entropy guarantees.The paper restricts to Pauli measurements for simplicity, while stating that the results hold more generally.Source: §2.1 · pp. 3–4
  • Measuring the other N−2 parties’ GHZ qubits in the X basis leaves Alice and Bob with |Φ+⟩ or |Φ−⟩ according to those outcomes’ parity; the referee corrects Alice’s output before checking the original game.The correction depends on Alice’s input and whether her measurement anticommutes with Z.Source: §2.1 · p. 4
  • Parity-G is not self-testing for an N-qubit GHZ state: Alice and Bob can play using EPR pairs while the other players output 0.The paper also states that genuine multipartite entanglement is not required to achieve DI-CKA with this game.Source: §2.1 · p. 4

The Parity Magic Square Game

  • The Parity Magic Square Game replaces the two EPR pairs of an optimal Magic Square strategy with two GHZ states, and the referee XORs swap-mask corrections into Alice’s outputs using the two parities and her input.Alice’s three outputs encode her selected row, and the original game checks its parity and agreement with Bob’s intersecting entry.Source: The Parity Magic Square Game · p. 4

2.2 The Conference Key Agreement Protocol

  • Each protocol round is randomly designated as a test round or key round; test rounds use X measurements for the other parties and the optimal MSG strategy for Alice and Bob, while key rounds use Z measurements.The protocol estimates the test-round winning probability and aborts if it is below ωtol; otherwise, the parties perform error correction and privacy amplification.Source: §2.2 · p. 5

2.3 Security analysis and key rates

  • The N-party entropy bound is reduced to a convex combination of two-player MSG entropy bounds, then extended across n rounds against coherent attacks using the Generalized Entropy Accumulation Theorem [MFSR22].The reduction avoids solving the full N-party security problem directly.Source: §2.3 · p. 6

3 Preliminaries

The preliminaries establish the entropy and non-local-game concepts used in the paper, then introduce the Magic Square game, entanglement monogamy, and the DI-CKA security definition.

3.1 Quantum states and entropies

  • The preliminaries define EPR and classical–quantum states, von Neumann and conditional entropy, and min-entropy through Eve’s optimal guessing probability.Source: §3.1 · p. 7
  • Smooth min-entropy optimizes over nearby states and is the entropy variant used to govern randomness extraction.Source: §3.1 · p. 7

3.2 Non-Local Games and Pseudo-Telepathy

  • A non-local game distributes inputs to non-communicating players; pseudo-telepathy means quantum players win with certainty while classical players cannot.Source: §3.2 · pp. 7–8

3.3 The Mermin–Peres magic square game

  • In the Magic Square game, Alice returns an even-parity row and Bob an odd-parity column, matching at their intersection; quantum value is 1, versus classical value 8/9.The perfect quantum strategy uses two EPR pairs.Source: §3.3 · p. 8

3.4 Monogamy of entanglement

  • If a subsystem is maximally entangled with one register, it must be uncorrelated with another register.Source: §3.4 · p. 9

3.5 Security definition for DI-CKA

  • DI-CKA security covers a shared key or abort, bounding unequal party keys on non-abort runs and specifying secrecy relative to Eve’s side information.Source: §3.5 · p. 9

4 Parity Extensions of Two-Player Games.

This section develops Parity-G extensions of two-player games with suitable Pauli strategies, including Parity Magic Square, Parity-CHSH, and some binary constraint system games; Parity Magic Square has a perfect quantum strategy and classical value below 1.

4.1 Two-player games with Pauli strategies

  • The framework requires a strategy using EPR pairs and Alice’s commuting Pauli measurements, with a key input whose observables are Z-type.Bob’s measurements may be arbitrary; the key input yields a computational-basis measurement.Source: §4.1 · p. 10

4.2 The Parity-G game

  • In Parity-G, additional Bobs receive no input and output bits whose parity forms p; the referee relabels Alice’s answer using the strategy’s swap mask before applying G’s winning predicate.The mask records which of Alice’s output bits flip under the Z^p twist.Source: §4.2 · p. 11

4.3 The honest strategy

  • The honest N-player strategy shares k GHZ states and has the same winning probability as S in G, conditioned on every parity p.Parity Bobs measure X, inducing a Z^p twist on Alice’s and B1’s EPR pairs; the mask relabeling restores the output distribution of S.Source: §4.3 · pp. 12–13

4.4 Quantum and classical values

  • Parity-G preserves both the quantum and classical values of G, and carries perfect strategies for pseudo-telepathy games to every N ≥ 2.The honest strategy attains the value of its underlying strategy S, so it is optimal when S is optimal for G.Source: §4.4 · p. 13

4.5 The Parity Magic Square game

  • The Parity Magic Square game is the Parity-G construction instantiated with the Magic Square game and Peres strategy, with mask σ(0, y) = 0 and σ(x, 0) = p1, σ(x, 1) = p2, σ(x, 2) = p1 ⊕ p2 for x ∈ {1, 2}.For N = 2, there are no parity Bobs and the game reduces to the Magic Square game.Source: §4.5 · pp. 14–15
  • The referee can use the ordinary magic-square check after relabeling Alice’s cell value by σ(x, y), since each row has even parity.The general predicate checks parity on a ⊕ σ(x, ·), whereas the alternate check uses a; the passages state these are equivalent.Source: §4.5 · p. 15

The honest strategy.

  • The Parity Magic Square game has quantum value 1 and classical value 8/9, making it a pseudo-telepathy game.The stated honest strategy wins on every input and for every outcome of the parity Bobs.Source: The honest strategy · p. 15

4.6 Further instances

  • The framework recovers Parity-CHSH, whose quantum and classical values are cos²(π/8) and 3/4, respectively; it was defined by.Its mask is σ(x, p) = xp, and Bob’s observables need not be Pauli strings because the twist is on Alice’s side.Source: §4.6 · p. 16
  • A subset of binary constraint system games that admit Pauli strategies can also be extended to corresponding Parity-G games.The passage says these constructions follow a similar argument to the preceding example.Source: §4.6 · p. 16

5 The DI-CKA protocol

The protocol interleaves key and test rounds using two measurement settings. Test-round scores support parameter estimation, while computational-basis measurements in key rounds produce a common string.

5.1 Setup

  • The protocol assumes isolated parties, trusted local randomness, authenticated public broadcast, and devices unable to access Alice and Bob’s classical communication during the protocol.Source: §5.1 · p. 16

5.2 The DI-CKA protocol

  • Key rounds have every party measure Z to obtain raw key bits, while test rounds play the Parity Magic Square game with Alice and Bob’s game inputs and the other Bobs measuring X.Source: §5 · p. 16, §5.2 · p. 17
  • The parties broadcast test data, calculate the empirical winning frequency, abort below the tolerated score, then reconcile and hash keys for correctness and privacy amplification.Source: §5.2 · p. 17
  • For Parity-G protocols, Alice’s key input and the other parties’ computational-basis measurements yield a common string whose security is certified by passing test rounds.Source: §5.2 · p. 17

6 Security proofs for pMSGN-DI-CKA

The security analysis proves correctness and secrecy for the pMSGN-DI-CKA protocol, reducing its entropy analysis to the two-player Magic Square Game and using entropy accumulation to establish secrecy.

6 Security proofs for pMSGN-DI-CKA

  • Theorem 6.2 proves correctness for parameter-estimation tolerances δ in [0, 1/9), bounding key mismatches and abort events.The proof accounts for error-correction failure and parameter-estimation failure when bounding the total error probability.Source: §6 · pp. 18–19
  • The Generalized Entropy Accumulation Theorem applies after the protocol’s round channels are shown to satisfy its non-signaling condition.The secrecy proof combines this condition with the per-round entropy bound and privacy amplification.Source: §6 · pp. 19–20
  • The authors numerically bound pMSG entropy by reducing the N-player problem to the two-player Magic Square Game and solving a constrained semidefinite program with the NPA hierarchy.They report that a closed-form analytical min-tradeoff function is unavailable even for the two-player game.Source: §6 · pp. 20, 22
  • For every N, a convex entropy lower bound for the two-player game G also lower-bounds Alice’s key-output entropy in the corresponding Parity-G game.This reduction lets the security analysis use the underlying two-player game rather than an N-player entropy optimization.Source: §6 · pp. 20–21
  • Theorem 6.9 establishes secrecy for Protocol 1 by combining a per-round entropy bound with the Generalized Entropy Accumulation Theorem and privacy amplification.The secrecy proof applies the Leftover Hash Lemma to convert a smooth min-entropy bound into a secrecy bound.Source: §6 · pp. 19, 22

7 Asymptotic key rate analysis with depolarizing noise

The section analyzes pMSGN key rates under depolarizing noise and compares them with Parity-CHSH. The comparison favors pMSGN in the low-noise regime, while the bounds leave some regimes unresolved.

7 Asymptotic key rate analysis with depolarizing noise

  • In the noiseless setting, pMSGN reaches its maximal rate of 2 bits per round when ωtol = 1, γ = 0, and the shared states are honestly prepared.The section notes that 2 bits per round is the maximum possible for this protocol.Source: §7 · p. 23
  • Under global depolarizing noise, the authors set ωtol to the expected winning probability 1 − q/2 and compute the asymptotic key rate as noise varies.They describe this as a standard noise model that also subsumes noisy player measurements, while noting that their techniques extend beyond depolarizing noise.Source: §7 · p. 23

7.1 Comparison to the Parity-CHSH game

  • For global-noise comparisons, the authors use Figure 3 to show key rate against noise probability q, with the true pMSG rate in a shaded region and some regimes left unresolved.The caption says the middle comparison region is open because the pMSG bounds are not tight.Source: Figure 3 · p. 25
  • The comparison models global depolarizing noise because adversarial state preparation has no dimension bound, making per-qubit noise ill-defined in that setting.The authors also describe local depolarizing noise per qubit and plot key rate for several party counts in Figure 4.Source: §7 · p. 24, §7.1 · p. 25, Figure 4 · p. 26
  • With an honest strategy, the maximal key rate is 2 for pMSGN and 1 for pCHSHN.pMSGN uses two GHZ states in parallel per round in its honest strategy.Source: §7.1 · pp. 25–26
  • pMSGN has improved key rates over Parity-CHSH in the low-noise regime, also improving over N −1 sequential CHSH-based DI-QKD protocols there.The authors leave comparison with parallel CHSH protocols to future work because the required entropy bounds are hard to compute with current techniques.Source: §7.1 · p. 27

A Impossibility of a Multiparty Consensus Magic Square

The literal multiparty Magic Square game cannot be won perfectly for N ≥3, so it is not pseudo-telepathy. This obstruction motivates the paper’s separate test and key bases, while a single-setting consensus construction remains open.

A Impossibility of a Multiparty Consensus Magic Square

  • For every N ≥3, the literal multiparty Magic Square game has quantum value below 1 and is not pseudo-telepathy.The appendix introduces the game by having Alice and all Bobs answer a shared column-consensus predicate.Source: A Impossibility of a Multiparty… · p. 30
  • Perfect play would make each Alice–Bob pair win the bipartite Magic Square game with certainty, forcing the same two-qubit core to be maximally entangled with every Bob.Alice uses the same row measurement for each pair; the self-testing argument rules out independent per-Bob cores.Source: A Impossibility of a Multiparty… · p. 30
  • That requirement contradicts entanglement monogamy: a core maximally entangled with B2 is in a product state with B3, yet perfect play also requires maximal entanglement with B3.The contradiction rules out a perfect strategy and yields the stated quantum-value bound.Source: A Impossibility of a Multiparty… · p. 30
  • The obstruction motivates the two-basis design: a non-consensus certification test and a separate consensus key basis, with test and key rounds required by the Parity-G framework.A genuinely multipartite consensus pseudo-telepathy game that would yield a DI conference key from one measurement setting remains an open problem.Source: A Impossibility of a Multiparty… · p. 30

B The Generalized Entropy Accumulation Theorem

The appendix restates the Generalized Entropy Accumulation Theorem with its constants for reference. It specifies conditions on a sequence of quantum channels and a smooth min-entropy bound for their outputs.

B The Generalized Entropy Accumulation Theorem

  • The theorem considers a sequence of quantum channels M_i satisfying a non-signaling condition expressed through channels R_i.For each M_i, the stated condition requires a channel from E_{i−1} to E_i.Source: B The Generalized Entropy Accumulation… · p. 30
  • It bounds the smooth min-entropy of the outputs A^n conditioned on the final side information E_n.The theorem states this entropy bound for the outputs of the channel sequence.Source: B The Generalized Entropy Accumulation… · p. 31
  • The appendix gives the constants c0 and c1 for an affine min-tradeoff function f, with h defined as the minimum of f(freq(c_n)).The supplied passage also identifies eE_{i−1} as a purifying system and specifies the state domain for the infimum.Source: B The Generalized Entropy Accumulation… · p. 31

C The Magic Square game strategy

The authors analyze an attack on the Magic Square game protocol in which Eve knows Alice’s key while the devices still win above the classical value. The attack’s optimality is unresolved.

C The Magic Square game strategy

  • The attack targets zero entropy for Alice’s key while retaining winning probability ω > 8/9, using the strategy introduced in [AW20].The security analysis focuses on the underlying two-party Magic Square game because the security of pMSG reduces to it.Source: C The Magic Square game strategy · p. 31
  • An attack gives Eve Alice’s entire key while achieving a Magic Square game winning probability of approximately 0.935, above the classical value 8/9.The devices output known bits on key rounds and use the optimal CHSH strategy on the remaining test inputs.Source: C The Magic Square game strategy · p. 31
  • The attack’s optimal winning probability is unknown, although an SDP calculation bounds it above by approximately 0.945.The reported strategy achieves approximately 0.935.Source: C The Magic Square game strategy · p. 31

D The Parallel Parity-CHSH game

The parallel Parity-CHSH construction plays two Parity-CHSH games and requires winning both, reducing the security analysis to two CHSH games in parallel. Its key-rate comparison with pMSG remains unresolved.

D The Parallel Parity-CHSH game

  • The parallel construction plays two pCHSH games and wins only if both are won; its security reduction is to winning two CHSH games in parallel.The passage proposes deriving entropy bounds as a route to analyzing its key rate.Source: D The Parallel Parity-CHSH game · pp. 31–32
  • For parallel Parity-CHSH, the honest strategy shares two GHZ states, and the optimal quantum and classical winning probabilities are approximately 0.7285 and 5/8, respectively.The quantum value is reported as cos^4(π/8) in [Amb26].Source: D The Parallel Parity-CHSH game · p. 32
  • At zero noise, the stated conditional entropies are μ/2 for parallel Parity-CHSH and pCHSH, versus 2μ/3 for pMSG; a finite-round low-noise comparison favors pMSG.The asymptotic case would require separate analysis, and a tight comparison among the three games is left open.Source: D The Parallel Parity-CHSH game · p. 32
  • The parallel game gives M bits only when Alice receives input 0^M, an event with probability 2^-M, so the chance of a valid key round falls exponentially with M.The passage notes that current asymptotic key-rate definitions focused only on valid key rounds may not reflect practical operation.Source: D The Parallel Parity-CHSH game · p. 32
Loading 2610.01025v1…