Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

On the (Im)Possibility of Quantum String Commitment

Harry Buhrman, Matthias Christandl, Patrick M. Hayden, Hoi-kwong Lo, Stephanie Wehner

Published Jan 1, 2005• 7 citations
OpenAlex

Abstract

Unconditionally secure non-relativistic bit commitment is known to be impossible in both the classical and quantum worlds. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? We consider quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of ''information'' before the reveal phase. We show a negative and a positive result, depending on how we measure Bob's information. If we use the Holevo quantity, no good schemes exist: a+b is at least n. If, however, we use accessible information, there exists a scheme where a=4 log n+O(1) and b=4. This is classically impossible. Our protocol is not efficient, however, we also exhibit an efficient scheme when Bob's measurement circuit is restricted to polynomial size. Our scheme also implies a protocol for n simultaneous coin flips which achieves higher entropy of the resulting string than any previously known protocol.

Related papers

Possibility, impossibility, and cheat sensitivity of quantum-bit string commitment

Harry Buhrman, Matthias Christandl, Patrick M. Hayden +2 more

Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum worlds. But when committing to a string of $n$ bits at once, how far can we stretch the quantum limits? In this paper, we introduce a framework for quantum schemes where Alice commits a string of $n$ bits to Bob in such a way that she can only cheat on $a$ bits and Bob can learn at most $b$ bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: $a+b$ is at least $n$. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where $a=4\text{ }{\text{log}}_{2}\text{ }n+O(1)$ and $b=4$, which is impossible classically. We furthermore present a cheat-sensitive quantum bit string commitment protocol for which we give an explicit tradeoff between Bob's ability to gain information about the committed string, and the probability of him being detected cheating.

arXiv:quant-ph/0504078•Physical Review A•Aug 11, 2008•63 citations

Security of Quantum Bit String Commitment Depends on the Information Measure

Harry Buhrman, Matthias Christandl, Patrick M. Hayden +2 more

Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum world. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? In this Letter, we introduce a framework of quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a + b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a = 4log2(n) + O(1) and b = 4, which is impossible classically. Our findings significantly extend known no-go results for quantum bit commitment.

arXiv:quant-ph/0609237•Physical Review Letters•Dec 19, 2006•36 citations

Quantum Bit String Commitment

Adrian Kent

A bit string commitment protocol securely commits N classical bits so that the recipient can extract only M<N bits of information about the string. Classical reasoning suggests that bit string commitment implies bit commitment and hence, given the Mayers-Lo-Chau theorem, that nonrelativistic quantum bit string commitment is impossible. Not so: there exist nonrelativistic quantum bit string commitment protocols, with security parameters epsilon and M, that allow A to commit N=N(M,epsilon) bits to B so that A's probability of successfully cheating when revealing any bit and B's probability of extracting more than N'=N-M bits of information about the N bit string before revelation are both less than epsilon. With a restrictive definition of security against A, N can be taken to be O(exp(CN')) for a positive constant C. I briefly discuss possible applications.

arXiv:quant-ph/0111099•Physical Review Letters•Jun 13, 2003•53 citations

Optimal Bounds for Quantum Bit Commitment

André Chailloux, Iordanis Kerenidis

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. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/√2 (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important open question. In this paper, we provide the optimal bound for quantum bit commitment. First, we show a lower bound of approximately 0.739, improving Kitaev's lower bound. For this, we present some generic cheating strategies for Alice and Bob and conclude by proving a new relation between the trace distance and fidelity of two quantum states. Second, we 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 + ε in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(ε). We then use the optimal quantum weak coin flipping protocol described by Mochon. Last, in order 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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2011•49 citations

Why Quantum Bit Commitment And Ideal Quantum Coin Tossing Are Impossible

Hoi-kwong Lo, H. F. Chau

There had been well known claims of unconditionally secure quantum protocols for bit commitment. However, we, and independently Mayers, showed that all proposed quantum bit commitment schemes are, in principle, insecure because the sender, Alice, can almost always cheat successfully by using an Einstein-Podolsky-Rosen (EPR) type of attack and delaying her measurements. One might wonder if secure quantum bit commitment protocols exist at all. We answer this question by showing that the same type of attack by Alice will, in principle, break any bit commitment scheme. The cheating strategy generally requires a quantum computer. We emphasize the generality of this ``no-go theorem'': Unconditionally secure bit commitment schemes based on quantum mechanics---fully quantum, classical or quantum but with measurements---are all ruled out by this result. Since bit commitment is a useful primitive for building up more sophisticated protocols such as zero-knowledge proofs, our results cast very serious doubt on the security of quantum cryptography in the so-called ``post-cold-war'' applications. We also show that ideal quantum coin tossing is impossible because of the EPR attack. This no-go theorem for ideal quantum coin tossing may help to shed some lights on the possibility of non-ideal protocols.

•Jan 1, 1996•172 citations

Quantum Bit Escrow

Dorit Aharonov, Amnon Ta‐Shma, Umesh V. Vazirani +1 more

Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related new primitive - {\em quantum bit escrow}. In this primitive Alice commits to a bit $b$ to Bob. The commitment is {\em binding} in the sense that if Alice is asked to reveal the bit, Alice can not bias her commitment without having a good probability of being detected cheating. The commitment is {\em sealing} in the sense that if Bob learns information about the encoded bit, then if later on he is asked to prove he was playing honestly, he is detected cheating with a good probability. Rigorously proving the correctness of quantum cryptographic protocols has proved to be a difficult task. We develop techniques to prove quantitative statements about the binding and sealing properties of the quantum bit escrow protocol. A related primitive we construct is a quantum biased coin flipping protocol where no player can control the game, i.e., even an all-powerful cheating player must lose with some constant probability, which stands in sharp contrast to the classical world where such protocols are impossible.

•Apr 4, 2000•0 citations
Unconditionally secure non-relativistic bit commitment is known to be impossible in both the classical and quantum worlds. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? We consider quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of ''information'' before the reveal phase. We show a negative and a positive result, depending on how we measure Bob's information. If we use the Holevo quantity, no good schemes exist: a+b is at least n. If, however, we use accessible information, there exists a scheme where a=4 log n+O(1) and b=4. This is classically impossible. Our protocol is not efficient, however, we also exhibit an efficient scheme when Bob's measurement circuit is restricted to polynomial size. Our scheme also implies a protocol for n simultaneous coin flips which achieves higher entropy of the resulting string than any previously known protocol.
Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum worlds. But when committing to a string of nnn bits at once, how far can we stretch the quantum limits? In this paper, we introduce a framework for quantum schemes where Alice commits a string of nnn bits to Bob in such a way that she can only cheat on aaa bits and Bob can learn at most bbb bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a+ba+ba+b is at least nnn. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a=4 log2 n+O(1)a=4\text{ }{\text{log}}_{2}\text{ }n+O(1)a=4 log2​ n+O(1) and b=4b=4b=4, which is impossible classically. We furthermore present a cheat-sensitive quantum bit string commitment protocol for which we give an explicit tradeoff between Bob's ability to gain information about the committed string, and the probability of him being detected cheating.
Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum world. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? In this Letter, we introduce a framework of quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a + b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a = 4log2(n) + O(1) and b = 4, which is impossible classically. Our findings significantly extend known no-go results for quantum bit commitment.
A bit string commitment protocol securely commits N classical bits so that the recipient can extract only M<N bits of information about the string. Classical reasoning suggests that bit string commitment implies bit commitment and hence, given the Mayers-Lo-Chau theorem, that nonrelativistic quantum bit string commitment is impossible. Not so: there exist nonrelativistic quantum bit string commitment protocols, with security parameters epsilon and M, that allow A to commit N=N(M,epsilon) bits to B so that A's probability of successfully cheating when revealing any bit and B's probability of extracting more than N'=N-M bits of information about the N bit string before revelation are both less than epsilon. With a restrictive definition of security against A, N can be taken to be O(exp(CN')) for a positive constant C. I briefly discuss possible applications.
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. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/√2 (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important open question. In this paper, we provide the optimal bound for quantum bit commitment. First, we show a lower bound of approximately 0.739, improving Kitaev's lower bound. For this, we present some generic cheating strategies for Alice and Bob and conclude by proving a new relation between the trace distance and fidelity of two quantum states. Second, we 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 + ε in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(ε). We then use the optimal quantum weak coin flipping protocol described by Mochon. Last, in order 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.
There had been well known claims of unconditionally secure quantum protocols for bit commitment. However, we, and independently Mayers, showed that all proposed quantum bit commitment schemes are, in principle, insecure because the sender, Alice, can almost always cheat successfully by using an Einstein-Podolsky-Rosen (EPR) type of attack and delaying her measurements. One might wonder if secure quantum bit commitment protocols exist at all. We answer this question by showing that the same type of attack by Alice will, in principle, break any bit commitment scheme. The cheating strategy generally requires a quantum computer. We emphasize the generality of this ``no-go theorem'': Unconditionally secure bit commitment schemes based on quantum mechanics---fully quantum, classical or quantum but with measurements---are all ruled out by this result. Since bit commitment is a useful primitive for building up more sophisticated protocols such as zero-knowledge proofs, our results cast very serious doubt on the security of quantum cryptography in the so-called ``post-cold-war'' applications. We also show that ideal quantum coin tossing is impossible because of the EPR attack. This no-go theorem for ideal quantum coin tossing may help to shed some lights on the possibility of non-ideal protocols.
Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related new primitive - {\em quantum bit escrow}. In this primitive Alice commits to a bit bbb to Bob. The commitment is {\em binding} in the sense that if Alice is asked to reveal the bit, Alice can not bias her commitment without having a good probability of being detected cheating. The commitment is {\em sealing} in the sense that if Bob learns information about the encoded bit, then if later on he is asked to prove he was playing honestly, he is detected cheating with a good probability. Rigorously proving the correctness of quantum cryptographic protocols has proved to be a difficult task. We develop techniques to prove quantitative statements about the binding and sealing properties of the quantum bit escrow protocol. A related primitive we construct is a quantum biased coin flipping protocol where no player can control the game, i.e., even an all-powerful cheating player must lose with some constant probability, which stands in sharp contrast to the classical world where such protocols are impossible.