Device-Independent Conference Keys from Parity-Extended Games

Device-Independent Conference Keys from Parity-Extended Games Suvradip Chakraborty∗

Ronak Ramachandran†

Aniruddha Sen ‡

arXiv:2610.01025v1 [quant-ph] 1 Oct 2026

Abstract 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 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 Parity Magic Square Game, which ideal devices win in every round. We use it to construct the 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

Quantum key distribution (QKD) lets two parties establish a secret key whose security rests on the laws of quantum mechanics [BB84, Eke91]. Standard security proofs assume that the devices behave as modeled, for instance that they prepare and measure qubits in prescribed bases. Real devices deviate from such models, and practical attacks (e.g., [LWW+ 10]) exploit these deviations. Device-independent (DI) QKD, also called fully DI QKD, removes the need to trust the quantum devices and seeks security even when those devices are uncharacterized or supplied by an adversary.1 The parties treat their devices as black boxes, and security follows from the observed input-output statistics alone, through the winning probability of a non-local game [ABG+ 07, AFDF+ 18]. Vazirani and Vidick proved that a slightly modified version of Ekert’s protocol, which is based on the CHSH game [CHSH69, Eke91], is secure in this fully deviceindependent setting [VV14]. DI-QKD has since been built on several other games, including generalized CHSH inequalities [SBV+ 21], the Mermin–Peres magic square game [ZMZ+ 23], and, more broadly, on the class of monogamy-of-entanglement games [CMT25]. The choice of game determines what the test certifies and how much key each round yields. Conference key agreement (CKA) generalizes QKD to N parties who wish to establish a common secret key. When the parties share a multipartite entangled state such as the GHZ ∗

Visa Research. suvchakr@visa.com UT Austin. ronakr@utexas.edu (Work done while at Visa.) ‡ UT Austin. aniruddhasen@utexas.edu (Work done while at Visa.) 1 Fully DI QKD trusts neither the sources nor the measurement devices. Measurement-device-independent QKD [LCQ12, BP12] trusts the sources but not the measurements, and one-sided DI QKD [BCW+ 12] trusts one party’s devices. †

1

state, a single measurement round gives all of them the same key bit. In some network topologies, this yields higher key rates than running N −1 two-player QKD protocols [EKMB17, MGKB20]. DI-CKA has received much less attention than DI-QKD. Ribeiro, Murta and Wehner [RMW18] gave the first fully DI-CKA protocol, based on the Parity-CHSH game, an N -party extension of the CHSH game [CHSH69]. Subsequent work designed a genuinely multipartite Bell inequality for DI-CKA [HKB20] and derived entropy bounds and key rates for multiparty DI protocols [GMKB21, GMKB23]. Wooltorton et al. recently showed that DI-CKA does not require genuine multipartite entanglement [WBC25]. Each of these protocols relies on a multiparty generalization of the CHSH inequality, such as the Parity-CHSH inequality [RMW18] or the genuinely multipartite generalization of CHSH by Holz et al. [HKB20]. To our knowledge, DI-CKA protocols based on other non-local games are not known. In particular, none is based on a pseudo-telepathy game, that is, a game quantum players can win with certainty while classical players cannot [BBT05]. Such games seem attractive for DI cryptography, since malicious devices cannot afford to lose even a single game in the ideal noiseless setting. We have concrete evidence of such an advantage in the two-party setting: DI-QKD based on the magic square game, a pseudo-telepathy game, indeed yields more key per round than CHSH-based DI-QKD at low noise [ZMZ+ 23]. This prompts the following question: Question 1: Would a DI-CKA protocol based on a pseudo-telepathy game outperform existing protocols? There are many obvious first choices for such an N -party pseudo-telepathy game: the N player GHZ game or parallel two-player magic square games2 , for instance. The central difficulty, however, is proving security for such a protocol by upper-bounding the information that an adversary Eve can learn about the conference key the players are attempting to share. Unfortunately, the only known techniques for doing so require solving computationally intensive semi-definite programs [NPA07, BFF24] that become infeasible for N even slightly larger than 2 and do not say anything about asymptotic behavior as N increases. Holz, Kampermann, and Bruß [HKB20], for instance, are unable to prove any security guarantees on their N -party game or proposed DI-CKA protocol for more than 4 parties. This leads to the following question: Question 2: Is there a general way to construct N -party DI-CKA protocols with provable security for all N ?

1.1

Our contributions

We answer both questions affirmatively. Our main contributions are the following. • Parity-G games. For every two-player game G with an optimal strategy in which one player measures Pauli observables on shared EPR pairs (Definition 4.2), we define an N player game pGN , the parity extension of G (Definition 4.5). For every N ≥ 2, pGN has the same quantum and classical values as G (Theorem 4.11), and its optimal value can be attained given copies of the N -party GHZ state (Proposition 4.10). • DI-CKA protocols based on Parity-G games. We instantiate our Parity-G games framework with the Mermin–Peres magic square game in particular, obtaining the Parity Magic Square game pMSGN (Definition 4.13), which is a new N -player pseudo-telepathy game with quantum value 1 and classical value 8/9 for every N (Propositions 4.15 and 4.16). From it we construct the first DI-CKA protocol based on such a game, which produces up to two key bits per round, and we prove its security against coherent attacks (Sections 5 2

See Page 26 for a discussion of DI-CKA protocols based on performing pairwise DI-QKD protocols in parallel.

2

and 6). Applied to the CHSH game, our Parity-G framework also recovers the ParityCHSH game of Ribeiro, Murta and Wehner [RMW18] as a special case (Example 4.18), capturing the DI-CKA protocol based on it, and extends to other two-party games as well. • Reduction of security to the two-party game. A major benefit of our framework is that the security of the N -party protocol reduces to that of the underlying two-party game G: every convex lower bound on the entropy of Alice’s key output that holds for G also holds for pGN , for every N (Lemma 6.6). This provides us with a family of DI-CKA protocols, based on Parity-G games, in which the security analysis is relatively simple and does not increase in difficulty with the number of parties. This gives us an important advantage over the current best techniques for analyzing the security of general DI-CKA, which require solving much larger semi-definite programs via the NPA hierarchy [NPA07, BFF24] that quickly become infeasible for N even slightly larger than 2, and do not give any asymptotic guarantees. • Key rates. We compare the asymptotic key rates of the DI-CKA protocols based on pMSGN and on the Parity-CHSH game under depolarizing noise (Section 7). Under global depolarizing noise, our protocol based on pMSGN achieves a higher key rate in the low noise regime. Conversely, to show the tightness of our analysis, we also give an attack, adapted from [AW20], under which an adversary learns Alice’s entire key while the devices are able to win pMSGN with probability up to 95 + 49 cos2 (π/8) ≈ 0.935 (Appendix C). When this attack is combined with [LBJF+ 23], it yields an upper bound on the key rate. We also consider a local depolarizing noise model, where an advantage again persists for pMSGN at low noise, though the key rates of both protocols decrease as N increases.

2

Technical Overview

Our technical overview is divided into three parts: an intuitive explanation of parity-extensions of 2-player games, an overview of our device-independent protocol for quantum conference key agreement based on the parity-extension of the Mermin–Peres Magic Square Game, and finally an analysis of key rates for this new protocol.

2.1

N -Player Parity-Extensions of 2-Player Games

Optimal quantum strategies for 2-player non-local games often require players to share the state 1 Φ+ := √ (|00⟩ + |11⟩). 2 In many cases, however, replacing that state with 1 Φ− := √ (|00⟩ − |11⟩) = (Z ⊗ I) Φ+ 2 without Alice and Bob knowing has a very predictable effect on player outputs. In particular, because |Φ− ⟩ is just |Φ+ ⟩ with a Z gate locally applied to Alice’s qubit, if all of Alice’s possible measurements commute or anticommute with Z—for instance, if her measurements are Paulis3 —then performing her measurements on |Φ+ ⟩ is equivalent to performing them on |Φ− ⟩ and flipping the outcome if the measurement anticommutes with Z. We call a 2-player non-local game a Pauli game if it has an optimal quantum strategy where parties share copies of |Φ+ ⟩ and one party applies only Pauli measurements to their shares. 3 Paulis are a strict subset; every basis along the equator of the Bloch sphere anticommutes with Z. Throughout this paper, we only restrict to Paulis for simplicity, but the results hold more generally.

3

In Section 4 we show that any Pauli game G can be extended to an N -player non-local game Parity-G that inherits the classical/quantum winning probabilities and entropy guarantees of the 2-player game. Almost every known 2-player non-local game is a Pauli game, so this technique is very general. Parity-CHSH is one special case. The key insight enabling N -player parity-extensions of Pauli games is that if all but 2 of N players measure their qubit of a shared N -party GHZ state in the X basis, the remaining two players—say Alice and Bob—will share |Φ+ ⟩ or |Φ− ⟩, and which state they share will depend sensitively on every measurement outcome of the N −2 others. In particular, Alice and Bob will share √12 (|00⟩ + (−1)p |11⟩), where p ∈ {0, 1} is the parity of the N − 2 measurement outcomes. Alice and Bob can then use their shared state to play any Pauli game, so long as the referee flips Alice’s raw output appropriately based on p and Alice’s input (which determines whether her measurement will anticommute with Z) before evaluating the game’s winning condition. Notably, the players other than Alice and Bob receive no input4 . In fact, the new N -party game can be won by simply having Alice and Bob independently play the 2-player game using shared copies of |Φ+ ⟩, while all other players output 0, so this game is not self-testing for an N -qubit GHZ state. Consistent with [WBC25], our game also does not require genuine multipartite entanglement to achieve DI-CKA. As we’ll see, all ability to arrive at shared bits of key comes from the tension between playing this game during test rounds and passing the error correction step of our protocol. The Parity Magic Square Game Our DI-CKA protocol relies on the N -player parityextension, pMSGN , of the 2-player Mermin–Peres Magic Square Game, MSG. In MSG, Alice and Bob claim to have some 3 × 3 grid of 0’s and 1’s where the rows have an even number of 1’s and the columns have an odd number of 1’s. To check this claim, the referee asks Alice for the 3 entries in one row and Bob for the 3 entries in one column. The players win if Alice’s entries have an even number of 1’s, Bob’s have an odd number of 1’s, and Alice and Bob agree on the entry where their row and column intersect. This game is a Pauli game, since an optimal quantum strategy exists where Alice and Bob share two copies of |Φ+ ⟩ and Alice makes only Pauli measurements on her two qubits, as shown in Figure 1. a0

a1

a2

x=0

I⊗Z

Z ⊗I

Z ⊗Z

x=1

X ⊗I

I⊗X

X ⊗X

x=2

−X ⊗ Z

−Z ⊗ X

Y ⊗Y

Figure 1: Alice’s Pauli measurements for outputs a0 , a1 , a2 ∈ {0, 1} on input x ∈ {0, 1, 2}. In one optimal quantum strategy for pMSGN , the two |Φ+ ⟩ states are replaced by two GHZ states. Let p0 and p1 be the parities of the X basis measurement outcomes of the players other than Alice and Bob for the first and second GHZ state respectively. To modify the winning condition of MSG to work for pMSGN , Alice’s raw outputs must be flipped if p0 is 1 and her measurement anticommutes with Z on the first qubit, and again if p1 is 1 and her measurement anticommutes with Z on the second qubit. In other words, before checking the winning condition of MSG, the referee must XOR the bits specified in Figure 2 into each of Alice’s three outputs a0 , a1 , a2 ∈ {0, 1} depending on her input x ∈ {0, 1, 2}. We call this table of correction bits the swap mask of pMSGN . By hard-coding these corrections into the winning condition, we will have fully specified the game. 4 Thus, unlike other N -party non-local games that require non-signaling between all N 2 pairs of players, Parity-G games only require non-signaling between N − 1 pairs (Alice and everyone else), which is quadratically easier to enforce.

4

a0

a1

a2

x=0

0

0

0

x=1

p0

p1

p0 ⊕ p 1

x=2

p0

p1

p0 ⊕ p 1

Figure 2: The referee’s corrections to Alice’s outputs for pMSGN .

2.2

The Conference Key Agreement Protocol

Now, we show how to construct a conference key agreement protocol based on pMSGN . This protocol extends to Parity-G games as well, but for ease of exposition we focus on just analyzing the protocol with pMSGN . We give an overview here, and the protocol is more formally described in Section 5. Consider N parties A, B1 , B2 , ..., BN −1 where the first two parties play distinguished roles, and are referred to as Alice (A) and Bob (B1 ). Since we are in the device independent setting, let us assume some (untrusted) multipartite quantum state ρ is shared between all the players. Broadly, we divide the protocol into m rounds, with each round being designated as a test round with probability γ and a key round with probability 1 − γ. The players do the following. • In key rounds, all players ask their devices to measure their state in the Z basis. • In test rounds, the players B2 , ..., BN −1 ask their devices to measure their state in the X basis. Alice and Bob ask their devices to perform measurements according to the optimal quantum strategy of MSG. Combined, this is the optimal winning strategy for pMSGN , as described in the last section. After all the rounds have been completed, the players first do a parameter estimation step, in which they publicly communicate their test-round outcomes, which allows them to calculate their average winning probability over multiple rounds of pMSGN . If the winning probability ω is below some predetermined threshold ωtol , they abort the protocol. If not, they carry out an error correction and privacy amplification step to verify they all received the same raw key bits in the key rounds, and to extract fully secret bits of key from their raw key bits. Clearly, if the devices behaved honestly and shared a tensor product of two GHZ states with the players, they would get bits of key. But why should we expect this protocol to be secure? Intuitively, the security of this protocol mainly comes from the observation that the devices are unable to distinguish key rounds and certain test rounds. In particular, Alice’s device can’t distinguish between the case where it is a key round, or the case when her test round input for MSG is 0 (which is the first row). Both of these cases correspond to Alice’s device being asked to measure Z ⊗ I and I ⊗ Z. Also note that the designation of each round is probabilistically chosen. So, in order to pass the winning condition on the test rounds, the devices are forced to play honestly and report correct measurement outcomes. Thus, on key rounds they are forced to do the same as well. Note that in order to just win on the test rounds, the devices could just share a tensor product of two EPR pairs with Alice and Bob, and have the other players just output 0. This ensures Alice and Bob get bits of secret key, but the other players do not. However, this is noticed by the players in the error correction step and the protocol is aborted. Thus, the devices are forced to act honestly in order to pass both these checks.

2.3

Security analysis and key rates

There are two parameter choices the players have when carrying out the above conference key agreement protocol: ωtol , the tolerated winning probability, and γ, the test-round probability. 5

Let us start by considering the security of a particular round – in particular we will just focus on setting ωtol . The ideal winning probability of pMSGN is 1, but we will often wish to set ωtol < 1, since there may be noise in the quantum channels that brings the winning probability down. Fortunately, it turns out that we can still get bits of secret key depending on how far below 1 we set ωtol . Note that we must still set ωtol > 8/9 to get any non-zero bits of key, since it is known that classical adversaries (the devices) can win pMSGN deterministically with winning probability 8/9, so their winning strategy or reported measurement outcomes could be pre-decided by an adversary Eve. In fact, we show that we need ωtol ≳ 0.935, since a better quantum strategy exists for the devices, as we show in Appendix C. We formally prove the per round security of the above protocol by lower bounding the per round conditional von Neumann entropy H(A|E) of Alice’s key bitstring, over all possible shared states and measurement strategies which can be devised by Eve (who we assume constructs the untrusted devices), such that she succeeds with probability ≥ ωtol on pMSGN . Intuitively, this just lower bounds how many bits of secret key Alice is expected to get per round as a function of ωtol , so for us 0 ≤ H(A|E) ≤ 2. No known analytical solution for this exists, so we resort to using numerical techniques which involve solving semi-definite programs (SDPs) via the NPA hierarchy [NPA07, BFF24], to calculate a lower bound. It is often challenging to calculate such lower bounds in device-independent protocols [BFF24], especially if the number of players is large, since this makes the size of the SDPs blow up. However, we get around this problem for our protocol by showing a reduction of the security of the N -party pMSGN to the two party MSG, by Lemma 6.6. The proof relies on expressing the entropy lower bound of pMSGN as a convex combination of entropy lower bounds of all possible MSG games Alice and Bob could be playing (up to a relabeling of their inputs) in the test rounds. Significantly, this technique generalizes to Parity-G games, which provides a new framework for proving security of a large family of conference key agreement protocols by reducing to the much simpler security bound of just 2 party games. Finally, we extend our security over all n rounds against coherent attacks (the protocol has n rounds and N parties), by appealing to the Generalized Entropy Accumulation Theorem [MFSR22]. We refer to Section 6 for our precise formulation and proofs. Key rates We evaluate our protocol by analyzing its asymptotic key rate. The key rate r∞ = H(A|E) − H(A|B) quantifies the average number of key bits we get each round over all rounds, when setting the test round probability γ → 0 as the number of rounds increases. It is a function of ωtol , and accounts for both the entropy lower bound when ω < 1, and the security loss in the error correction step. We mainly compare our conference key agreement protocol based on pMSGN with the work of [RMW18], whose protocol is based on the Parity-CHSH game. As the name suggests, our framework of Parity-G games captures the Parity-CHSH game, as explained in Example 4.18, roughly since it can be expressed as a suitable N -party extension of the CHSH game. Moreover, we show that our protocol based on pMSGN achieves strictly better key rates in the low noise regime. Note that r∞ can be expressed as a function of noise since it influences the expected winning probability ω of our N -party games, and we set the threshold ωtol accordingly. For instance, our protocol achieves higher key rate when the global depolarizing noise probability q is below ≈ 5%; also when the local depolarizing noise probability is below ≈ 1.5%, setting the number of parties N = 3. Conversely, our protocol has lower key rate when q ≳ 10%. Both protocols exhibit zero key rate when q ≳ 14%. We calculate both lower and upper bounds on key rates for both protocols to show the gap in tightness of our comparison. We refer to Section 7 for a detailed explanation of our techniques and comparison between key rates of both protocols.

6

3

Preliminaries

3.1

Quantum states and entropies

We assume the reader is familiar with quantum information essentials. For a primer on quantum states and measurements, see [NC00]. We briefly introduce some useful definitions and notation regarding states and entropies. • The canonical Bell state or EPR pair is defined as |Φ+ ⟩ = √12 (|00⟩ + |11⟩), the other Bell states are |Φ− ⟩ , |Ψ+ ⟩ , |Ψ− ⟩. P • A classical-quantum state is defined as a state ρKE = x∈X |x⟩ ⟨x| ⊗ ρE,x where E is a quantum system and X is a classical alphabet. • The von Neumann entropy of a state ρ is defined as H(A)ρ = − Tr(ρA log ρA ). • The conditional von Neumann entropy of a bipartite state ρAB is defined as H(A|B)ρ = H(AB)ρ − H(B)ρ . • The min-entropy of a classical-quantum state ρKE isP defined as Hmin (K|E)ρ = − log2 (pguess (K|E)), where pguess (K|E) = max{Mk } k Tr(Mk ρkE ) is the optimal probability of guessing the classical bitstring K by measuring the state ρE . ε (K|E) = • The smooth min-entropy of a classical-quantum state is defined as Hmin ρ ′ supρ′ Hmin (K|E)ρ′ , where the supremum is over ε-close states ρ in terms of their purified p distance 1 − F (ρ, ρ′ )2 ≤ ε, where F (ρ, ρ′ ) denotes the fidelity between ρ and ρ′ . This is the variant of min-entropy we will mainly be using throughout the paper, since it governs randomness extraction.

• The min-tradeoff function is a function which lower bounds the conditional von Neumann entropy of a particular non-local game, as a function of its winning probability.

3.2

Non-Local Games and Pseudo-Telepathy

Informally, non-local games are collaborative games where players that cannot communicate with each other receive inputs from a referee and must return satisfactory outputs to the referee. ⃗ V ) has finite Definition 3.1 (Non-local game). An N -player non-local game G = (π, X⃗ , A, ⃗ input sets Xj , output sets Aj , an input distribution π on X = X1 × · · · × XN , and a predicate ⃗ → {0, 1}. A referee samples ⃗x ∼ π, sends xj to player j, each player outputs aj V : X⃗ × A without communicating with the others, and all players win together iff V (⃗x, ⃗a) = 1. Preventing communication between players is crucial, since communicating players could trivially win any such game. In practice, non-communication is enforced by placing players far enough apart that signals, which are limited by the speed of light, cannot travel between players before the game ends. This is why we call such games non-local —players are separated from each other. Since communication must be prevented between every pair of players, the difficulty of preventing communication scales as N 2 , becoming more demanding as N grows. Every quantum strategy for a non-local game is defined by a shared quantum state and inputdependent observables (POVMs) that players can apply to their part of the state5 . The classical and quantum values of a non-local game G, denoted ωC (G) and ωQ (G), are the maximum possible winning probabilities of classical and quantum strategies respectively. Because classical strategies are a strict subclass of quantum strategies where players can only share randomness instead of quantum states, ωC (G) ≤ ωQ (G). 5

In this paper we will restrict to local observables rather than more general commuting observables.

7

What makes non-local games interesting is that quantum players can win some games with strictly greater probability than classical players by using entanglement to correlate their outputs in ways that classical players cannot. For this reason, winning such a game with much higher probability than ωC (G) can certify that players shared some highly entangled state. Games which certify a specific state are called self-testing [MY04]. Games where the optimal quantum strategy succeeds with certainty, called pseudo-telepathy games, can be especially powerful, since losing a single game certifies non-classicality. Definition 3.2 (Pseudo-telepathy). G is a pseudo-telepathy game if ωQ (G) = 1 > ωC (G).

3.3

The Mermin–Peres magic square game

Here, we introduce a well-known non-local game known as the Magic Square game or MSG; it will be useful in our construction of a multiparty game later on. We also give brief proofs of its optimal classical and quantum winning strategies. Definition 3.3 (Magic Square game, MSG). This is a non-local game played between two players, Alice and Bob. Alice and Bob both receive inputs x, y respectively from the set {0, 1, 2}. We assume their inputs are uniform random and independent. They each output two vectors a = (a0 , a1 ) and b = (b0 , b1 ); then set a2 = a0 ⊕ a1 , b2 = b0 ⊕ b1 ⊕ 1. They win iff ay = bx . For intuition, it is useful to think of a strategy for this game as a 3 × 3 matrix M , where Alice and Bob’s inputs are a row and column index of the matrix. They have to output an even parity row and odd parity column respectively, and they win iff their intersecting cell has the same value. Proposition 3.4 (Classical value of MSG). ωC (MSG) = 8/9. Proof. Consider Alice and Bob’s classical strategies as a matrix. By convexity, it suffices to restrict to deterministic strategies x 7→ a(x) , y 7→ b(y) . For a strategy which wins over all possible (x) cells that can appear at the intersection of Alice and Bob’s output, the matrix Mxy := ay would (x) (y) need Lrows (Alice even) gives L to have ay = bx for all x, y. However, summing all entries by x,y Mxy ≡ 1 + 1 + 1 ≡ 1. x,y Mxy = 0, while summing all entries by columns (Bob odd) gives This results in a contradiction. Hence, at least one of the nine equally likely cells is lost, so ωC ≤ 8/9. Thus, such a strategy attains 8/9, and it is not possible to improve on this, which we can simply check by enumerating all such possible matrices. The quantum strategy uses the Peres square of two-qubit ±1 observables

(Pxy ) =

I⊗Z X ⊗I −X ⊗ Z

Z ⊗I I⊗X −Z ⊗ X

Z ⊗Z X ⊗X Y ⊗Y

(1)

(x = row, y = column). Lemma 3.5 (Peres relations). In (1), the three observables in each row commute and multiply to + I ⊗ I; the three in each column commute and multiply to − I ⊗ I. Proof. Commutation is checked by counting anti-commuting tensor factors (an even number implies that the observables commute). This can be verified by a straightforward calculation. Proposition 3.6 (Quantum value of MSG). ωQ (MSG) = 1. This is achieved by a strategy ⊗2 using two EPR pairs |Φ+ ⟩ : Alice measures the row-x observables of (1), Bob the conjugated column-y observables. 8

Proof. By Lemma 3.5, Alice’s row product is +I, so her three outcomes have even parity; Bob’s conjugated column product is −I, giving odd parity. We can check consistency of outputs on the intersecting cell by the ricochet identity (M ⊗ I) |Φ+ ⟩ = (I ⊗ M T ) |Φ+ ⟩, also using P = P T for ⊗2 ⊗2 a Hermitian P , which are their observables, gives us the identity (Pxy ⊗ Pxy ) |Φ+ ⟩ = |Φ+ ⟩ , so the measurement outcomes of their observables satisfy ay = bx with probability one.

3.4

Monogamy of entanglement

Lemma 3.7 (A pure subsystem factorizes off). If a bipartite state |ψ⟩XY and its subsystem state ρX = TrY |ψ⟩⟨ψ| are both pure states, then |ψ⟩ = |u⟩X ⊗ |w⟩Y . P √ Proof. ConsiderPthe Schmidt decomposition |ψ⟩ = k pk |uk ⟩ |wk ⟩. Then, clearly the subsystem ρX = k pk |uk ⟩⟨uk | is pure iff some pk0 = 1, which implies |ψ⟩ is a product pure state. Lemma 3.8 (Maximal entanglement is monogamous). Let |ψ⟩ABC be a pure state and suppose HA = HA0 ⊗ HA1 such that ρA0 B is a maximally entangled pure state between the two registers. Then, register A0 must be uncorrelated with C. Proof. Since ρA0 B is a pure state, we can apply Lemma 3.7 across the cut (A0 B | A1 C). So, we can write |ψ⟩ = |ϕ⟩A0 B ⊗ |ζ⟩A1 C . Then, it must be true that ρA0 C = ρA0 ⊗ ρC , thus the entanglement between A0 and C is zero. In other words, if a two-qubit subsystem A is maximally entangled with register B then it must share no entanglement with another register C.

3.5

Security definition for DI-CKA

Definition 3.9 (DI-CKA security [RMW18]). An N -party DI-CKA protocol outputs a key K ∈ {0, 1}ℓ for all parties, or ⊥. It is ε-secure if: (i) Correctness (εcor ): Pr[no abort ∧ ∃i ̸= j : Ki ̸= Kj ] ≤ εcor ; (ii) Secrecy (εsec ): conditioned on no abort, 12 ρKE − τK ⊗ ρE 1 ≤ εsec , with τK maximally mixed and E the adversary’s quantum side information including the public transcript, and ε = εcor + εsec .

4

Parity Extensions of Two-Player Games.

In this section we introduce Parity-G games, an N -player extension of a two-player non-local game G. The construction applies to every G that has a suitable Pauli strategy. We develop the general framework in Sections 4.1–4.4, and instantiate it with the Magic Square game in Section 4.5. There may also be various other potential paths to designing a multiparty game based on two-party games for conference key agreement. We motivate our Parity-G framework by showing in Appendix A why a certain natural extension, for the Magic Square game in particular, cannot be used as a basis for a conference key agreement. This informs our construction of the ParityG framework. We first describe the conditions we need from a two-player game G in order to extend it to an N -player Parity-G game. We note that these conditions are very natural and satisfied by nearly all two-party games studied in the literature.

9

4.1

Two-player games with Pauli strategies

Games. Throughout this section, G = (π, X , Y, {0, 1}L , B, V ) refers to a two-player game such that (x, y) ∼ π on the cross product of input sets X × Y, Alice receives x and outputs a bit string a = (aℓ )ℓ∈L ∈ {0, 1}L indexed by a finite set L, Bob receives y and outputs b ∈ B, and they win iff V (x, y, a, b) = 1. Alice’s output set is all of {0, 1}L , and any constraint on her answer is encoded in the winning condition V . Pauli strings. A signed Pauli string on k qubits is an operator τ = ± τ1 ⊗ · · · ⊗ τk with τi ∈ {I, X, Y, Z}. Its X-support is the vector suppX (τ ) ∈ Fk2 with suppX (τ )i = 1 iff τi ∈ {X, Y }. v k v v1 vk We call τ Z-type if suppL X (τ ) = 0, that is, τ = ±Z for some v ∈ F2 , where Z := Z ⊗· · ·⊗Z . k We also write ⟨u, p⟩ := i ui pi for u, p ∈ F2 . Lemma 4.1 (Twist rule). For every signed Pauli string τ on k qubits and every p ∈ Fk2 , Z p τ Z p = (−1)⟨p,suppX (τ )⟩ τ. Proof. Z anticommutes with X and Y and commutes with I and Z. Hence, for each i, Z pi τi Z pi = (−1)pi suppX (τ )i τi , and the claim follows by taking the tensor product over i. Definition 4.2 (Pauli strategy and key input). A k-qubit Pauli strategy S for a game G is a quantum strategy satisfying conditions (C1), (C2) and (C3) as follows. ⊗k

(C1) Resource state. Alice and Bob share k EPR pairs |Φ+ ⟩

between them.

(C2) Alice measures Pauli strings. For every input x ∈ X , Alice jointly measures pairwise commuting signed Pauli strings (Qx,ℓ )ℓ∈L on her k qubits. So, she reports (−1)aℓ as the outcome of Qx,ℓ . In particular, she performs the projective measurement Πxa :=

Y

1 2

I + (−1)aℓ Qx,ℓ ,

a ∈ {0, 1}L .

(2)

ℓ∈L

Bob’s measurements are arbitrary POVMs {Nby }b∈B on his k qubits. We write ω(S) for the winning probability of S in G. Also, an input x∗ ∈ X is a key input for S if the following condition is met. (C3) Key input. Every Qx∗ ,ℓ is Z-type, say Qx∗ ,ℓ = (−1)sℓ Z vℓ , such that the vectors (vℓ )ℓ∈L span Fk2 . Remark 4.3. Condition (C1) says the resource state required by S should be a tensor product of EPR pairs. In our N -player Parity-G game, this will be obtained from sharing k GHZ states. Condition (C2) is the key requirement of our framework. By Lemma 4.1, conjugating any Qx,ℓ by Z p gives ±Qx,ℓ . Applying Z p to Alice’s qubits before she measures therefore leaves her measurement (2) unchanged as a set of projectors and only changes which outcome label each projector carries (Lemma 4.9 makes this precise). As we will see soon, the referee of a Parity-G game will need to undo such a relabelling. Note that for observables outside the √ Z = −X+Z √ √ Pauli group this fails: Z X+Z is neither X+Z nor its negation. Condition (C2) 2 2 2 restricts only Alice, because in our construction the operators Z p act on her qubits alone; Bob’s measurements are arbitrary. Condition (C3) singles out an input on which Alice’s measurement is a computational-basis measurement (Lemma 5.1); this input will produce the key.

10

4.2

The Parity-G game

Consider a two-player game G which has a k-qubit Pauli strategy S. We first establish some more notation by defining the swap mask of S, which intuitively the referee of the Parity-G game will use to relabel Alice’s answer. Definition 4.4 (Swap mask). For each input x ∈ X and output index ℓ ∈ L, the mask vector of Qx,ℓ is ux,ℓ := suppX (Qx,ℓ ) ∈ Fk2 . We define the swap mask of S as the map σ : X ×Fk2 → {0, 1}L given by
σ(x, p) := σℓ (x, p) ℓ∈L , σℓ (x, p) := ⟨ux,ℓ , p⟩. (3) By Lemma 4.1, σℓ (x, p) = 1 exactly when Z p anticommutes with Qx,ℓ . Thus σ(x, p) lists the outcome bits of Alice’s measurement on input x that flip when her qubits carry the twist Z p . Section 4.3 shows that entanglement swapping produces such a twist. Definition 4.5 (Parity-G game). For N ≥ 2, the N -player game pGN has players Alice, B1 , and parity Bobs B2 , . . . , BN −1 . • Inputs. The referee samples (x, y) ∼ π and sends x to Alice and y to B1 . The parity Bobs receive no input. • Outputs. Alice outputs a ∈ {0, 1}L and B1 outputs b ∈ B. Each parity Bob Bj outputs (1) (k) a vector cj = (cj , . . . , cj ) ∈ Fk2 , one bit per index i ∈ {1, . . . , k}. • Parity. The referee computes the parity vector p = (p1 , . . . , pk ) ∈ Fk2 , where pi :=

N −1 M

(i)

cj

(1 ≤ i ≤ k)

j=2

is the XOR of the parity Bobs’ i-th bits. In vector notation, p = c2 ⊕ · · · ⊕ cN −1 with ⊕ taken coordinate wise. • Winning predicate. The players win iff
V x, y, a ⊕ σ(x, p), b = 1.

(4)

The game depends on S only through the mask vectors, and we suppress this dependence in the notation. For N = 2 there are no parity Bobs, p = 0, and pG2 = G. Since Alice’s output set is all of {0, 1}L , the relabeled answer a ⊕ σ(x, p) is again an element of it, so the predicate (4) is well defined. This is why constraints on Alice’s answer are encoded in V . Lemma 4.6 (Properties of the mask). Given a game G with a k-qubit Pauli strategy S, the swap mask σ has the following properties. (i) σ(x, ·) is linear: σ(x, p ⊕ p′ ) = σ(x, p) ⊕ σ(x, p′ ), and σ(x, 0) = 0. (ii) If x∗ is a key input, then σ(x∗ , p) = 0 for every p. Q L (iii) If T ⊆ L and ℓ∈T Qx,ℓ = ±I, then ℓ∈T σℓ (x, p) = 0 for every p. Proof. (i) follows directly from (3), and (ii) holds because Z-type strings have zero
QX-support. p p p For (iii), inserting Z Z = I between the factors and applying Lemma 4.1 gives Z Qx,ℓ Z p = ℓ∈T L Q Q (−1) ℓ∈T σℓ (x,p) ℓ∈T Qx,ℓ . The left side equals ℓ∈T Qx,ℓ because this product is ±I. Part (iii) says that the mask respects every multiplicative relation among Alice’sQ observables. In particular, the relabelling never breaks a L parity constraint that S satisfies: if ℓ∈T Qx,ℓ = (−1)s I, then Alice’s answers under S satisfy ℓ∈T aℓ = s, and so does a ⊕ σ(x, p) for every p. 11

4.3

The honest strategy

The honest strategy for a Parity-G game can be constructed by applying the corresponding two player strategy S for G on k EPR pairs shared between Alice and B1 , with some additional measurements by the parity Bobs. The strategy. The N players share |GHZN ⟩⊗k . Every player holds one qubit of each copy, and P (i) denotes player P ’s qubit of copy i. They carry out the following measurements. (i)

(M1) Each parity Bob Bj measures X on each of their k qubits, obtaining the bit cj from copy (1)

(k)

i, and outputs cj = (cj , . . . , cj ). (M2) On input x, Alice performs {Πxa }a of (2) on (A(1) , . . . , A(k) ) and outputs a. (1)

(k)

(M3) On input y, B1 performs {Nby }b on (B1 , . . . , B1 ) and outputs b. Lemma 4.7 (Single-copy swap). Consider a single copy of |GHZN ⟩ and group its qubits as
|GHZN ⟩ = √12 |0⟩A |0⟩B1 |0 · · · 0⟩par + |1⟩A |1⟩B1 |1 · · · 1⟩par , where the register par holds the qubits of the parity Bobs B2 , . . . , BN −1 . Each parity Bob Bj measures their qubit in the X basis, obtaining the bit ej ∈ {0, 1}. Let e :=

N −1 M

ej .

j=2

Then, each outcome string (e2 , . . . , eN −1 ) ∈ {0, 1}N −2 occurs with probability 2−(N −2) , and conditioned on it, the state of (A, B1 ) collapses to
√1 |00⟩ + (−1)e |11⟩ = (Z e ⊗ I) Φ+ . (5) 2 For N = 2 there are no parity Bobs, e = 0, and the state is |Φ+ ⟩ = |GHZ2 ⟩. Proof. After all the parity Bobs B2 , ..., BN −1 measure the GHZ state in the X basis, with Bj measuring the bit ej , we can check that the state collapses to the unnormalized two-qubit state  Q  √ −(N −2) 1
Q (−1)ej e √1 √1 √ √ 2) · |00⟩ + (−1) |11⟩ , |00⟩ + |11⟩ = ( j j 2 2 2 2 | {z } | {z } √ √ ( 2)−(N −2)

(−1)e ( 2)−(N −2)

Q where j (−1)ej = (−1)e because only the parity of the number of minus signs matters. Normalizing this, we obtain the state in Eq. (5). Lemma 4.8 (Dressed EPR resource). Under the measurement (M1), every outcome (c2 , . . . , cN −1 ) occurs with probability 2−k(N −2) , so p is uniform on Fk2 . Conditioned on the outcome, the state of Alice’s and B1 ’s qubits is p |Ψp ⟩ = ZA ⊗ IB1

Φ+

⊗k

p p1 pk ZA = ZA (1) ⊗ · · · ⊗ ZA(k) ,

,

(6)

(i)

where the i-th EPR pair is on (A(i) , B1 ). Proof. We apply Lemma 4.7 to each copy. On copy i, the parity Bobs’ outcome bits are (i) (i) ej = cj , so e = pi ; copy i therefore yields (Z pi ⊗ I) |Φ+ ⟩ on (A(i) , B1 ), and its outcome string has probability 2−(N −2) . The lemma follows from taking the product over i. 12

Lemma 4.9 (The twist relabels Alice’s outcome). For all x ∈ X , a ∈ {0, 1}L and p ∈ Fk2 , Z p Πxa Z p = Πxa⊕σ(x,p) .
Proof. By Lemma 4.1, conjugating each factor of (2) gives Z p 21 I + (−1)aℓ Qx,ℓ Z p = 12 I +
(−1)aℓ ⊕σℓ (x,p) Qx,ℓ . Proposition 4.10 (Honest winning probability). For every p ∈ Fk2 , conditioned on the parity being p, the honest strategy (M1)–(M3) wins pGN with probability ω(S). In particular it wins with probability ω(S). Proof. Fix p and (x, y), and let PS (a, b | x, y) be the output distribution of S in G. By Lemmas 4.8 and 4.9,

⊗k ⊗k = PS a ⊕ σ(x, p), b | x, y . Z p Πxa Z p ⊗ Nby Φ+ Pr[a, b | x, y, p] = Φ+ So, (a ⊕ σ(x, p), b) has the same distribution as the outputs of S, and the referee evaluates V on this pair. Averaging over (x, y) ∼ π gives the winning probability ω(S).

4.4

Quantum and classical values

A quantum strategy for pGN consists of a state ρ on QA ⊗ QB1 ⊗ Qpar , where Qpar = QB2 ⊗ (j) · · ·⊗QBN −1 , together with POVMs {Max } for Alice, {Nby } for B1 , and {Dc }c∈Fk for each parity 2 Bob, which carries no input label. For p ∈ Fk2 let Dp :=

N −1 O

X

Dc(j) , j

  qp := Tr ρ (I ⊗ I ⊗ Dp ) ,

c2 ,...,cN −1 ∈Fk2 j=2 c2 ⊕···⊕cN −1 =p

 1/2 1/2  and, for qp > 0, let ρ(p) := qp−1 Trpar (I ⊗ I ⊗ Dp ) ρ (I ⊗ I ⊗ Dp ) be the state of QA QB1 conditioned on parity p. Theorem 4.11 (Values of Parity-G games). For every N ≥ 2, ωQ (pGN ) = ωQ (G)

and

ωC (pGN ) = ωC (G).

The honest strategy attains ω(S), so it is optimal whenever S is optimal for G. Proof. Lower bound. If every parity Bob outputs cj = 0, then p = 0, σ(·, 0) = 0, and Alice and B1 play G. Every quantum or classical strategy for G therefore wins pGN with the same probability. Quantum upper bound. The parity Bobs have no input, so Dp does not depend on (x, y) and X X X  
Pr[win] = q p ωp , ωp := π(x, y) Tr ρ(p) (Max ⊗ Nby ) V x, y, a ⊕ σ(x, p), b . p

x,y

a,b

Substituting a′ = a ⊕ σ(x, p), which is a bijection of {0, 1}L , shows that ωp is the winning probability in G of the strategy with state ρ(p) , Alice’s POVMs Ma′x′ := Max′ ⊕σ(x,p) and Bob’s POVMs Nby . Hence ωp ≤ ωQ (G) for every p, and Pr[win] ≤ ωQ (G). Classical upper bound. By convexity it suffices to bound deterministic strategies. The parity Bobs then output constants, so p is fixed, and the predicate sees Alice’s answer function x 7→ f (x) as x 7→ f (x) ⊕ σ(x, p), which is again a deterministic answer function. The winning probability is that of a deterministic strategy for G, at most ωC (G). The last claim is Proposition 4.10. Corollary 4.12. If G is a pseudo-telepathy game and ω(S) = 1, then pGN is a pseudo-telepathy game for every N ≥ 2, and the honest strategy wins it with certainty. 13

4.5

The Parity Magic Square game

We now study the Parity-G game for the special case when G is the Magic Square game. For the rest of the paper, we will mostly focus on building a conference key protocol from this game and analyzing its security, to simplify exposition. When needed, we will show how our analysis carries over to general Parity-G games. So, let G = MSG with L = {0, 1, 2}, X = Y = {0, 1, 2}, π uniform, and Alice’s parity constraint folded into the predicate: L2 L2 ay = bx . VMSG (x, y, a, b) = 1 ⇐⇒ ℓ=0 bℓ = 1, ℓ=0 aℓ = 0, Answers violating a parity constraint lose in this formulation and in the one of the preliminaries, so the two define the same game. The Pauli strategy. Let SP be the optimal quantum strategy (or Peres strategy) described ⊗2 in Proposition 3.6: Alice holds (A(1) , A(2) ) of |Φ+ ⟩ and on row x measures Qx,y := Pxy from (1), and B1 on column y measures P0y , P1y , P2y . We note that SP is a valid Pauli strategy since it satisfies the conditions of Definition 4.2 with k = 2: • (C1) holds with two EPR pairs. • (C2) holds because every entry of (1) is a signed Pauli string and the entries of each row commute (Lemma 3.5). • (C3) holds with x∗ = 0: the row-0 observables are I ⊗ Z = Z (0,1) , Z ⊗ I = Z (1,0) and Z ⊗ Z = Z (1,1) , and (0, 1), (1, 0) span F22 . Moreover, ω(SP ) = 1 by Proposition 3.6. The swap mask. where

(1)

(2)

Writing Pxy = ± τxy ⊗τxy , the mask vector of cell (x, y) is ux,y = (αxy , βxy ), (1) αxy := [τxy ∈ {X, Y }],

(2) βxy := [τxy ∈ {X, Y }].

(7)

Table 1 lists these values. By (3), the mask on cell (x, y) is αxy p1 ⊕ βxy p2 ; following the rest of the paper, we write it as σ(x, y) and leave the dependence on p = (p1 , p2 ) implicit. (αxy , βxy ) x=0 x=1 x=2

y=0 (0, 0) (1, 0) (1, 0)

y=1 (0, 0) (0, 1) (0, 1)

y=2 (0, 0) (1, 1) (1, 1)

Table 1: The mask vectors (7) of the Peres strategy (1). The mask is σ(x, y) = αxy p1 ⊕ βxy p2 . Definition 4.13 (Parity Magic Square game pMSGN ). pMSGN is defined as the Parity-G game, from Definition 4.5, with G = MSG and the Peres strategy SP . Explicitly, the players are Alice, Bob B1 , and parity Bobs B2 , . . . , BN −1 . • Inputs. Alice receives a row x ∈ {0, 1, 2} and B1 a column y ∈ {0, 1, 2}, both input are uniform random and independent. The parity Bobs receive no input. • Outputs. Alice outputs a = (a0 , a1 , a2 ), B1 outputs b = (b0 , b1 , b2 ), and each parity Bob (1) (2) Bj outputs two bits (cj , cj ).

14

• Parities and mask. The referee sets p1 = σ(0, y) = 0 (∀y),

LN −1 (2) LN −1 (1) j=2 cj , and the mask j=2 cj , p2 =

σ(x, 0) = p1 , σ(x, 1) = p2 , σ(x, 2) = p1 ⊕ p2

(x ∈ {1, 2}).

(8)

• Winning predicate. 2 M

aℓ = 0 (Alice even),

ℓ=0

2 M

bℓ = 1 (B1 odd),

ay ⊕ bx = σ(x, y) (masked cell check).

ℓ=0

(9) For N = 2 there are no parity Bobs, σ ≡ 0, and pMSG2 = MSG. Remark 4.14 (Equivalence with Definition 4.5). The general predicate (4) checks Alice’s parity on a ⊕ σ(x, ·), while (9) checks it on a. TheLtwo agree: each row of the Peres square multiplies to +I (Lemma 3.5), so by Lemma 4.6 (iii) y σ(x, y) = 0 for every x, which is also implied by (8). Hence, the referee may equivalently replace Alice’s cell value ay by ay ⊕ σ(x, y) and apply the ordinary magic-square check. Note that the relabeled triple would still have even parity. The honest strategy. Here, we simply instantiate the measurement strategy (M1)–(M3) from Section 4.3 with k = 2: (1)

(2)

(S1) Each parity Bob Bj measures X on both of their qubits and gets cj , cj . (S2) On row input x, Alice measures the commuting Peres observables Px0 , Px1 , Px2 of (1) jointly on her qubits (A(1) , A(2) ), getting the measurement outcomes a0 , a1 , a2 . (S3) On column input y, B1 measures the commuting conjugated observables P0y , P1y , P2y (1) (2) jointly on his qubits (B1 , B1 ), getting the measurement outcomes b0 , b1 , b2 . ⊗2

p1 p2 + By Lemma 4.8, after (S1), Alice and B1 obtain the state (ZA , and by (1) ⊗ ZA(2) ) |Φ ⟩ Lemma 4.9 the twist flips exactly the cells with σ(x, y) = 1. We also note the following properties of pMSGN .

Proposition 4.15 (Quantum value). ωQ (pMSGN ) = 1: the strategy (S1)–(S3) wins on every input and for every outcome of the parity Bobs. Proof. This follows from Proposition 4.10 with ω(SP ) = 1. Proposition 4.16 (Classical value). ωC (pMSGN ) = 8/9 < 1. Hence pMSGN is a pseudotelepathy game. Proof. This follows from Theorem 4.11 and ωC (MSG) = 8/9. Remark 4.17. The classical value can also be checked directly. For a deterministic strategy the mask L is fixed, and the row-versus-column L L parity count of the magic square acquires the extra term σ(x, y) = p α ⊕ p 1 2 x,y x,y xy x,y βxy . Table 1 has four ones in each coordinate, so this term vanishes for every (p1 , p2 ), and we can follows the same proof as the 2-player Magic Square game. Key input.

The key input for Alice is x∗ = 0, which is never masked.

15

4.6

Further instances

Here, we show some examples of other games which also fit into the framework of Parity-G games. Example 4.18 (Parity-CHSH). Let G = CHSH: x, y ∈ {0, 1} uniform, |L| = 1, b ∈ {0, 1}, and V (x, y, a, b) = [ a ⊕ b = xy ]. The optimal strategy
on one EPR pair has Alice measure Q0 = Z and Q1 = X and Bob measure √12 Z + (−1)y X . With this strategy, they win with probability cos2 (π/8). Alice’s observables are Pauli strings and x∗ = 0 is a key input. The mask vectors are u0 = 0 and u1 = 1, so σ(x, p) = xp, and the resulting Parity-G game, which we denote pCHSHN , is won iff L −1 a ⊕ b ⊕ xp = xy, p= N j=2 cj . By Theorem 4.11, ωQ (pCHSHN ) = cos2 (π/8) and ωC (pCHSHN ) = 3/4. Bob’s observables are not Pauli strings, which is allowed since the twist sits on Alice’s side. The Parity-CHSH game was defined by [RMW18], and also used as part of their conference key agreement protocol. Example 4.19 (Binary constraint system games). We note that a subset of Binary constraint system games admitting Pauli strategies [CM14] can be used to construct their corresponding Parity-G games as well, following a similar argument as above.

5

The DI-CKA protocol

We now show our conference key agreement protocol, basing it on the Parity Magic Square game, followed by a proof of its security. By Remark A.3, it seems challenging and perhaps impossible in certain cases to obtain a conference key from a single game, so our protocol uses two measurement settings depending on whether the players are in a test round or a key round.

5.1

Setup

There are N parties P1 = Alice, P2 , . . . , PN = B1 , . . . , BN −1 , each holding one untrusted device with settings {X, Y, Z} and classical outputs. We make the same standard assumptions as used in DI-QKD literature (isolated parties, trusted local randomness, authenticated public broadcast given to Alice and Bob), see for instance [CMT25]. In particular, we assume that the devices can not access classical communication between Alice and Bob during the protocol. This is important when Alice announces a round as being a test round or a key round, for instance, as we will see in the protocol. At the end, this information is made public, since their classical channels are not secret to an adversary Eve. Note that this is consistent with the non-signaling assumption between the devices and Eve, during the protocol. As we are in the device-independent setting, we assume nothing about the devices’ internal workings and allow them to be maximally malicious within these constraints.

5.2

The DI-CKA protocol

Here we describe the conference key agreement protocol based on pMSGN . Protocol 1: pMSGN -DI-CKA Parameters. Rounds n; test probability γ ∈ (0, 1); tolerated score ωtol = ω(v) − δ; error-correction budget; correctness-hash length t; key length ℓ. For each round i = 1, . . . , n: (1) Round type. Alice asks her device to generate |GHZN ⟩⊗2 and distributes it with all the players. She also broadcasts a coin Ti with Pr[Ti = 1] = γ.

16

(2a) Key round (Ti = 0). Every player asks their devices to measure Z and records their b } output, setting their raw key bits {Kj,i b∈{0,1} . (2b) Test round (Ti = 1). Alice chooses a uniform random row xi , B1 chooses a uniform random column yi , and they both ask their devices to perform measurements according to the cell (xi , yi ) in (1); all the parity Bobs B2 , ..., BN −1 ask their devices to measure X on both their qubits. (Note that all devices may behave dishonestly, both when preparing states or performing measurements) After all rounds: (3) Parameter estimation. All test-round inputs and outputs are broadcast. All parties calculate p1,i , p2,i , the masks σi , and the empirical winning frequency ω̂. If ω̂ < ωtol , they abort. 0 , K1 } (4) Sifting. Each party’s raw key is its key-round string Kj = {Kj,i j,i i:Ti =0 .

(5) Error correction (one-to-many). Alice broadcasts a single syndrome of K1 of length leakEC ≈ nkey maxj H(K1 |KBj ) + O(log 1/εEC ); each Bob decodes towards K1 . Alice broadcasts a 2-universal hash of K1 of length t; abort on any mismatch. (6) Privacy amplification. Alice broadcasts a hash seed; all parties hash their corrected keys to length ℓ, obtaining K1 , . . . , KN . In short, every party measures Z on key rounds, so all N parties obtain the same key. The test rounds are just used to ensure that the devices behave honestly throughout the protocol, since they are not able to distinguish between key rounds and some test rounds (in particular, when Alice’s test round input is 0). Now, we can generalize this conference key agreement protocol to DI-CKA protocols based on Parity-G games as well. Let pGN be a Parity-G game corresponding to the two player game G. Similarly as before, we interleave test rounds of playing pGN with key rounds, in which Alice’s device receives the key input x∗ and every other party measures (say) k qubits in the computational basis. Condition (C3) from Definition 4.2 makes Alice’s key round output equivalent to a Z-basis outcome (or a bitstring), so all parties obtain a common string. So, the security of this string can be certified by passing the test rounds, as we explain later in the analysis in the next section. Lemma 5.1 (Key input and consensus). Let x∗ be a key input for S, with Qx∗ ,ℓ = (−1)sℓ Z vℓ as used in Definition 4.2. Then,
∗ (i) Every nonzero Πxa equals |z⟩⟨z| for the unique z ∈ Fk2 with a = ⟨vℓ , z⟩ ⊕ sℓ ℓ∈L . Hence Alice’s output on x∗ and her computational-basis outcome z determine each other. (ii) If all N players measure each of their qubits of |GHZN ⟩⊗k in the computational basis, they all obtain the same uniformly random z ∈ Fk2 . ∗

Proof. (i) Qx∗ ,ℓ |z⟩ = (−1)⟨vℓ ,z⟩⊕sℓ |z⟩, so Πxa projects onto the span of the |z⟩ with ⟨vℓ , z⟩ ⊕ sℓ = aℓ for all ℓ. Since the vℓ span Fk2 , at most one z solves these equations. (ii) Follows directly by the entanglement structure of each GHZ state.

6

Security proofs for pMSGN -DI-CKA

We start by recalling the security definition for a general N -party DI-CKA protocol. 17

Definition 6.1 (Restatement of Definition 3.9). An N -party DI-CKA protocol outputs a key K ∈ {0, 1}ℓ for all parties, or ⊥. It is ε-secure if: (i) Correctness (εcor ): Pr[no abort ∧ ∃i ̸= j : Ki ̸= Kj ] ≤ εcor ; (ii) Secrecy (εsec ): conditioned on no abort, 12 ρKE − τK ⊗ ρE 1 ≤ εsec , with τK maximally mixed and E the adversary’s quantum side information including the public transcript, and ε = εcor + εsec . We first prove a theorem showing the correctness of the pMSGN -DI-CKA protocol. Theorem 6.2 (Correctness of Protocol 1). For any parameter estimation tolerance bound δ ∈ [0, 1/9), Protocol 1 is εcor for   n 2 εcor ≤ (N − 1)(εEC + ε′EC ) + 1 − γ 1 − e−2δ (10) where max{Pr[EC(j) aborts]} ≤ εEC and max{Pr[Ki ̸= Kj | no abort]} ≤ ε′EC . j

i,j

Proof. In an honest implementation of the protocol, we assume the measurement devices acted honestly, which means they prepared the correct states and reported the correct measurement outcomes to all the players. If our protocol is honestly implemented, we show that the probability of getting a bit of key per round shared by all the players is high, as follows. Conditioned on not aborting, we know that the probability of any two of them not sharing the same key bits is bounded by εEC . By applying a union bound on the mismatch events corresponding to Alice’s key bits and each of the N − 1 Bobs’ key bits, we obtain that Pr[∃i, j : Ki ̸= Kj | no abort] ≤ (N − 1)ε′EC .

(11)

Now, we just need to bound the probability of the protocol aborting. There are two scenarios in which the protocol aborts. 1. An error correction step failed, which happens with probability at most εEC per Bob’s EC(j). By a union bound, the probability of any one of them failing is at most Pr[∃j : EC(j) aborts] ≤ (N − 1)εEC .

(12)

2. The parameter estimation step failed, conditioned on the protocol not aborting in the error correction step. The latter probability is bounded by the following expression. Let G(j) denote Alice’s guess for Bob j’s testing-round bits, and let G(1,...,N −1) be correct whenever G(j) is correct for every j ∈ {1, . . . , N − 1}. Then, # " n n h i X X (1,...,N −1) (1,...,N −1) is correct Pr(PE aborts) = Pr G is correct Pr Ci < ωtol Ti G i=1

i=1

# " n n h i X X + Pr ∃j : G(j) is wrong Pr Ci < ωtol Ti ∃j : G(j) is wrong . i=1

(13)

i=1

Here Ti denotes the indicator random variable for the event that round i is chosen for testing, so that the Ti are i.i.d. Bernoulli random variables with Pr[Ti = 1] = γ. Moreover, Ci denotes the indicator random variable for the event that the parameter estimation test passed in test round i. So, for every j ∈ {0, . . . , n}, " n #   X n Pr Ti = j = (1 − γ)n−j γ j . (14) j i=1

18

Pn Now, conditioned on i=1 Ti = j and assuming E[Ci ] = ω(ν) such that δ = ω(v) − ωtot , Hoeffding’s inequality gives " n # n X X 2 Pr Ci < (ωtol )j Ti = j ≤ e−2δ j . i=1

i=1

 We can also trivially bound Pr G(1,...,N −1) is correct ≤ 1. Substituting back into the previous expression, we get 

PPE (abort) =

n X

" n # " n # n X X X Pr Ti = j Pr Ci < (ωtol )j Ti = j

j=0 n  X

i=1

i=1

i=1



n 2 (1 − γ)n−j γ j e−2δ j j j=0 n     X n 2 j = (1 − γ)n−j γe−2δ j j=0   2 n = 1 − γ + γe−2δ   n 2 = 1 − γ 1 − e−2δ ,

≤

(15)

where the final equality follows from the binomial theorem as n    j  n   n X n n−j −2δ 2 −2δ 2 −2δ 2 (1 − γ) γe = 1 − γ + γe = 1−γ 1−e . j j=0

Thus, the total error probability is bounded by the sum of the failure probabilities of any of the three events in (11), (12) and (15), which proves the lemma. It remains to prove the secrecy of Protocol 1. For this, the main quantity to control is the smooth conditional min-entropy of Alice’s raw key string conditioned on the adversary’s quantum side information and the public transcript. More precisely, we require a lower bound on ε Hmin (An1 | X = 0, E)ρ|Ω , (16) where ρAn1 E denotes the classical-quantum state describing Alice’s raw key string and the adversary’s side information immediately before privacy amplification, conditioned on Ω, the event that the protocol did not abort. The secrecy proof uses two main technical ingredients. The first is the Leftover Hash Lemma applied to a classical-quantum state ρAn1 E , which converts a lower bound on the smooth minentropy of Alice’s raw key into a bound on the secrecy of the extracted key. The second is the Generalized Entropy Accumulation Theorem (GEAT), which is used to establish such a lower bound on the smooth min-entropy in terms of the per round conditional von Neumann entropy. We state these two theorems as follows. Theorem 6.3 (Leftover Hash Lemma on ρAn1 E [Ren05]). Let ρAn1 E be the classical-quantum state of Alice’s raw key string An1 ∈ {0, 1}n and the adversary’s quantum side information E immediately before privacy amplification. Let Ω denote the event that Protocol 1 does not abort. Let F be a two-universal family of hash functions F : {0, 1}n → {0, 1}ℓ . Let F be sampled independently and publicly. The final key is defined as K := F (An1 ). Then, for every ε ≥ 0,
  ε 1 1 − 12 Hmin An 1 |X=0,E ρ|Ω −ℓ ρ − τK ⊗ ρE|Ω 1 ≤ ε + · 2 , (17) 2 KE|Ω 2 where τK := 2−ℓ IK denotes the maximally mixed state on {0, 1}ℓ . 19

Theorem 6.4 (Generalized Entropy Accumulation Theorem (GEAT) [MFSR22]). Consider quantum channels Mi : Ri−1 Ei−1 → Ai Ri Ei , i ∈ {1, . . . , n}, satisfying the following nonsignaling condition: for each channel Mi , there exists a quantum channel Ri : Ei−1 → Ei such that TrAi Ri ◦Mi = Ri ◦ TrRi−1 . (18) Then, for any initial state ρ0R0 E0 , the smooth min-entropy of the outputs An := A1 · · · An conditioned on the final side information En satisfies ε Hmin (An | En )M ◦···◦M ρ0 n

1

R0 E 0

 ≥

n X i=1

  ei−1 inf H Ai | Ei E ω

√ ≥ nh − c0 − c1 n ,

Mi (ω)

√ − O( n) ,

(19) (20)

ei−1 ≡ Ri−1 Ei−1 is a purifying system for the input to Mi , and the infimum is taken where E ei−1 . Appendix B contains the specific values of the over all states ω on the systems Ri−1 Ei−1 E constants c0 and c1 , which depend on an affine min-tradeoff function f as well. We first define the channels in Protocol 1 which satisfy the non-signaling condition required by GEAT, and give a short proof of this claim. Lemma 6.5 (Non-signaling condition). Consider the following CPTP map in a general round i: {Mi : Ri−1 Ei−1 → KA,i KB,i,j Ci Ri Ei } of Protocol 1, where KA,i is the set of Alice’s two key bits in the i−th round, R = RA RB1 ...RBN −1 are the internal registers of Alice and Bobs’ devices, Ci is the classical information computed by Alice and Bob (e.g., for privacy amplification), and i−1 is given Ei = X1i Y1i,1 ...Y1i,N −1 T1i QE is Eve’s side information for that round. The state ωRE i−1 as input to the map Mi . Then, there exist corresponding reduced channels {Ri : Ei−1 → Ei } such that TrAi Ri ◦Mi = Ri ◦ TrRi−1 . Proof. Consider the channel Ri : Ei−1 → Ei constructed as follows, following the steps of protocol. So, given the register Ei−1 , we generate the register Ei by sampling Ti , Xi , Yi1 , ..., YiN −1 as Alice and Bobs do in Protocol 1 at the start of the round, and then simulating Eve’s operations on her part of the state. Clearly, the distribution on these samples is identical to what is produced by R. Since we assumed the devices of Alice and Bob cannot communicate with Eve, the simulated output marginal of Mi will be independent of Ri−1 . Thus, if we trace out the Ri−1 register, the action of Ri is identical to the expected action when the channel Mi is i−1 . Thus, TrAi Ri ◦Mi = Ri ◦ TrRi−1 . applied to the state ωRE i−1 In the absence of a closed-form analytical min-tradeoff function for even the 2-player Magic Square Game, we resort to obtaining a lower bound on the per round conditional von Neumann entropy H(A|X = 0, E) of Protocol 1 via numerical methods. We use the techniques of [BFF24] to formulate a constrained minimization problem, which can be solved using the NPA hierarchy method [NPA07]. We first reduce the entropy lower bound of pMSGN to pMSG2 = MSG to simplify our problem as follows, and then solve for the case of MSG as a semi-definite program. Since this is perhaps the key component of our security analysis, we state and prove the following lemma in full generality for Parity-G games as defined in Section 4.2; setting G = MSG would then follow as a special case. Lemma 6.6 (Entropy Lower Bound Reduction from the N -player game pGN to the two-player game G). Let N ≥ 2 and x∗ ∈ X , where the latter is Alice’s input set with x∗ being her key input. Let A denote Alice’s k-bit output, and E denote Eve’s quantum system. Let us assume there exists a convex function fG : [0, 1] → R such that the per round conditional von Neumann entropy is lower bounded as H(A | X = x∗ , E)G ≥ fG (ω) (21) 20

over all possible quantum strategies by Eve, for the ordinary two-player G, where ω is its winning probability for G and E is arbitrary quantum side information. Then, H(A | X = x∗ , E)pGN ≥ fG (ω ′ ) ,

(22)

where ω ′ is the winning probability for pGN . Proof. Consider a strategy S for pGN . Let the output distribution of the parity-Bobs B2 ...BN −1 be described by the random variable C. Since the parity-Bobs receive no input, and by the non-signaling assumption, their output distribution qc := Pr[C = c] is independent of Alice’s and B1 ’s inputs. Indeed, if Ma|x , Nb|y , and Dc are the corresponding measurement operators, then X   Pr[C = c | X = x, Y = y] = Tr ρ Ma|x ⊗ Nb|y ⊗ Dc (23) a,b

= Tr[ρ I ⊗ I ⊗ Dc ] = qc .

(24)

For any output c sampled from C, let p = p(c) be the corresponding parity string output. Conditioned on this, Alice and Bob B1 reduce to playing G, by the proof of Theorem 4.11. ′ In particular, Alice and B1 can play a strategy for G with Alice’s relabeled POVMs Max = x Ma⊕σ(x,p(c)) . Hence the conditional, relabeled strategy S | p(c) is equivalent to a G strategy. Let ωc denote its winning probability. By (24) and the definition of independent events, the conditional distribution of inputs (X, Y ) over all c also remains the same. Therefore, X ′ ωpG (S) = q c ωc , (25) N c ′ where ωpG (S) is the winning probability of strategy S for pGN . N ∗ ∗ Now, by Lemma 4.6 (ii), M ′x = M x . By definition of fG , this implies H(A | E, X = x∗ , C = c) ≥ fG (ωc ). So, applying (21) in each branch gives the following lower bound for the strategy S, splitting E = ẼC, X H(A | E, X = x∗ ) = qc H(A | Ẽ, X = x∗ , C = c) (26) c

≥

X

qc fG (ωc )

(27)

c

! ≥ fG

X

q c ωc

(28)

c

′ = fG ωpG (S) , N

(29)

where (28) uses Jensen’s inequality and the last line follows from (25). Since we assumed S was arbitrarily chosen, the lemma follows. Lemma 6.7 (Conditional von Neumann entropy lower bound). The  conditional  von Neumann ei−1 entropy of Alice’s classical key bitstring H(A|X = 0, QE ) ≥ inf H Ai | Ei E ≥ f (ω) = ω

Mi (ω)

33.4ω − 31.47, imposing the winning probability threshold ω ≥ ωtol . Proof. Following the formalism in [BFF24], we can express a lower bound as follows. Lemma 6.8 ([BFF24]). Let m ∈ N, and let t1 , . . . , tm and w1 , . . . , wm be the nodes and weights of an m-point Gauss–Radau quadrature on [0, 1] with endpoint tm = 1. Let ρQA QB QE be the initial quantum state shared between Alice, Bob, and Eve’s devices, and let {Ma|x∗ }a denote the

21

∗ measurement operators performed by Alice’s n deviceoin response to the input X = x . Further1 more, for i = 1, . . . , m − 1, let αi := 23 max t1i , 1−t . Then H(A|X = x∗ , QE ) is never smaller i than m−1 h  X wi X
inf cm + Tr ρQA QE Ma|x∗ ⊗ Za + Za∗ + (1 − ti )Za∗ Za t ln 2 a Za ∈B(QE ) i=1 i (30) ∥Za ∥≤αi i
+ ti IQA ⊗ Za Za∗ ,

where cm =

Pm−1 i=1

wi ti ln 2 . Moreover, these lower bounds converge to H(A|X = 0, QE ) as m → ∞.

We also require the following additional constraint which describes the winning condition for the magic square with the winning probability threshold ωtol . ω(ρQA QB QE , Ma|x∗ , Nb|y∗ ) ≥ ωtol ,

(31)

Formulating and solving the resultant SDP via the NPA hierarchy techniques [NPA07], we get a lower bound function from a feasible solution to the dual SDP as prescribed by [BFF24], as follows. f (ω) = 33.4ω − 31.47 . (32) This solution comes from solving the SDP for the MSG game6 , but by Lemma 6.6, we know this is also a valid lower bound for the pMSGN game, for any N ≥ 2, since f is clearly a convex – indeed affine – function. We now combine these results and are ready to prove our main theorem. Theorem 6.9 (Secrecy of Protocol 1). Conditioned on not aborting, for every ε > 0, Protocol 1 produces ℓ bits of secret key and is εsec -secret with εsec ≤ ε +

1 − 1 (nh−c0 −c1 √n−leakε −ℓ) ·2 2 2

(33)

where h = mincn ∈Ω f (freq(cn )) corresponding to the affine min-tradeoff function f (ω) = 33.4ω − 31.47, γ is the probability of a test round, and the constants c0 , c1 are as defined in Theorem 6.4. Proof. By Theorem 6.4 and Lemma 6.7, since we satisfy Lemma 6.5, we can lower bound the smooth min-entropy of Alice’s key bitstring An before error correction as √ ε Hmin (An |En ) ≥ nh − c0 − c1 n . (34) Let the additional leakage in the broadcast, error correction and privacy amplification steps be denoted by leakε . The exact value of this depends on implementation details and will be ε (An |E ) and negligible asymptotically. Applying Theorem 6.3, with this lower bound on Hmin n leakage proves our desired result. Corollary 6.10 (Security of Protocol 1). Conditioned on not aborting, for every ε′ > 0, Protocol 1 produces ℓ bits of secret key and is ε-secure with   n √ 1 1 2 ε ≤ (N − 1)(εEC + ε′EC ) + 1 − γ 1 − e−2δ + ε′ + · 2− 2 (n·f (ω)−O( n)−leakε −ℓ) 2

(35)

Proof. This follows from Definition 3.9; and the statements of Theorem 6.2 and Theorem 6.9. 6

all code used for solving SDPs, and plotting key rates based on this in Section 7, can be found at [Sen26]

22

7

Asymptotic key rate analysis with depolarizing noise

The winning probability threshold we choose in an implementation of pMSGN should inherently be a function of the noise we expect in the channels. If we expect our channels to be perfectly noiseless, then we should set our winning probability threshold to be perfectly ω(v) = 1. In this case, losing any single game would mean that we detect an eavesdropper Eve, and abort the protocol. This implies that in the asymptotic regime, we get a guarantee that our key is perfectly secure with high probability, by monogamy of entanglement and self-testing property of the magic square game. Now, we define the key rate of a protocol as ℓ = (1 − γ)[H(A|X = 0, T = 1, E) − H(A|X = 0, T = 1, B)] (36) n where ℓ is the number of bits of the final secret key produced by the protocol, n is the number of rounds, γ is the test round probability, H(A|X = 0, T = 1, E) is the per round conditional von Neumann entropy of Alice’s raw key in a test round given by Ti = 1 (so Alice’s input X = 0), conditioned on Eve’s side information, and H(A|X = 0, T = 1, B) is the conditional entropy of Alice’s final key (after error correction and privacy amplification) with respect to the final key of any Bob Bi . For this calculation, we assume that all the outputs generated in the test rounds are published publicly and used for parameter estimation, so the players get secret bits of key as a fraction of the key rounds only. For calculating key rates, we consider an honest implementation of the protocol, which means that the states prepared and measurements performed by the devices are honest, up to some noise threshold. This means that the adversary Eve can adversarially prepare the state, and try to guess the key, but any measurement outcomes the dishonest devices report should be indistinguishable from the honest measurement outcome distribution on a noisy state. This is an upper bound on the number of bits of key we can get in a fully adversarial setting with noisy and dishonest measurements, and it is a simplified scenario which makes it amenable to comparing different protocols. In particular, assuming absence of noise, setting ωtol = 1, γ = 0, and having shared states which are honestly prepared, the key rate for pMSGN is 2. This is maximal since at most 2 bits of key can be produced per round. More generally, any quantum key distribution or conference key agreement protocol, whose security relies on the monogamy of entanglement, achieves maximal key rate in the absence of noise. But since, realistically, our channels are not noiseless, we must set a winning probability threshold which is below 1. Unfortunately, this also results in key rates which are lower. However, we can still get good lower bounds on the key rate as a function of the noise, by lower bounding ωtol as a function of the noise and applying Lemma 6.7 to get the corresponding number of bits per round. We first consider a global depolarizing noise channel when preparing the state, which is a standard assumption for a noise model in our setting, and also subsumes noisy measurements made by the players. We note that our techniques extend to any general noise model beyond depolarizing. The state ρ that all the players will share now is r :=

IN ρ = (1 − q) |ψ⟩ ⟨ψ| + q 4N , 4

(37)

where q ∈ [0, 1] is the noise parameter and |ψ⟩ = |GHZN ⟩⊗2 . Note that the quantum bit error rate (QBER) Q = Pr(A ̸= Bi ), which is the probability that Alice and some Bob Bi ’s bits disagree on average over their 2 bits, is Q = q/2. Now, the expected probability pexp of them winning pMSGN is 1 − q/2, since with probability 1 − q, the state is correct and with probability q, both the outputs of Alice and Bob B1 , and the parity bits, are all random. So, we set ωtol = pexp = 1 − q/2 = 1 − Q and compute the asymptotic key rate r∞ of pMSGN by defining r∞ := limn→∞ nl . So, r∞ (pMSGN ) = (1 − γ)[f (pexp ) − h(Q)] = (1 − γ)[f (1 − Q) − h(Q)] 23

(38)

where f was defined in Lemma 6.7, and h is the binary entropy function. We will also set γ = O log(n) , so limn→∞ γ = 0. n Local Depolarizing Noise Channels We may also consider a local depolarizing noise model where each pair of qubits that any Bob receives independently becomes maximally mixed with probability q. This model is relevant in the setting where we assume the state is locally prepared by Alice’s device, but the major source of noise comes from Alice sending out a pair of qubits from |GHZN ⟩⊗2 to each of the Bobs, so we assume the quantum channel between Alice and any Bob Bi is a depolarizing channel D : L(H) → L(H), with dim(H) = 4, such that I4 (39) 4 where q ∈ [0, 1]. The QBER in this case becomes Q = q/2, similarly as before. However, the expected winning probability pexp changes. If Bob B1 ’s subsystem becomes maximally mixed, then the probability of winning pMSGN becomes 1/2, but if B1 is noiseless and at least one parity-Bob qubit becomes maximally mixed, there is a 2/3 chance of winning (if Alice picks the first row as input); in all other cases it is 1/2 . So, D(ρ) = (1 − q)ρ + q

1 2 + Pr[B1 ideal , ∃i : Bi ̸= B1 noisy] · 2 3
q 2 = (1 − q)N −1 + + (1 − q) 1 − (1 − q)N −2 2 3 1 (1 − q) + 2(1 − q)N −1 = + . 2 6

pexp = Pr[all Bi s ideal] · 1 + Pr[B1 noisy] ·

(40) (41) (42)

Depolarizing Noise per qubit We can further consider a more fine grained noise model where each qubit that any Bob receives becomes maximally mixed with probability q ∈ [0, 1]. The QBER remains Q = q/2, and the expected winning probability pexp is again calculated through a case analysis as follows.    q2 5 (1 − q)N −2 2 2N −2 + + + (1 − q) 2(1 − (1 − q)N −2 ) (43) pexp = (1 − q) + 2q(1 − q) 9 18 2  N −2 7 N −2 2 2 (1 − q) · + (1 − (1 − q) ) · 9 3 2 1 (1 − q) (1 − q) 1 1 1 = + + + (1 − q)N −1 + (1 − q)N + (1 − q)2N −2 (44) 2 9 18 9 9 9

7.1

Comparison to the Parity-CHSH game

We compare the asymptotic key rate of our CKA protocol using pMSGN to its precursor, the CKA protocol using Parity-CHSH game as defined in [RMW18], which we denote by pCHSHN . It is analogously defined, with Alice and Bob B1 playing CHSH games in the test rounds instead of the magic square game. This game only requires 1 GHZ state to be shared between the players per round instead of 2, but it produces at most 1 bit of key per round for this reason as well. We also calculate the key rate for pCHSH as follows, in the presence of global depolarizing noise. Note that there is no dependence on the number of players N , since we are considering global noise on the entire state, regardless of the Hilbert space dimension.   1 − 2Q ′ 1 − h(Q) (45) r∞ (pCHSHN ) = f + √ 2 2 2     p where f ′ (ω) = 1 − h 21 + 12 (4ω − 2)2 − 1 asymptotically. We again set γ = O log(n) , so n limn→∞ γ = 0, and this term vanishes from the r∞ expression. We explain this comparison in Figure 3. 24

Figure 3: Key rate r = H(A|X = 0, T = 1, E) − h(q/2) as a function of the global depolarizing noise probability q. The per round entropy lower bound for pMSG is computed from Eq. (38) and the techniques of Lemma 6.7. We use a piecewise linear lower bound instead of just a single affine function since we just need a per round bound. The upper bound for pMSG is calculated from the strategy described in the paragraph below. We refer to prior work for a tight entropy upper and lower bound for pCHSH [GMKB23]. The true key rate for pMSG lies in the shaded region. The bars below the graph show which game achieves higher key rate in some noise regime; the middle section is open since our bounds for pMSG are not tight. The pMSG upper bound To prove an upper bound on the per round conditional von Neumann entropy of pMSG, it suffices to show that a strategy for Eve exists such that given a particular expected winning probability ω, H(A|X = 0, T = 1, E) ≤ g(ω) for some function g. Of course, if ω ≤ 8/9, which is the classical winning probability for pMSG, then g(ω) = 0 since a classical strategy would succeed up to this probability. Similarly, if ω = 1 which is the quantum winning probability for pMSG, then g(ω) = 2, by monogamy of entanglement. Now surprisingly, it turns out that there exists a (quantum) strategy for Eve such that g(ω) = 0 for ω ≲ 0.935 [AW20]. Since this seems to not have been discussed in the DI-QKD literature to the best of the authors’ knowledge, we describe this strategy in Appendix C. Eve then employs a convex-combination attack [LBJF+ 23] (between this strategy and the honest strategy), which gives us a reasonably good upper bound g(ω) for any ω. Now, we step back and discuss our model of comparison. For the purpose of comparing these two games, if we allow Eve to adversarially prepare states such that they maximize her guessing probability for the bits of secret key, then global depolarizing noise is the correct model to consider, since we put no bound on the dimension of the state Alice’s device prepares, so a per qubit noise model is not well-defined. However, note that, with an honest strategy, the maximal key rate for pMSGN is 2, and for pCHSHN it is 1. This is mainly due to the fact that, in pMSGN , we allow for the players

25

to share two GHZ states in parallel per round for the honest strategy. This suggests we can assume a noise model which fixes the dimension of the states, and allows for a fairer comparison by adding noise proportional to the number of qubits the players share, so arbitrarily increasing the size of this state doesn’t improve key rate for free. Local Depolarizing Noise Channels Similarly as in the case of analyzing pMSGN with noisy channels, the QBER remains Q = q/2. Following the same case analysis as previously, the noisy winning probability is as follows. Note that this noise model is the same as the depolarizing noise per qubit case, since Alice sends exactly one qubit to every Bob for pCHSHN , unlike in pMSGN where she had to send 2 qubits each.     
1 q 1 1 1 1 1 N −1 N −2 pexp = (1 − q) · + + (1 − q) 1 − (1 − q) + √ · + · + √ 2 2 2 2 4 2 2 2 2 (46) =

1 (1 − q) + (1 − q)N −1 √ . + 2 4 2

(47)

Figure 4: Key rate r = H(A|X = 0, T = 1, E) − h(q/2) as a function of the local, per qubit, depolarizing noise probability q, for various values of the number of parties N . The per round entropy lower bound for pMSG is computed from Eq. (44) and the techniques of Lemma 6.7. We use a piecewise linear lower bound instead of just a single affine function since we just need a per round bound. We refer to Eq. (47) and prior work for the (tight) lower bound for pCHSH [GMKB23].

Comparison with Parallel CHSH. Perhaps the most natural DI-CKA proposal is to use N − 1 pairwise DI-QKDs to share keys between a designated leader and each other party, allowing the leader to one-time pad their choice of key to all others. If each DI-QKD was based on a two-player non-local game, the resulting DI-CKA protocol would either be based on sequential two-player games, reducing the bits of key gained per round by a factor of N − 1, or would be based on parallel two-player games, which are actually new hard-to-analyze N -party games where the leader gets N − 1 inputs while all others get a single input. 26

In [RMW18], the main point of comparison for their CKA protocol based on the pCHSH game is N − 1 sequential DI-QKD protocols, each based on the CHSH game. Since we show that pMSG obtains improved key rates over pCHSH in the low noise regime, this implies we also improve over N − 1 sequential DI-QKD CHSH protocols in this regime. We may also attempt to compare with N − 1 DI-QKD protocols played in parallel, but that would require us to compute entropy lower bounds for a new N -party parallel CHSH game. This is essentially unfeasible with current techniques such as [BFF24] since the size of the resulting SDPs would scale with N . The only reason we are able to analyze the security of pMSG using an SDP is because the security reduces to the 2-party case as shown in Lemma 6.6. We analyze a possibly tractable variant which we term the Parallel Parity-CHSH game in Appendix D, which may serve as a proxy for comparison with N − 1 parallel DI-QKDs. We leave the full comparison with Parallel CHSH, or indeed any parallel two-party game including the Parallel Magic Square game, to future work.

8

Acknowledgments

This work was completed while all authors were employed by Visa Inc. The authors thank Adithya Bhat and Jonathan Lu for helpful conversations and the late Dr. Anderson C. A. Nascimento for his kindness and inspiring curiosity. AS is supported by a TQI Graduate Fellowship. RR is supported by an NSF Graduate Research Fellowship. Statement of AI Use. Generative AI was used to write the code to solve semi-definite programs (found here [Sen26]), based on the implementation by [ZMZ+ 23], which gave us the bounds for Lemma 6.7. It also helped write the code for calculating the key rates in Figure 3 and Figure 4 as well. It was also used to aid in proofreading and some parts of writing the paper. It did not contribute to any of the main ideas or conceptual insights of this work.

References [ABG+ 07]

Antonio Acı́n, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. Device-independent security of quantum cryptography against collective attacks. Physical Review Letters, 98:230501, 2007.

[AFDF+ 18] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick. Practical device-independent quantum cryptography via entropy accumulation. Nature communications, 9(1):459, 2018. [Amb26]

Andris Ambainis. Optimal bounds on the classical value of the repeated chsh game. arXiv preprint arXiv:2608.16439, 2026.

[AW20]

Sean A Adamson and Petros Wallden. Quantum magic rectangles: Characterization and application to certified randomness expansion. Physical Review Research, 2(4):043317, 2020.

[BB84]

Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, pages 175–179, Bangalore, India, 1984. IEEE.

[BBT05]

Gilles Brassard, Anne Broadbent, and Alain Tapp. Quantum pseudo-telepathy. Foundations of Physics, 35(11):1877–1907, 2005.

27

[BCW+ 12] Cyril Branciard, Eric G. Cavalcanti, Stephen P. Walborn, Valerio Scarani, and Howard M. Wiseman. One-sided device-independent quantum key distribution: Security, feasibility, and the connection with steering. Physical Review A, 85:010301(R), 2012. [BFF24]

Peter Brown, Hamza Fawzi, and Omar Fawzi. Device-independent lower bounds on the conditional von neumann entropy. Quantum, 8:1445, 2024.

[BP12]

Samuel L. Braunstein and Stefano Pirandola. Side-channel-free quantum key distribution. Physical Review Letters, 108:130502, 2012.

[CHSH69]

John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. Proposed experiment to test local hidden-variable theories. Physical review letters, 23(15):880, 1969.

[CM14]

Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In International colloquium on automata, languages, and programming, pages 320–331. Springer, 2014.

[CMT25]

Enrique Cervero-Martı́n and Marco Tomamichel. Device independent security of quantum key distribution from monogamy-of-entanglement games. Quantum, 9:1652, 2025.

[CS17]

Andrea Coladangelo and Jalex Stark. Robust self-testing for linear constraint system games. arXiv preprint arXiv:1709.09267, 2017.

[Eke91]

Artur K Ekert. Quantum cryptography based on bell’s theorem. Physical review letters, 67(6):661, 1991.

[EKMB17] Michael Epping, Hermann Kampermann, Chiara Macchiavello, and Dagmar Bruß. Multi-partite entanglement can speed up quantum key distribution in networks. New Journal of Physics, 19:093012, 2017. [GMKB21] Federico Grasselli, Gláucia Murta, Hermann Kampermann, and Dagmar Bruß. Entropy bounds for multiparty device-independent cryptography. PRX Quantum, 2:010308, 2021. [GMKB23] Federico Grasselli, Gláucia Murta, Hermann Kampermann, and Dagmar Bruß. Boosting device-independent cryptography with tripartite nonlocality. Quantum, 7:980, 2023. [HKB20]

Timo Holz, Hermann Kampermann, and Dagmar Bruß. Genuine multipartite Bell inequality for device-independent conference key agreement. Physical Review Research, 2:023251, 2020.

[LBJF+ 23] Karol Lukanowski, Maria Balanzó-Juandó, Máté Farkas, Antonio Acı́n, and Jan Kolodyński. Upper bounds on key rates in device-independent quantum key distribution based on convex-combination attacks. Quantum, 7:1199, 2023. [LCQ12]

Hoi-Kwong Lo, Marcos Curty, and Bing Qi. Measurement-device-independent quantum key distribution. Physical Review Letters, 108:130503, 2012.

[LWW+ 10] Lars Lydersen, Carlos Wiechers, Christoffer Wittmann, Dominique Elser, Johannes Skaar, and Vadim Makarov. Hacking commercial quantum cryptography systems by tailored bright illumination. Nature Photonics, 4(10):686–689, 2010.

28

[MFSR22]

Tony Metger, Omar Fawzi, David Sutter, and Renato Renner. Generalised entropy accumulation. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, pages 844–850. IEEE Computer Soc., Los Alamitos, CA, 2022] ©2022.

[MGKB20] Gláucia Murta, Federico Grasselli, Hermann Kampermann, and Dagmar Bruß. Quantum conference key agreement: A review. Advanced Quantum Technologies, 3(11):2000025, 2020. [MY04]

Dominic Mayers and Andrew Yao. Self testing quantum apparatus. Quantum Inf. Comput., 4(4):273–286, 2004.

[NC00]

Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000.

[NPA07]

Miguel Navascués, Stefano Pironio, and Antonio Acı́n. Bounding the set of quantum correlations. Physical Review Letters, 98(1):010401, 2007.

[Ren05]

Renato Renner. Security of Quantum Key Distribution. PhD thesis, ETH Zurich, 9 2005. Available at http://arxiv.org/abs/quant-ph/0512258.

[RMW18]

Jérémy Ribeiro, Gláucia Murta, and Stephanie Wehner. Fully device-independent conference key agreement. Physical Review A, 97(2):022307, 2018.

[SBV+ 21]

Pavel Sekatski, Jean-Daniel Bancal, Xavier Valcarce, Ernest Y-Z Tan, Renato Renner, and Nicolas Sangouard. Device-independent quantum key distribution from generalized chsh inequalities. Quantum, 5:444, 2021.

[Sen26]

Sen, Aniruddha. Magic-Square-CVN (Linked), 2026. GitHub repository with Python code.

[VV14]

Umesh Vazirani and Thomas Vidick. Fully device-independent quantum key distribution. Phys. Rev. Lett., 113:140501, Sep 2014.

[WBC25]

Lewis Wooltorton, Peter Brown, and Roger Colbeck. Genuine multipartite entanglement is not necessary for standard device-independent conference key agreement. Physical Review Letters, 135:220803, 2025.

[ZMZ+ 23]

Yi-Zheng Zhen, Yingqiu Mao, Yu-Zhe Zhang, Feihu Xu, and Barry C Sanders. Device-independent quantum key distribution based on the mermin-peres magic square game. Physical Review Letters, 131(8):080801, 2023.

29

Supplementary material A

Impossibility of a Multiparty Consensus Magic Square

In this section, we prove why a natural multiparty magic square game fails to be useful for a conference key agreement protocol, which motivates us to define pMSGN in the framework of Parity-G games. Definition A.1 (Literal multiparty magic square MSGN ). N parties: Alice and B1 , . . . , BN −1 . Alice receives a row x ∈ {0, 1, 2} and outputs an even triple a; each Bj receives the same column (j) y ∈ {0, 1, 2} (uniform) and outputs an odd triple b(j) . The players wins iff ay = bx for all j — Alice reaches cell-consensus with every Bob. (This is a consensus predicate: winning forces (1) (N −1) ay = bx = · · · = bx .) Theorem A.2 (Monogamy obstruction). ωQ (MSGN ) < 1 for every N ≥ 3. Hence MSGN is not a pseudo-telepathy game. Proof. Suppose a strategy wins MSGN with probability 1. Purify everything to a register |ψ⟩ on HA ⊗ HB1 ⊗ · · · ⊗ HBN −1 ⊗ HE . Step 1 (bipartite reduction). Fix any Bj . Marginalizing to (A, Bj ): Alice’s input x and Bj ’s input y are uniform and independent, Alice outputs an even triple, Bj an odd triple, and (j) the j-th winning clause ay = bx holds with certainty for every (x, y). Thus (A, Bj ) wins the bipartite magic square (Definition 3.3) with probability 1. Step 2 (self-test pins a single core). Alice performs one fixed measurement (her row observables), regardless of which Bob is considered. By the self-testing property of the Magic Square game [CS17], it is identical up to isometry in every application. Hence there is a single two-qubit core Acore ⊆ HA such that, for every j, perfect (A, Bj ) play forces Acore to be maximally entangled with Bj ’s core. (Alice cannot split into independent per-Bob cores: the Peres observables generate the full operator algebra on her two-qubit core, which acts irreducibly on C4 , so a single observable cannot act non-trivially on several independent cores.) Step 3 (monogamy). Apply Step 2 with j = 2: ρAcore ,B2 is pure maximally entangled. By Lemma 3.8, Acore is then in a product state with B3 , so the entanglement between Acore and B3 is zero. But Step 2 with j = 3 requires Acore maximally entangled with B3 (two ebits), which is a contradiction. Therefore no perfect strategy exists: ωQ (MSGN ) < 1. Remark A.3. The above theorem shows that the obvious idea for constructing a genuinely multipartite consensus pseudo-telepathy game of the magic-square form, for N ≥ 3, does not work. A DI conference key therefore cannot be extracted from this game, motivating the twobasis design of Section 5: a non-consensus certification test plus a separate consensus key basis. Our Parity-G games framework explicitly requires this in the form of test rounds and key rounds. We leave it as an intriguing open problem to construct a genuinely multipartite consensus pseudo-telepathy game, from which we could extract a DI conference key with a single measurement setting.

B

The Generalized Entropy Accumulation Theorem

We restate the full theorem here for reference, including the specific values of the constants c0 , c1 mentioned in the main text. Theorem B.1 (Generalized Entropy Accumulation Theorem (GEAT) [MFSR22]). Consider quantum channels Mi : Ri−1 Ei−1 → Ai Ri Ei , i ∈ {1, . . . , n}, satisfying the following nonsignaling condition: for each channel Mi , there exists a quantum channel Ri : Ei−1 → Ei such

30

that TrAi Ri ◦Mi = Ri ◦ TrRi−1 .

(48)

Then, for any initial state ρ0R0 E0 , the smooth min-entropy of the outputs An := A1 · · · An conditioned on the final side information En satisfies ε Hmin (An | En )M ◦···◦M ρ0 n 1

 ≥

R0 E 0

n X

  ei−1 inf H Ai | Ei E

i=1

ω

√ ≥ nh − c0 − c1 n ,

Mi (ω)

√ − O( n) ,

(49) (50)

ei−1 ≡ Ri−1 Ei−1 is a purifying system for the input to Mi , and the infimum is taken over where E ei−1 . The constants c0 and c1 are as follows, corresponding all states ω on the systems Ri−1 Ei−1 E to an affine min-tradeoff function f , with h = mincn ∈Ω f (freq(cn )). c0 :=

  (2 − η)η 2 log(1/ Prρn [Ω] + η 2 )g(ε) 1−η (2 log dA +Max(f )−MinΣ (f )) 3 2 log dA +Max(f )−MinΣ (f ) 2 η ln 2 + e , 2 3(ln 2)2 V 2 (2η − 1)3 s

c1 :=

2 ln(2)V 2 η



 g(ε) + (2 − η) log(1/ Pr[Ω]) , ρn

such that η :=

C

2 ln(2) , 1 + 2 ln(2)

  p g(ε) := − log 1 − 1 − ε2 ,

p V := log 2d2A + 1 + 2 + Var(f ) .

The Magic Square game strategy

Since the security of pMSG reduces to the security of the Magic Square game, as shown in Lemma 6.6, we simply analyze the latter. Our goal is to come up with a strategy for Eve in the Magic square game DI-QKD protocol, such that the entropy of Alice’s key bits is zero while obtaining a winning probability ω > 8/9, which is strictly greater than the best classical winning probability. We follow the idea introduced in [AW20], in the context of a DI-QKD protocol. We will design an attack from the perspective of the adversary Eve who prepares the devices that Alice and Bob use, and then calculate what winning probability we obtain. Recall that Alice and Bob both sample their inputs from the uniform distribution over {0, 1, 2}. When either device gets an input 0, this corresponds to measuring in the Z basis, which includes all key rounds and some test rounds. So the devices deterministically generate the same but known output bits (say 10) on such rounds. So, Eve learns all the key bits. Conversely, when either device gets either 1 or 2 as an input, this must be a test round. This new game now reduces to a CHSH game as shown in [AW20], where the input to a device is either 0 or from the set {1,2}. The devices play the optimal CHSH strategy on the latter inputs, winning with probability cos2 (π/8). Now, we can calculate the overall winning probability of this strategy for the Magic square game, with known key rounds inputs, as 5/9 · 1 + 4/9 · cos2 (π/8) ≈ 0.935. Perhaps surprisingly, this turns out to be greater than 8/9, concluding our argument. The optimality of this winning probability remains open, but an SDP calculation shows us that it cannot possibly be more than ≈ 0.945.

D

The Parallel Parity-CHSH game

Like pCHSH, the parallel Parity-CHSH game is also an N -player game, but where all players receive 2 sets of inputs, each input set corresponding to a pCHSH game. They win the parallel 31

game iff they win both pCHSH games. A similar argument to Lemma 6.6 would then show that this reduces to winning two CHSH games in parallel. We can design a conference key agreement protocol based on this game, similarly as the pCHSH is used for [RMW18]. Now, we could try comparing the key rates of the conference key protocol based on pMSG to the parallel Parity-CHSH game, between Alice and each of the Bobs. The honest strategy in both cases now is to share 2 GHZ states. But the optimal classical winning probability of both CHSH games in parallel is 5/8 = 0.625 which is greater than (3/4)2 = 9/16 = 0.5625 as we might expect. The optimal quantum winning probability now becomes cos4 (π/8) ≈ 0.7285 [Amb26]. It is unclear how this would change the key rates since we would need to re-derive bounds on H(A|E) and key rates for this new game. In particular, we could again try applying the method by [BFF24] to get lower bounds on the per round conditional von Neumann entropy of Parallel Parity-CHSH, which allows us to lower bound the key rate. We note that we expect its finite round key rate (as opposed to asymptotic key rate which is what we consider in the main text for simplicity) to be worse than that of pMSG when the key round probability is a constant, particularly in the low noise regime, due to the following fact. The conditional von Neumann entropy H(A|E) is calculated conditioned on Alice receiving a certain input, as described in Lemma 6.6. For the Parallel Parity-CHSH game, it would be conditional on Alice receiving the bits 00 as input, which occurs with probability 1/4. So, when the noise is zero, only 1/4’th of the key rounds will result in a valid key bit. Let there be a µ = 1 − γ fraction of key rounds over all rounds. Thus, H(A|E) = p(X = 00) · H(A|E, X = 00) = µ · 1/4 · 2 = µ/2 when the noise probability q = 0, and it will further decrease as q increases. The corresponding calculation for pMSG gives H(A|E) = µ · 1/3 · 2 = 2µ/3 > µ/2. For pCHSH, it is µ · 1/2 · 1 = µ/2. So, in the finite round, low noise regime, it suggests pMSG obtains better key rates over both these games. The asymptotic case would require a separate analysis. This also gives us some intuition why increasing the number of qubits shared between all parties per round in a conference key agreement doesn’t arbitrarily let us improve key rate, since the probability of a valid key round would naively go down. For M parallel CHSH games, we would get M bits of key on valid key rounds when the input to (say) Alice is 0M , but the probability of this is 2−M , which goes down exponentially as M increases. This suggests we may also need better formulations for asymptotic key rate calculations, since various current definitions would only analyze the key rate on valid key rounds when Alice’s input is 0M , which is clearly not indicative when running this experiment in a practical sense. We leave a tight comparison between the key rates obtained from pMSG, pCHSH and the Parallel Parity-CHSH game, as an interesting open question for future work. Disclaimer Case studies, comparisons, statistics, research and recommendations are provided “AS IS” and intended for informational purposes only and should not be relied upon for operational, marketing, legal, technical, tax, financial or other advice. Visa Inc. neither makes any warranty or representation as to the completeness or accuracy of the information within this document, nor assumes any liability or responsibility that may result from reliance on such information. The Information contained herein is not intended as investment or legal advice, and readers are encouraged to seek the advice of a competent professional where such advice is required. These materials and best practice recommendations are provided for informational purposes only and should not be relied upon for marketing, legal, regulatory or other advice. Recommended marketing materials should be independently evaluated in light of your specific business needs and any applicable laws and regulations. Visa is not responsible for your use of the marketing materials, best practice recommendations, or other information, including errors of any kind, contained in this document.

32

Related documents

• Device-Independent Conference Keys from Parity-Extended Games#1155960
• Enhancing noise robustness in device-independent conference key agreement with asymmetric parity-CHSH inequalities#926460
• Rotational Bell-State Loop-Back Key Establishment and Agreement Certification for Passive Users#972449
• CoCoA: Concurrent continuous group key agreement#665973
• Proof-of-principle long-distance Sagnac twin-field quantum key distribution network#927735