Document Open Access Logo

Simple, Near-Optimal Quantum Protocols for Die-Rolling

Author Jamie Sikora

PDF
Thumbnail PDF

File

LIPIcs.TQC.2016.4.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Jamie Sikora

Cite As Get BibTex

Jamie Sikora. Simple, Near-Optimal Quantum Protocols for Die-Rolling. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.TQC.2016.4

Abstract

Die-rolling is the cryptographic task where two mistrustful, remote parties wish to generate a random D-sided die-roll over a communication channel. Optimal quantum protocols for this task have been given by Aharon and Silman (New Journal of Physics, 2010) but are based on optimal weak coin-flipping protocols which are currently very complicated and not very well understood. In this paper, we first present very simple classical protocols for die-rolling which have decent (and sometimes optimal) security which is in stark contrast to coin-flipping, bit-commitment, oblivious transfer, and many other two-party cryptographic primitives. We also present quantum protocols based on the idea of integer-commitment, a generalization of bit-commitment, where one wishes to commit to an integer. We analyze these protocols using semidefinite programming and finally give protocols which are very close to Kitaev's lower bound for any D >= 3.

Subject Classification

Keywords
  • Quantum Cryptography
  • Semidefinite Programming
  • Die-Rolling
  • Integer-Commitment

Metrics

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

References

  1. N. Aharon and J. Silman. Quantum dice rolling: a multi-outcome generalization of quantum coin flipping. New Journal of Physics, 12(3):033027, 2010. Google Scholar
  2. Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, and Loïck Magnin. A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias. SIAM Journal of Computing, to appear, 2016. Google Scholar
  3. Dorit Aharonov, Amnon Ta-Shma, Umesh Vazirani, and Andrew Chi-Chih Yao. Quantum bit escrow. In Proceedings of 32nd Annual ACM Symposium on the Theory of Computing, 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. In Proceedings of 33rd Annual ACM Symposium on the Theory of Computing, pages 134-142. ACM, 2001. URL: http://dx.doi.org/10.1109/FOCS.2004.13.
  5. Manuel Blum. Coin flipping by telephone. In Allen Gersho, editor, Advances in Cryptology: A Report on CRYPTO 81, CRYPTO 81, IEEE Workshop on Communications Security, Santa Barbara, California, USA, August 24-26, 1981, pages 11-15. U. C. Santa Barbara, Dept. of Elec. and Computer Eng., ECE Report No. 82-04, 1982, 1981. Google Scholar
  6. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Google Scholar
  7. Harry Buhrman, Matthias Christandl, Patrick Hayden, Hoi-Kwong Lo, and Stephanie Wehner. Possibility, impossibility, and cheat-sensitivity of quantum bit string commitment. Phys. Rev. A, 78:022316, 2008. Google Scholar
  8. André Chailloux and Iordanis Kerenidis. Optimal quantum strong coin flipping. In Proceedings of 50th IEEE Symposium on Foundations of Computer Science, pages 527-533. IEEE Computer Society, 2009. Google Scholar
  9. André Chailloux and Iordanis Kerenidis. Optimal bounds for quantum bit commitment. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 354-362. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.42.
  10. André Chailloux, Iordanis Kerenidis, and Jamie Sikora. Lower bounds for quantum oblivious transfer. Quantum Information &Computation, 13(1 & 2):158-177, 2013. Google Scholar
  11. Rahul Jain. New binding-concealing trade-offs for quantum string commitment. Journal of Cryptology, 21:579-592, 2008. Google Scholar
  12. Adrian Kent. Quantum bit string commitment. Phys. Rev. Lett., 90:237901, 2003. Google Scholar
  13. Iordanis Kerenidis and Ashwin Nayak. Weak coin flipping with small bias. Information Processing Letters, 89(3):131-135, 2004. URL: http://dx.doi.org/10.1016/j.ipl.2003.07.007.
  14. Alexei Kitaev. Quantum coin-flipping. Unpublished result. Talk at the 6th Annual workshop on Quantum Information Processing (QIP 2003), 2002. Google Scholar
  15. Carlos Mochon. A large family of quantum weak coin-flipping protocols. Physical Review A, 72:022341, 2005. URL: http://arxiv.org/abs/quant-ph/0502068, URL: http://dx.doi.org/10.1103/PhysRevA.72.022341.
  16. Carlos Mochon. Quantum weak coin flipping with arbitrarily small bias. Available as arXiv.org e-Print quant-ph/0711.4114, 2007. Google Scholar
  17. Ashwin Nayak and Peter W. Shor. Bit-commitment based quantum coin flipping. Physical Review A, 67:012304, 2003. URL: http://dx.doi.org/10.1103/PhysRevA.67.012304.
  18. 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
  19. 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
  20. 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.
  21. Toyohiro Tsurumaru. Implementable quantum bit-string commitment protocol. Phys. Rev. A, 71:012313, 2005. Google Scholar
  22. Toyohiro Tsurumaru. Group covariant protocols for quantum string commitment. Phys. Rev. A, 74:042307, 2006. Google Scholar
  23. A. Uhlmann. The "transition probability" in the state space of a *-algebra. Reports on Mathematical Physics, 9(2):273-279, 1976. Google Scholar
  24. John Watrous. Semidefinite programs for completely bounded norms. Theory of Computing, 5:217-238, 2009. Google Scholar
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