Physics – Quantum Physics
Scientific paper
2011-02-08
Physics
Quantum Physics
v1 20pages
Scientific paper
Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes 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] (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important and open question. In this paper, we provide the optimal bound for quantum bit commitment. We first show a lower bound of approximately 0.739, improving Kitaev's lower bound. We then present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + eps in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(eps). We then use the optimal quantum weak coin flipping protocol described by Mochon[Moc07]. To stress the fact that our protocol uses quantum effects beyond the weak coin flip, we show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.
Chailloux André
Kerenidis Iordanis
No associations
LandOfFree
Optimal bounds for quantum bit commitment 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 bounds for quantum bit commitment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal bounds for quantum bit commitment will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-502899