On bit-commitment based quantum coin flipping

Nayak, Ashwin and Shor, Peter (2002) On bit-commitment based quantum coin flipping. Technical Report. California Institute of Technology. [CaltechCSTR:2002.004]

Full text available as:

	Postscript - Requires a viewer, such as GhostView
	PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

In this paper, we focus on a special framework for quantum coin flipping protocols, {\em bit-commitment based protocols}, within which almost all known protocols fit. We show a lower bound of~$1/16$ for the bias in any such protocol. We also analyse a sequence of multi-round protocol that tries to overcome the drawbacks of the previously proposed protocols, in order to lower the bias. We show an intricate cheating strategy for this sequence, which leads to a bias of~$1/4$. This indicates that a bias of~$1/4$ might be optimal in such protocols, and also demonstrates that a cleverer proof technique may be required to show this optimality.

EPrint Type:	Monograph (Technical Report)
Uncontrolled Keywords:	coin flipping, bit commitment, quantum cryptography
Subjects:	All Records
ID Code:	327
Deposited By:	Ashwin Nayak
Deposited On:	23 April 2002
Record Number:	CaltechCSTR:2002.004
Official Persistent URL:	http://resolver.caltech.edu/CaltechCSTR:2002.004
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record