Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the $30$ th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than $1/\sqrt{2}$ [A. Kitaev, Presentation at the $6$ th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present 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+\varepsilon$ in order to achieve a strong coin flipping protocol with cheating probability $1/\sqrt{2}+O(\varepsilon)$ . The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately $\gamma \approx 0.739$ , improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to $\gamma$ . More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2 + \varepsilon$ in order to achieve a quantum bit commitment protocol with cheating probability $\gamma + O(\varepsilon)$ . To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the $30$th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than $1/\sqrt{2}$ [A. Kitaev, Presentation at the $6$th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present 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+\varepsilon$ in order to achieve a strong coin flipping protocol with cheating probability $1/\sqrt{2}+O(\varepsilon)$. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately $\gamma \approx 0.739$, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to $\gamma$. More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2 + \varepsilon$ in order to achieve a quantum bit commitment protocol with cheating probability $\gamma + O(\varepsilon)$. To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.

SIAM Journal on ComputingJan 1, 20172 citations

30

th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than

1/\sqrt{2}

[A. Kitaev, Presentation at the

6

th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present 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+\varepsilon

in order to achieve a strong coin flipping protocol with cheating probability

1/\sqrt{2}+O(\varepsilon)

. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately

\gamma \approx 0.739

, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to

\gamma

. More precisely, we show how to use any weak coin flipping protocol with cheating probability

1/2 + \varepsilon

in order to achieve a quantum bit commitment protocol with cheating probability

\gamma + O(\varepsilon)

. To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.