A monogamy-of-entanglement game for subspace coset states

Eric Culf1 and Thomas Vidick2

1Department of Mathematics and Statistics, University of Ottawa, Canada
2Department of Computing and Mathematical Sciences, California Institute of Technology, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We establish a strong monogamy-of-entanglement property for subspace coset states, which are uniform superpositions of vectors in a linear subspace of $\mathbb{F}_2^n$ to which has been applied a quantum one-time pad. This property was conjectured recently by [Coladangelo, Liu, Liu, and Zhandry, Crypto'21] and shown to have applications to unclonable decryption and copy-protection of pseudorandom functions. We present two proofs, one which directly follows the method of the original paper and the other which uses an observation from [Vidick and Zhang, Eurocrypt'20] to reduce the analysis to a simpler monogamy game based on BB'84 states. Both proofs ultimately rely on the same proof technique, introduced in [Tomamichel, Fehr, Kaniewski and Wehner, New Journal of Physics '13].

Quantum entanglement allows for correlations between two non-communicating systems that are classically impossible, a property that may be quantified using Bell inequalities or nonlocal games. The situation gets more involved when there are more parties. For example, correlations as strong as maximal entanglement are not possible between three quantum systems. This is a particular case of monogamy-of-entanglement — limitations on the strength of quantum multipartite correlations. One way to quantify this property is via monogamy-of-entanglement (MoE) games. An MoE game is played cooperatively by two players Bob and Charlie, who each hold a quantum system but do not communicate, against a referee Alice, who has fixed actions. The players win if they can both simultaneously guess the result of Alice's measurement, chosen at random from a predetermined set of possible measurements, on a state they have prepared, each using their own local quantum system. Monogamy-of-entanglement appears in the fact that the maximal winning probability may be low while, using a maximally entangled state, either one of the players could have guessed the result with certainty.

In this work, we study the winning probability of an MoE game called the strong monogamy game. In this game, Alice measures her $n$-qubit system in a basis of subspace coset states, which is a basis that arises from a linear subspace of the finite vector space of $n$ bits. An important property of this basis is that it is naturally indexed by two indices, one corresponding to a coset of the subspace and the other to a coset of its orthogonal complement. To win the game, Bob is only required to guess the first index correctly and Charlie is only required to guess the second. Nevertheless, we show that the optimal winning probability is exponentially small in the number of qubits. The bound also holds for a version of the game where Alice sends subspace coset states rather than measuring in a basis; this version has applications to uncloneable quantum cryptography, where the no-cloning property of quantum states, closely related to MoE, is exploited to achieve classically impossible security.

► BibTeX data

► References

[1] V. V. Albert, J. P. Covey, and J. Preskill. Robust encoding of a qubit in a molecule. Physical Review X, 10(3), 2020. DOI: 10.1103/​physrevx.10.031050.

[2] A. Coladangelo, J. Liu, Q. Liu, and M. Zhandry. Hidden cosets and applications to unclonable cryptography. In T. Malkin and C. Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 556–584, Cham, 2021. Springer International Publishing. DOI: 10.1007/​978-3-030-84242-0_20.

[3] N. Johnston, R. Mittal, V. Russo, and J. Watrous. Extended non-local games and monogamy-of-entanglement games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 472(2189): 20160003, 2016. DOI: 10.1098/​rspa.2016.0003.

[4] M. Koashi. Unconditional security of quantum key distribution and the uncertainty principle. In Journal of Physics: Conference Series, volume 36, page 016. IOP Publishing, 2006. DOI: 10.1088/​1742-6596/​36/​1/​016.

[5] M. Tomamichel, S. Fehr, J. Kaniewski, and S. Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10): 103002, 2013. DOI: 10.1088/​1367-2630/​15/​10/​103002.

[6] M. Tomamichel and A. Leverrier. A largely self-contained and complete security proof for quantum key distribution. Quantum, 1: 14, 2017. DOI: 10.22331/​q-2017-07-14-14.

[7] T. Vidick and T. Zhang. Classical proofs of quantum knowledge. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 630–660. Springer, 2021. DOI: 10.1007/​978-3-030-77886-6_22.

Cited by

[1] Prabhanjan Ananth, Fatih Kaleoglu, and Qipeng Liu, Lecture Notes in Computer Science 14085, 66 (2023) ISBN:978-3-031-38553-7.

[2] Fuyuki Kitagawa and Ryo Nishimaki, Lecture Notes in Computer Science 13794, 569 (2022) ISBN:978-3-031-22971-8.

[3] Fuyuki Kitagawa and Ryo Nishimaki, Lecture Notes in Computer Science 14372, 246 (2023) ISBN:978-3-031-48623-4.

[4] Céline Chevalier, Paul Hermouet, and Quoc-Huy Vu, Lecture Notes in Computer Science 14372, 155 (2023) ISBN:978-3-031-48623-4.

[5] Shweta Agrawal, Fuyuki Kitagawa, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa, Lecture Notes in Computer Science 14004, 581 (2023) ISBN:978-3-031-30544-3.

[6] Jiahui Liu, Qipeng Liu, Luowen Qian, and Mark Zhandry, Lecture Notes in Computer Science 13747, 294 (2022) ISBN:978-3-031-22317-4.

[7] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry, Lecture Notes in Computer Science 13508, 212 (2022) ISBN:978-3-031-15978-7.

[8] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry, "Hidden Cosets and Applications to Unclonable Cryptography", arXiv:2107.05692, (2021).

[9] Prabhanjan Ananth, Fatih Kaleoglu, and Qipeng Liu, "Cloning Games: A General Framework for Unclonable Primitives", arXiv:2302.01874, (2023).

[10] Anne Broadbent and Eric Culf, "Uncloneable Cryptographic Primitives with Interaction", arXiv:2303.00048, (2023).

[11] Fuyuki Kitagawa and Ryo Nishimaki, "Functional Encryption with Secure Key Leasing", arXiv:2209.13081, (2022).

[12] Anne Broadbent and Eric Culf, "Rigidity for Monogamy-of-Entanglement Games", arXiv:2111.08081, (2021).

[13] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry, "On the Feasibility of Unclonable Encryption, and More", arXiv:2207.06589, (2022).

[14] Or Sattath and Uriel Shinar, "Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism", arXiv:2212.08750, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 13:58:16) and SAO/NASA ADS (last updated successfully 2024-05-21 13:58:16). The list may be incomplete as not all publishers provide suitable and complete citation data.