Document Open Access Logo

Rigidity for Monogamy-Of-Entanglement Games

Authors Anne Broadbent, Eric Culf

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.28.pdf
  • Filesize: 0.96 MB
  • 29 pages

Document Identifiers

Author Details

Anne Broadbent
  • Department of Mathematics and Statistics, University of Ottawa, Canada
Eric Culf
  • Department of Mathematics and Statistics, University of Ottawa, Canada

Funding

Funded by the Air Force Office of Scientific Research under award number FA9550-20-1-0375, Canada’s NFRF and NSERC, an Ontario ERA, and the University of Ottawa’s Research Chairs program.

Acknowledgements

We would like to thank Arthur Mehta for introducing us to sum-of-squares decompositions, and Sébastien Lord for many insightful discussions.

Cite AsGet BibTex

Anne Broadbent and Eric Culf. Rigidity for Monogamy-Of-Entanglement Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 28:1-28:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.28

Abstract

In a monogamy-of-entanglement (MoE) game, two players who do not communicate try to simultaneously guess a referee’s measurement outcome on a shared quantum state they prepared. We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis and informs the players of her choice. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. That is, in order to win optimally, the players' strategy must be of a specific form, namely a convex combination of four unentangled optimal strategies generated by the Breidbart state. We extend this to show that strategies that win near-optimally must also be near an optimal state of this form. We also show rigidity for multiple copies of the game played in parallel. We give three applications: (1) We construct for the first time a weak string erasure (WSE) scheme where the security does not rely on limitations on the parties' hardware. Instead, we add a prover, which enables security via the rigidity of this MoE game. (2) We show that the WSE scheme can be used to achieve bit commitment in a model where it is impossible classically. (3) We achieve everlasting-secure randomness expansion in the model of trusted but leaky measurement and untrusted preparation and measurements by two isolated devices, while relying only on the temporary assumption of pseudorandom functions. This achieves randomness expansion without the need for shared entanglement.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Cryptographic primitives
  • Security and privacy → Mathematical foundations of cryptography
Keywords
  • Rigidity
  • Self-Testing Monogamy-of-Entanglement Games
  • Bit Commitment
  • Randomness Expansion

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Antonio Acín and Lluis Masanes. Certified randomness in quantum physics. Nature, 540:213-219, December 2016. URL: https://doi.org/10.1038/nature20119.
  2. Cédric Bamps and Stefano Pironio. Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing. Physical Review A, 91(5), 2015. URL: https://doi.org/10.1103/physreva.91.052111.
  3. Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Widgerson. Multi-prover interactive proofs: how to remove intractability assumptions. In 20th Annual ACM Symposium on Theory of Computing - STOC 1988, pages 113-131, 1988. URL: https://doi.org/10.1145/62212.62223.
  4. Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In 59th Annual Symposium on Foundations of Computer Science - FOCS 2018, pages 320-331, 2018. URL: https://doi.org/10.1109/FOCS.2018.00038.
  5. 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. Phys. Rev. A, 85:010301, January 2012. URL: https://doi.org/10.1103/PhysRevA.85.010301.
  6. Anne Broadbent and Sébastien Lord. Uncloneable quantum encryption via oracles. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography - TQC 2020, pages 4:1-4:22, 2020. URL: https://doi.org/10.4230/LIPIcs.TQC.2020.4.
  7. Anne Broadbent and Christian Schaffner. Quantum cryptography beyond quantum key distribution. Designs, Codes and Cryptography, 78(1):351-382, 2016. URL: https://doi.org/10.1007/s10623-015-0157-4.
  8. 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-884, 1969. URL: https://doi.org/10.1103/PhysRevLett.23.880.
  9. Andrea Coladangelo. Parallel self-testing of (tilted) EPR pairs via copies of (tilted) CHSH and the magic square game. Quantum Information & Computation, 17(9-10):831-865, 2017. URL: https://doi.org/10.5555/3179561.3179567.
  10. Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. Hidden cosets and applications to unclonable cryptography. In Advances in Cryptology - CRYPTO 2021, pages 556-584, 2021. URL: https://doi.org/10.1007/978-3-030-84242-0_20.
  11. Roger Colbeck. Quantum And Relativistic Protocols For Secure Multi-Party Computation. PhD thesis, University of Cambridge, UK, 2006. URL: http://arxiv.org/abs/0911.3814.
  12. Matthew Coudron and Henry Yuen. Infinite randomness expansion with a constant number of devices. In 46th Annual ACM Symposium on Theory of Computing - STOC 2014, pages 427-436, 2014. URL: https://doi.org/10.1145/2591796.2591873.
  13. Claude Crépeau, Louis Salvail, Jean-Raymond Simard, and Alain Tapp. Two provers in isolation. In Advances in Cryptology - ASIACRYPT 2011, pages 407-430, 2011. URL: https://doi.org/10.1007/978-3-642-25385-0_22.
  14. David Cui, Arthur Mehta, Hamoon Mousavi, and Seyed Sajjad Nezhadi. A generalization of CHSH and the algebraic structure of optimal strategies. Quantum, 4:346, 2020. URL: https://doi.org/10.22331/q-2020-10-21-346.
  15. Eric Culf and Thomas Vidick. A monogamy-of-entanglement game for subspace coset states. Quantum, 6:791, September 2022. URL: https://doi.org/10.22331/q-2022-09-01-791.
  16. W T Gowers and O Hatami. Inverse and stability theorems for approximate representations of finite groups. Sbornik: Mathematics, 208(12):1784-1817, 2017. URL: https://doi.org/10.1070/sm8872.
  17. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP^* = RE. Communications of the ACM, 64(11):131-138, 2021. URL: https://doi.org/10.1145/3485628.
  18. Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous. Extended non-local games and monogamy-of-entanglement games. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 472(2189):20160003, 2016. URL: https://doi.org/10.1098/rspa.2016.0003.
  19. Robert König, Stephanie Wehner, and Jürg Wullschleger. Unconditional security from noisy quantum storage. IEEE Transactions on Information Theory, 58(3):1962-1984, 2012. URL: https://doi.org/10.1109/TIT.2011.2177772.
  20. Hong-Wei Li, Zhen-Qiang Yin, Yu-Chun Wu, Xu-Bo Zou, Shuang Wang, Wei Chen, Guang-Can Guo, and Zheng-Fu Han. Semi-device-independent random-number expansion without entanglement. Phys. Rev. A, 84:034301, September 2011. URL: https://doi.org/10.1103/PhysRevA.84.034301.
  21. Hoi-Kwong Lo and H .F. Chau. Is quantum bit commitment really possible? Physical Review Letters, 78(17):3410-3413, 1997. URL: https://doi.org/10.1103/PhysRevLett.78.3410.
  22. Laura Mančinska, Thor Gabelgaard Nielsen, and Jitendra Prakash. Glued magic games self-test maximally entangled states, 2021. Available at https://arxiv.org/abs/2105.10658. URL: http://arxiv.org/abs/2105.10658.
  23. Dominic Mayers. The trouble with quantum bit commitment, 1996. URL: http://arxiv.org/abs/9603015.
  24. Dominic Mayers and Andrew Yao. Self testing quantum apparatus. Quantum Information & Computation, 4(4):273-286, 2004. URL: http://dl.acm.org/citation.cfm?id=2011827.2011830.
  25. M. McKague, T. H. Yang, and V. Scarani. Robust self-testing of the singlet. Journal of Physics A, 45(45):455304, 2012. URL: https://doi.org/10.1088/1751-8113/45/45/455304.
  26. Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In 49th Annual ACM Symposium on Theory of Computing - STOC 2017, pages 1003-1015, 2017. URL: https://doi.org/10.1145/3055399.3055468.
  27. Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, 2008. URL: https://doi.org/10.1088/1367-2630/10/7/073013.
  28. Michael A. Nielsen and Issac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  29. Narutaka Ozawa. About the Connes Embedding Conjecture - Algebraic approaches - , 2013. Available at https://arxiv.org/abs/1212.1700. URL: http://arxiv.org/abs/1212.1700.
  30. Marcin Pawłowski and Nicolas Brunner. Semi-device-independent security of one-way quantum key distribution. Physical Review A, 84:010302, July 2011. URL: https://doi.org/10.1103/PhysRevA.84.010302.
  31. Ben W. Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. Nature, 496:456-460, 2013. URL: https://doi.org/10.1038/nature12035.
  32. Jean-Pierre. Serre. Linear representations of finite groups. Graduate texts in mathematics ; 042. Springer-Verlag, New York, 1977. Google Scholar
  33. Douglas Stebila, Michele Mosca, and Norbert Lütkenhaus. The case for quantum key distribution. In Quantum Communication and Quantum Networking, volume 36, pages 283-296, 2010. URL: https://doi.org/10.1007/978-3-642-11731-2_35.
  34. Marco. Tomamichel. Quantum Information Processing with Finite Resources Mathematical Foundations. SpringerBriefs in Mathematical Physics, 5. Springer International Publishing, Cham, 2016. Google Scholar
  35. Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10):103002, 2013. URL: https://doi.org/10.1088/1367-2630/15/10/103002.
  36. B. S. Tsirelson. Some results and problems on quantum Bell-type inequalities. Hadronic Journal Supplement, 8:329-345, 1993. Google Scholar
  37. Dominique Unruh. Everlasting multi-party computation. In Advances in Cryptology - CRYPTO 2013, pages 380-397, 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_22.
  38. Umesh V. Vazirani and Thomas Vidick. Certifiable quantum dice: or, true random number generation secure against quantum adversaries. In 44th Annual ACM Symposium on Theory of Computing - STOC 2012, pages 61-76, 2012. URL: https://doi.org/10.1145/2213977.2213984.
  39. Thomas Vidick. Expository note based on [NV17], 2018. URL: http://users.cms.caltech.edu/~vidick/notes/pauli_braiding_1.pdf.
  40. John Watrous. The Theory of Quantum Information. Cambridge University Press, 1superscriptst edition, 2018. Google Scholar
  41. Steven H. Weintraub. Representation theory of finite groups : algebra and arithmetic. Graduate studies in mathematics, v. 59. American Mathematical Society, Providence, R.I, 2003. Google Scholar
  42. Yu-Guang Yang, Peng Xu, Ju Tian, and Hua Zhang. Quantum oblivious transfer with an untrusted third party. Optik, 125(18):5409-5413, 2014. URL: https://doi.org/10.1016/j.ijleo.2014.06.023.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact