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

Axioms

Impossibility of Quantum Bit Commitment, a Categorical Perspective

Xin Sun, Feifei He, Quanlong Wang

Published Mar 9, 2020• 7 citations
Publisher

Abstract

Bit commitment is a cryptographic task in which Alice commits a bit to Bob such that she cannot change the value of the bit after her commitment and Bob cannot learn the value of the bit before Alice opens her commitment. According to the Mayers–Lo–Chau (MLC) no-go theorem, ideal bit commitment is impossible within quantum theory. In the information theoretic-reconstruction of quantum theory, the impossibility of quantum bit commitment is one of the three information-theoretic constraints that characterize quantum theory. In this paper, we first provide a very simple proof of the MLC no-go theorem and its quantitative generalization. Then, we formalize bit commitment in the theory of dagger monoidal categories. We show that in the setting of dagger monoidal categories, the impossibility of bit commitment is equivalent to the unitary equivalence of purification.

DOI
10.3390/axioms9010028

Related papers

Information-Theoretic Description of No-go Theorem of a Bit Commitment

Yoshihiro Nambu, Yoshie Chiba-Kohno

We give a comprehensive and constructive proof of the no-go theorem of a bit commitment given by Mayers, Lo, and Chau from the viewpoint of quantum information theory. It is shown that there is a trade-off relation between information acquired by Bob during the commitment phase and the ability to change a commit bit by Alice during the opening phase. It is clarified that a protocol that is unbiased to both Alice and Bob cannot be, at the same time, secure against both parties. Fundamental physical constraints that govern this no-go theorem are also discussed.

arXiv:quant-ph/0011068•Nov 16, 2000•1 citation

Simple proof of the impossibility of bit commitment in generalized probabilistic theories using cone programming

Jamie Sikora, John H. Selby

Bit commitment is a fundamental cryptographic task, in which Alice commits a bit to Bob such that she cannot later change the value of the bit, while, simultaneously, the bit is hidden from Bob. It is known that ideal bit commitment is impossible within quantum theory. In this work, we show that it is also impossible in generalized probabilistic theories (under a small set of assumptions) by presenting a quantitative trade-off between Alice's and Bob's cheating probabilities. Our proof relies crucially on a formulation of cheating strategies as cone programs, a natural generalization of semidefinite programs. In fact, using the generality of this technique, we prove that this result holds for the more general task of integer commitment.

arXiv:1711.02662•Physical Review A•Apr 3, 2018•18 citations

A brief review on the impossibility of quantum bit commitment

Gilles Brassard A, Claude Crépeau, Dominic Mayers +1 more

The desire to obtain an unconditionally secure bit commitment protocol in quantum cryptography was expressed for the first time thirteen years ago. Bit commitment is sufficient in quantum cryptography to realize a variety of applications with unconditional security. In 1993, a quantum bit commitment protocol was proposed together with a security proof. However, a basic flaw in the protocol was discovered by Mayers in 1995 and subsequently by Lo and Chau. Later the result was generalized by Mayers who showed that unconditionally secure bit commitment is impossible. A brief review on quantum bit commitment which focuses on the general impossibility theorem and on recent attempts to bypass this result is provided.

arXiv:quant-ph/9712023•Dec 10, 1997•25 citations

An Information-Theoretic Perspective on the Quantum Bit Commitment Impossibility Theorem

Marius Nagy, Naya Nagy

This paper proposes a different approach to pinpoint the causes for which an unconditionally secure quantum bit commitment protocol cannot be realized, beyond the technical details on which the proof of Mayers' no-go theorem is constructed. We have adopted the tools of quantum entropy analysis to investigate the conditions under which the security properties of quantum bit commitment can be circumvented. Our study has revealed that cheating the binding property requires the quantum system acting as the safe to harbor the same amount of uncertainty with respect to both observers (Alice and Bob) as well as the use of entanglement. Our analysis also suggests that the ability to cheat one of the two fundamental properties of bit commitment by any of the two participants depends on how much information is leaked from one side of the system to the other and how much remains hidden from the other participant.

Entropy•Mar 13, 2018•7 citations

Non-static Quantum Bit Commitment

Jeong Woon Choi, Dowon Hong, Ku-Young Chang +2 more

Quantum bit commitment has been known to be impossible by the independent proofs of Mayers, and Lo and Chau, under the assumption that the whole quantum states right before the unveiling phase are static to users. We here provide an unconditionally secure non-static quantum bit commitment protocol with a trusted third party, which is not directly involved in any communications between users and can be limited not to get any information of commitment without being detected by users. We also prove that our quantum bit commitment protocol is not secure without the help of the trusted third party. The proof is basically different from the Mayers-Lo-Chau's no-go theorem, because we do not assume the staticity of the finally shared quantum states between users.

arXiv:0901.1178•Jan 9, 2009•2 citations

Is quantum bit commitment really impossible

Jeong Woon Choi, Dowon Hong, Ku-Young Chang +2 more

Quantum bit commitment has been known to be impossible by the independent proofs of Mayers, and Lo and Chau, even though several quantum bit commitment protocols have been proposed. However, we here point out that their proof is available only for one-way quantum bit commitment protocols, and present a simple and efficient quantum bit commitment protocol with two-way quantum communications. The unconditional security of our protocol is guaranteed by the additional unknownness and randomness generated by both users.

•Jan 9, 2009•0 citations
Bit commitment is a cryptographic task in which Alice commits a bit to Bob such that she cannot change the value of the bit after her commitment and Bob cannot learn the value of the bit before Alice opens her commitment. According to the Mayers–Lo–Chau (MLC) no-go theorem, ideal bit commitment is impossible within quantum theory. In the information theoretic-reconstruction of quantum theory, the impossibility of quantum bit commitment is one of the three information-theoretic constraints that characterize quantum theory. In this paper, we first provide a very simple proof of the MLC no-go theorem and its quantitative generalization. Then, we formalize bit commitment in the theory of dagger monoidal categories. We show that in the setting of dagger monoidal categories, the impossibility of bit commitment is equivalent to the unitary equivalence of purification.
We give a comprehensive and constructive proof of the no-go theorem of a bit commitment given by Mayers, Lo, and Chau from the viewpoint of quantum information theory. It is shown that there is a trade-off relation between information acquired by Bob during the commitment phase and the ability to change a commit bit by Alice during the opening phase. It is clarified that a protocol that is unbiased to both Alice and Bob cannot be, at the same time, secure against both parties. Fundamental physical constraints that govern this no-go theorem are also discussed.
Bit commitment is a fundamental cryptographic task, in which Alice commits a bit to Bob such that she cannot later change the value of the bit, while, simultaneously, the bit is hidden from Bob. It is known that ideal bit commitment is impossible within quantum theory. In this work, we show that it is also impossible in generalized probabilistic theories (under a small set of assumptions) by presenting a quantitative trade-off between Alice's and Bob's cheating probabilities. Our proof relies crucially on a formulation of cheating strategies as cone programs, a natural generalization of semidefinite programs. In fact, using the generality of this technique, we prove that this result holds for the more general task of integer commitment.
The desire to obtain an unconditionally secure bit commitment protocol in quantum cryptography was expressed for the first time thirteen years ago. Bit commitment is sufficient in quantum cryptography to realize a variety of applications with unconditional security. In 1993, a quantum bit commitment protocol was proposed together with a security proof. However, a basic flaw in the protocol was discovered by Mayers in 1995 and subsequently by Lo and Chau. Later the result was generalized by Mayers who showed that unconditionally secure bit commitment is impossible. A brief review on quantum bit commitment which focuses on the general impossibility theorem and on recent attempts to bypass this result is provided.
This paper proposes a different approach to pinpoint the causes for which an unconditionally secure quantum bit commitment protocol cannot be realized, beyond the technical details on which the proof of Mayers' no-go theorem is constructed. We have adopted the tools of quantum entropy analysis to investigate the conditions under which the security properties of quantum bit commitment can be circumvented. Our study has revealed that cheating the binding property requires the quantum system acting as the safe to harbor the same amount of uncertainty with respect to both observers (Alice and Bob) as well as the use of entanglement. Our analysis also suggests that the ability to cheat one of the two fundamental properties of bit commitment by any of the two participants depends on how much information is leaked from one side of the system to the other and how much remains hidden from the other participant.
Quantum bit commitment has been known to be impossible by the independent proofs of Mayers, and Lo and Chau, under the assumption that the whole quantum states right before the unveiling phase are static to users. We here provide an unconditionally secure non-static quantum bit commitment protocol with a trusted third party, which is not directly involved in any communications between users and can be limited not to get any information of commitment without being detected by users. We also prove that our quantum bit commitment protocol is not secure without the help of the trusted third party. The proof is basically different from the Mayers-Lo-Chau's no-go theorem, because we do not assume the staticity of the finally shared quantum states between users.
Quantum bit commitment has been known to be impossible by the independent proofs of Mayers, and Lo and Chau, even though several quantum bit commitment protocols have been proposed. However, we here point out that their proof is available only for one-way quantum bit commitment protocols, and present a simple and efficient quantum bit commitment protocol with two-way quantum communications. The unconditional security of our protocol is guaranteed by the additional unknownness and randomness generated by both users.