A new protocol and lower bounds for quantum coin flipping

ABSTRACT

We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols.For arbitrary quantum protocols, we show that if a protocol achieves a bias of at most epsilon, it must use at least \Omega(\log \log \frac{1}{\epsilon}) rounds of communication. This implies that the parallel repetition fails for quantum coin flipping. (The bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel.)

REFERENCES

• 1: Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
• 2: Dorit Aharonov , Amnon Ta-Shma , Umesh V. Vazirani , Andrew C. Yao, Quantum bit escrow, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.705-714, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335404]
• 3: C. Bennett, G. Brassard. Quantum cryptography: public-key distribution and coin tossing. Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, pp. 175-179, Bangalore, India, 1984.
• 4: Eli Biham , Michel Boyer , P. Oscar Boykin , Tal Mor , Vwani Roychowdhury, A proof of the security of quantum key distribution (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.715-724, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335406]
• 5: M. Blum. Coin ipping by telephone: A protocol for solving impossible problems. Advances in Cryptology: Report on CRYPTO'81, pp. 11-15.
• 6: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 7: Claude Crépeau , Frédéric Légaré , Louis Salvail, How to Convert the Flavor of a Quantum Bit Commitment, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.60-77, May 06-10, 2001
• 8: P. Dumais, D. Mayers, L. Salvail. Perfectly concealing quantum bit commitment fromany quantum one-way permutation. Advances in Cryptology: EUROCRYPT 2000: Proceedings, Lecture Notes in Computer Science, 1807:300-315, Springer, Berlin, 2000.
• 9: C. Fuchs, J. van der Graaf. Cryptographic distinguishability measures for quantum mechanical states. IEEE Transactions on Information Theory, 45:1216-1227, 1999.
• 10: L. Goldenberg, L. Vaidman, S. Wiesner. Quantum gambling. Physical Review Letters, 82:3356-3359, 1999.
• 11: D. Gottesman and H.-K. Lo. From quantum cheating to quantum security. Physics Today, 53, no. 11, pp. 22-27.
• 12: D. Gottesman, D. Simon. Personal communication, January 2001.
• 13: R. Jozsa. Fidelity for mixed quantum states. Journal of Modern Optics, 41:2315-2323, 1994.
• 14: B. Leslau. Attacks on symmetric quantum coin-tossing protocols, quant-ph/0104075.
• 15: H. Lo. Insecurity ofquantum secure computations. Physical Review A, 56:1154-1162, 1997.
• 16: H. Lo, H. Chau. Is quantum bit commitment really possible? Physical Review Letters, 78:3410-3413, 1997.
• 17: Hoi-Kwong Lo , H. F. Chau, Why quantum bit commitment and ideal quantum coin tossing are impossible, Physica D, v.120 n.1-2, p.177-187, Sept. 1998
• 18: H. Lo, H. Chau. Unconditional security of quantum key distribution over arbitrarily long distances. Science, 283:2050-2056, 1999.
• 19: D. Mayers. Unconditionally secure quantum bit commitment is impossible. Physical Review Letters, 78:3414-3417, 1997.
• 20: Dominic Mayers, Unconditional security in quantum cryptography, Journal of the ACM (JACM), v.48 n.3, p.351-406, May 2001 [doi>10.1145/382780.382781]
• 21: D. Mayers, L. Salvail, Y. Chiba-Kohno. Unconditionally secure quantum coin-tossing. quant-ph/9904078.
• 22: Hartmut Klauck , Ashwin Nayak , Amnon Ta-Shma , David Zuckerman, Interaction in quantum communication and the complexity of set disjointness, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.124-133, July 2001, Hersonissos, Greece [doi>10.1145/380752.380786]
• 23: M. Nielsen. Conditions for a class of entanglement transformations. Physical Review Letters, 83:436-439, 1999.
• 24: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 25: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 26: P. Shor, J. Preskill. Simple proof of security of the BB84 quantum key distribution protocol. Physical Review Letters, 85:441-444, 2000.
• 27: A. Uhlmann. The 'transition probability' in the state space of *-algebra. Reports on Mathematical Physics, 9:273-279, 1976.
• 28: Y. Zhang, C. Li, G. Guo. Unconditionally secure quantum coin tossing via entanglement swapping, quant-ph/0012139.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing

General Terms:
Design, Performance, Standardization, Theory, Verification