Physics – Quantum Physics
Scientific paper
2009-04-09
Physics
Quantum Physics
12 pages
Scientific paper
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].
Chailloux André
Kerenidis Iordanis
No associations
LandOfFree
Optimal quantum strong coin flipping does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal quantum strong coin flipping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal quantum strong coin flipping will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-408648