Optimal quantum strong coin flipping

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].

12 pages

References in corpus (6)

• Unconditionally secure quantum bit commitment is impossible
• Is Quantum Bit Commitment Really Possible?
• Degrees of concealment and bindingness in quantum bit commitment protocols
• Reexamination of Quantum Bit Commitment: the Possible and the Impossible
• Cheat Sensitive Quantum Bit Commitment
• Possibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment

Cited by in corpus (3)

• Quantum Strategies and Local Operations
• A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias
• Optimal bounds for semi-honest quantum oblivious transfer