Optimal quantum strong coin flipping
Preprint
Abstract
Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit [Blu81]. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4 [Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than $1/\sqrt{2}$ [Kit03]. Closing this gap has been one of the important open questions in quantum cryptography. In this paper, we resolve this question by presenting a quantum strong coin flipping protocol with cheating probability arbitrarily close to $1/\sqrt{2}$. More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2+\epsilon$ in order to achieve a strong coin flipping protocol with cheating probability $1/\sqrt{2}+O(\epsilon)$. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon [Moc07].
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Reexamination of quantum bit commitment: The possible and the impossiblePhysical Review A, 2007
- Large family of quantum weak coin-flipping protocolsPhysical Review A, 2005
- Cheat Sensitive Quantum Bit CommitmentPhysical Review Letters, 2004
- Weak coin flipping with small biasInformation Processing Letters, 2004
- Bit-commitment-based quantum coin flippingPhysical Review A, 2003
- Quantum Protocol for Cheat-Sensitive Weak Coin FlippingPhysical Review Letters, 2002
- Degrees of concealment and bindingness in quantum bit commitment protocolsPhysical Review A, 2001
- Unconditionally Secure Quantum Bit Commitment is ImpossiblePhysical Review Letters, 1997
- Is Quantum Bit Commitment Really Possible?Physical Review Letters, 1997