Document Open Access Logo

Quantum Coin Hedging, and a Counter Measure

Authors Maor Ganz, Or Sattath

PDF
Thumbnail PDF

File

LIPIcs.TQC.2017.4.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Maor Ganz
Or Sattath

Cite As Get BibTex

Maor Ganz and Or Sattath. Quantum Coin Hedging, and a Counter Measure. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.TQC.2017.4

Abstract

A quantum board game is a multi-round protocol between a single quantum player against the quantum board. Molina and Watrous discovered quantum hedging. They gave an example for perfect quantum hedging: a board game with winning probability < 1, such that the player can win with certainty at least 1-out-of-2 quantum board games played in parallel. Here we show that perfect quantum hedging occurs in a cryptographic protocol – quantum coin flipping. For this reason, when cryptographic protocols are composed in parallel, hedging may introduce serious challenges into their analysis.
We also show that hedging cannot occur when playing two-outcome board games in sequence. This is done by showing a formula for the value of sequential two-outcome board games, which depends only on the optimal value of a single board game; this formula applies in a more general setting of possible target functions, in which hedging is only a special case.

Subject Classification

Keywords
  • quantum coin hedging
  • quantum board games

Metrics

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

References

  1. Dorit Aharonov. Personal communication, 2007. Google Scholar
  2. Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, and Loïck Magnin. A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias. SIAM J. Comput., 45(3):633-679, 2016. URL: http://dx.doi.org/10.1137/14096387X.
  3. Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, and Andrew Chi-Chih Yao. Quantum bit escrow. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 705-714. ACM, 2000. URL: http://dx.doi.org/10.1145/335305.335404.
  4. Andris Ambainis. A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci., 68(2):398-416, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.07.010.
  5. Andris Ambainis, Harry Buhrman, Yevgenity Dodis, and Hein Rörig. Multiparty quantum coin flipping. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, pages 250-259. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/CCC.2004.19.
  6. Srinivasan Arunachalam, Abel Molina, and Vincent Russo. Quantum hedging in two-round prover-verifier interactions. arxiv preprint arxiv:1310.7954, 2013. URL: http://arxiv.org/abs/1310.7954.
  7. Manuel Blum. Coin flipping by telephone a protocol for solving impossible problems. SIGACT News, 15(1):23-27, 1983. URL: http://dx.doi.org/10.1145/1008908.1008911.
  8. André Chailloux, Gus Gutoski, and Jamie Sikora. Optimal bounds for semi-honest quantum oblivious transfer. Chicago J. Theor. Comput. Sci., 2016, 2016. URL: http://arxiv.org/abs/1310.3262.
  9. André Chailloux and Iordanis Kerenidis. Optimal quantum strong coin flipping. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 527-533. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.71.
  10. André Chailloux and Iordanis Kerenidis. Optimal bounds for quantum bit commitment. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 354-362. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.42.
  11. Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and its Applications, 10(3):285-290, 1975. URL: http://dx.doi.org/10.1016/0024-3795(75)90075-0.
  12. Richard Cleve. Limits on the security of coin flips when half the processors are faulty (extended abstract). In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 364-369. ACM, 1986. URL: http://dx.doi.org/10.1145/12130.12168.
  13. Gus Gutoski and John Watrous. Quantum interactive proofs with competing provers. In Volker Diekert and Bruno Durand, editors, STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings, volume 3404 of Lecture Notes in Computer Science, pages 605-616. Springer, 2005. URL: http://dx.doi.org/10.1007/978-3-540-31856-9_50.
  14. Rahul Jain, Sarvagya Upadhyay, and John Watrous. Two-message quantum interactive proofs are in PSPACE. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 534-543. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.30.
  15. Andrzej Jamiolkowski. Linear transformations which preserve trace and positive semidefiniteness of operators. Reports on Mathematical Physics, 3(4):275-278, 1972. URL: http://dx.doi.org/10.1016/0034-4877(72)90011-0.
  16. Alexei Kitaev. Quantum coin flipping. Talk at the 6th workshop on Quantum Information Processing, 2003. Google Scholar
  17. Hirotada Kobayashi. General properties of quantum zero-knowledge proofs. In Ran Canetti, editor, Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008., volume 4948 of Lecture Notes in Computer Science, pages 107-124. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-78524-8_7.
  18. Rajat Mittal and Mario Szegedy. Product rules in semidefinite programming. In Erzsébet Csuhaj-Varjú and Zoltán Ésik, editors, Fundamentals of Computation Theory, 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings, volume 4639 of Lecture Notes in Computer Science, pages 435-445. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74240-1_38.
  19. Carlos Mochon. Quantum weak coin-flipping with bias of 0.192. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 2-11. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.55.
  20. Carlos Mochon. Quantum weak coin flipping with arbitrarily small bias. arxiv preprint arxiv:0711.4114, 2007. URL: http://arxiv.org/abs/0711.4114.
  21. Abel Molina. Parallel repetition of prover-verifier quantum interactions. Arxiv preprint arXiv:1203.4885, 2012. Google Scholar
  22. Abel Molina and John Watrous. Hedging bets with correlated quantum strategies. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, pages 2614-2629, 2012. URL: http://dx.doi.org/10.1098/rspa.2011.0621.
  23. Anna Pappa, André Chailloux, Eleni Diamanti, and Iordanis Kerenidis. Practical quantum coin flipping. Phys. Rev. A, 84:052305, 2011. URL: http://dx.doi.org/10.1103/PhysRevA.84.052305.
  24. Anna Pappa, Paul Jouguet, Thomas Lawson, André Chailloux, Matthieu Legré, Patrick Trinkler, Iordanis Kerenidis, and Eleni Diamanti. Experimental plug and play quantum coin flipping. Nature Communications, 5, 2014. Article. URL: http://dx.doi.org/10.1038/ncomms4717.
  25. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. URL: http://dx.doi.org/10.1137/S0097539795280895.
  26. Robert W. Spekkens and Terry Rudolph. Degrees of concealments and bindingness in quantum bit commitment protocols. Physical Review A, 65(01):012310, 2001. URL: http://dx.doi.org/10.1103/PhysRevA.65.012310.
  27. John Watrous. Theory of quantum information. Available online, 2011. URL: https://cs.uwaterloo.ca/~watrous/TQI/.
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 About DROPS Imprint Privacy Contact