Fidelity of Quantum Strategies with Applications to Cryptography

Authors Gus Gutoski, Ansis Rosmanis, Jamie Sikora



PDF
Thumbnail PDF

File

LIPIcs.TQC.2017.8.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Gus Gutoski
Ansis Rosmanis
Jamie Sikora

Cite AsGet BibTex

Gus Gutoski, Ansis Rosmanis, and Jamie Sikora. Fidelity of Quantum Strategies with Applications to Cryptography. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.TQC.2017.8

Abstract

We introduce a definition of the fidelity function for multi-round quantum strategies, which we call the strategy fidelity, that is a generalization of the fidelity function for quantum states. We provide many interesting properties of the strategy fidelity including a Fuchs-van de Graaf relationship with the strategy norm. We illustrate an operational interpretation of the strategy fidelity in the spirit of Uhlmann's Theorem and discuss its application to the security analysis of quantum protocols for interactive cryptographic tasks such as bit-commitment and oblivious string transfer. Our analysis is very general in the sense that the actions of the protocol need not be fully specified, which is in stark contrast to most other security proofs. Lastly, we provide a semidefinite programming formulation of the strategy fidelity.
Keywords
  • Quantum strategies
  • cryptography
  • fidelity
  • semidefinite programming

Metrics

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

References

  1. Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, and Hein Röhrig. 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.
  2. Viacheslav P. Belavkin, Giacomo Mauro D'Ariano, and Maxim Raginsky. Operational distance and fidelity for quantum channels. Journal of Mathematical Physics, 46(6):062106, 2005. arXiv:quant-ph/0408159. Google Scholar
  3. Charles 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. IEEE Computer Society, 1984. Google Scholar
  4. André Chailloux, Gus Gutoski, and Jamie Sikora. Optimal bounds for semi-honest quantum oblivious transfer. Chicago Journal of Theoretical Computer Science, 2016. Google Scholar
  5. André Chailloux and Iordanis Kerenidis. Optimal quantum strong coin flipping. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, FOCS 2009, pages 527-533, 2009. arXiv:0904.1511 [quant-ph]. Google Scholar
  6. 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.
  7. André Chailloux, Iordanis Kerenidis, and Jamie Sikora. Lower bounds for quantum oblivious transfer. Quantum Information and Computation, 13(1&2):158-177, 2013. arXiv:1007.1875 [quant-ph]. Google Scholar
  8. André Chailloux, Iordanis Kerenidis, and Jamie Sikora. Strong connections between quantum encodings, nonlocality, and quantum cryptography. Phys. Rev. A, 89:022334, 2014. arXiv:1304.0983 [quant-ph]. Google Scholar
  9. Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Theoretical framework for quantum networks. Physical Review A, 80(2):022339, 2009. arXiv:0904.4483 [quant-ph]. Google Scholar
  10. Giulio Chiribella, Giacomo Mauro D'Ariano, Paolo Perinotti, Dirk Schlingemann, and Reinhard F. Werner. A short impossibility proof of quantum bit commitment. Physics Letters A, 377(15):1076-1087, 2013. arXiv:0905.3801v1 [quant-ph]. Google Scholar
  11. Gus Gutoski. Quantum strategies and local operations. PhD thesis, University of Waterloo, 2009. arXiv:1003.0038 [quant-ph]. Google Scholar
  12. Gus Gutoski. On a measure of distance for quantum strategies. Journal of Mathematical Physics, 53(3):032202, 2012. arXiv:1008.4636 [quant-ph]. Google Scholar
  13. Gus Gutoski and John Watrous. Toward a general theory of quantum games. In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pages 565-574, 2007. arXiv:quant-ph/0611234. Google Scholar
  14. Iordanis Kerenidis and Ashwin Nayak. Weak coin flipping with small bias. Information Processing Letters, 89(3):131-135, 2004. arXiv:quant-ph/0206121. URL: http://dx.doi.org/10.1016/j.ipl.2003.07.007.
  15. Alexei Kitaev. Quantum coin-flipping. Presentation at the 6th Workshop on Quantum Information Processing (QIP 2003), 2002. Google Scholar
  16. Hoi-Kwong Lo and Hoi Fung Chau. Is quantum bit commitment really possible? Physical Review Letters, 78(17):3410-3413, 1997. URL: http://dx.doi.org/10.1103/PhysRevLett.78.3410.
  17. Hoi-Kwong Lo and Hoi Fung Chau. Why quantum bit commitment and ideal quantum coin tossing are impossible. Physica D: Nonlinear Phenomena, 120(1-2):177-187, 1998. Proceedings of the Fourth Workshop on Physics and Consumption. URL: http://dx.doi.org/10.1016/S0167-2789(98)00053-0.
  18. Dominic Mayers. Unconditionally secure quantum bit commitment is impossible. Physical Review Letters, 78(17):3414-3417, 1997. URL: http://dx.doi.org/10.1103/PhysRevLett.78.3414.
  19. Ashwin Nayak and Peter Shor. Bit-commitment based quantum coin flipping. Physical Review A, 67(1):012304, 2003. arXiv:quant-ph/0206123. URL: http://dx.doi.org/10.1103/PhysRevA.67.012304.
  20. Ashwin Nayak, Jamie Sikora, and Levent Tunçel. Quantum and classical coin-flipping protocols based on bit-commitment and their point games. Available as arXiv.org e-Print quant-ph/1504.04217, 2015. Google Scholar
  21. Ashwin Nayak, Jamie Sikora, and Levent Tunçel. A search for quantum coin-flipping protocols using optimization techniques. Mathematical Programming, 156(1):581-613, 2016. Google Scholar
  22. Jamie Sikora. Simple, near-optimal quantum protocols for die-rolling. In Theory of Quantum Computation, Communication and Cryptography (TQC 2016), pages 1-14, 2016. Google Scholar
  23. Robert W. Spekkens and Terence Rudolph. Degrees of concealment and bindingness in quantum bit commitment protocols. Physical Review A, 65:012310, 2001. URL: http://dx.doi.org/10.1103/PhysRevA.65.012310.
  24. A. Uhlmann. The "transition probability" in the state space of a *-algebra. Reports on Mathematical Physics, 9(2):273-279, 1976. Google Scholar
  25. Salil P. Vadhan. An unconditional study of computational zero knowledge. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 176-185. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.13.
  26. John Watrous. Semidefinite programs for completely bounded norms. Theory of Computing, 5:217-238, 2009. arXiv:0901.4709v2 [quant-ph]. Google Scholar
  27. John Watrous. Simpler semidefinite programs for completely bounded norms. Chicago Journal of Theoretical Computer Science, 2013. Google Scholar
  28. Stephen Wiesner. Conjugate coding. SIGACT News, 15(1):78-88, 1983. URL: http://dx.doi.org/10.1145/1008908.1008920.
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