I like to describe bit commitment using the analogy of a sealed envelope. I write a bit down, seal it in an envelope, and hand it to someone else. They cannot see what I wrote (this is the “hiding” property), but later, when I open the envelope, I cannot claim I wrote something different (this is the “binding” property). Quantum Bit Commitment (QBC) tries to build this envelope using quantum states instead of paper and wax. I find this topic especially interesting because it sits at the center of one of the more humbling results in quantum cryptography — the discovery that unconditionally secure bit commitment is actually impossible using quantum mechanics alone, a result now known as the Mayers–Lo–Chau (MLC) no-go theorem.
History and Background
I trace the earliest attempts at quantum bit commitment to Bennett and Brassard’s foundational 1984 work on quantum cryptography, which also gave rise to BB84 quantum key distribution. Throughout the late 1980s and early 1990s, several protocols were proposed, most notably by Brassard, Crépeau, Jozsa, and Langlois in 1993, which appeared to offer unconditional security using quantum states. For a while, the cryptography community was excited that quantum mechanics might deliver a primitive that classical cryptography could never achieve unconditionally. That excitement was tempered in 1996–1997 when Dominic Mayers, and independently Hoi-Kwong Lo and H. F. Chau, proved that no quantum bit commitment protocol can be simultaneously unconditionally hiding and unconditionally binding. I see this as one of those rare moments where a “no-go” theorem reshaped an entire subfield, pushing later research toward relativistic protocols, bounded/noisy-storage models, and computationally secure variants instead.
Problem Statement
I want a protocol where a committer, Alice, picks a bit $b \in {0,1}$ and commits to it by sending some quantum state to a receiver, Bob. Two properties must hold: hiding — Bob learns nothing about $b$ from the commitment phase alone — and binding — once committed, Alice cannot later reveal a different bit $b’$ and have Bob accept it as valid. The challenge is that these two properties tend to work against each other: a state that is easy to bind is also somewhat exposing, and a state that hides well is often ambiguous enough to unbind. This tension is exactly what the MLC theorem formalizes.
Core Concepts
- Commit phase — Alice sends a quantum state (or classical data derived from quantum operations) to Bob that encodes $b$ without revealing it.
- Reveal phase — Alice later sends additional information allowing Bob to verify $b$.
- Hiding property — the reduced density matrices Bob holds for $b=0$ and $b=1$ commitments should be statistically indistinguishable, ideally $\rho_0 = \rho_1$.
- Binding property — Alice should not be able to find local unitary operations that change her committed state from representing $0$ into representing $1$ after the fact.
- EPR pairs / entanglement cheating — the central idea in the MLC attack, where a dishonest Alice uses entangled states to delay her actual choice of bit until the reveal phase.
How It Works
I describe a simplified BCJL-style (Brassard–Crépeau–Jozsa–Langlois) protocol to show the mechanics, even though I know it was later shown to be breakable:
- Alice wants to commit to bit $b$.
- Alice prepares a sequence of qubits: if $b=0$ she encodes random bits in the rectilinear basis; if $b=1$ she encodes random bits in the diagonal basis (similar to BB84 state preparation).
- Alice sends these qubits to Bob.
- Bob measures each qubit in a randomly chosen basis (he cannot know Alice’s true basis), recording outcomes and, importantly, is unable to reliably tell which basis Alice used from his measurements alone.
- To reveal, Alice announces $b$ and the original basis and bit values.
- Bob checks that his own recorded measurement outcomes are consistent with Alice’s claimed basis and values for the subset of qubits where his random basis happened to match hers.
- If everything checks out within an acceptable error tolerance, Bob accepts the commitment as valid for bit $b$.
Working Principle
I understand the internal logic as an attempt to exploit basis uncertainty: Bob cannot determine Alice’s basis choice from a single quantum measurement with certainty, which is meant to guarantee hiding. Binding was meant to follow from the fact that once qubits are sent and (partially) measured, Alice cannot go back and change her earlier choice without being caught, because she no longer holds the qubits. However, the MLC theorem shows that if Alice does not use simple product states but instead prepares entangled states between her own private qubits and the ones she sends, she can postpone her actual commitment until the reveal phase, applying a “measurement postponed” trick that lets her locally steer her reduced state to appear consistent with either $b=0$ or $b=1$ after seeing the challenge, all without Bob detecting anything wrong, as long as the entangled state satisfies the hiding property she needed in the first place.
Mathematical Foundation
I formalize hiding as requiring the reduced density matrices on Bob’s side, from committing to $0$ or $1$, to be essentially identical:
$$ \rho_0 \approx \rho_1 $$
Ideal (unconditional) hiding requires:
$$ \Vert \rho_0 – \rho_1 \Vert_{\text{tr}} = 0 $$
The MLC theorem shows that if this holds exactly, then Alice’s overall committed state, purified using an ancillary system $A$, can be written for both bits using local unitaries $U_0, U_1$ acting only on Alice’s side:
$$ \vert\Psi_1\rangle = (U_1 \otimes I_B)\vert\Psi_0\rangle $$
Because $U_1$ acts only on Alice’s system and $\rho_0 = \rho_1$ implies such a unitary exists by the properties of purification (via the Hughston–Jozsa–Wootters theorem), Alice can wait until the reveal phase, decide which bit she wants to reveal, and apply $U_1$ to switch her committed state from representing $0$ to representing $1$ without Bob detecting any change on his side. This is the mathematical heart of why unconditional QBC fails:
$$ \text{Unconditional Hiding} + \text{Unconditional Binding} = \text{Impossible} $$
Diagrams
sequenceDiagram
participant A as Alice (Committer)
participant B as Bob (Receiver)
A->>B: Sends encoded qubits for bit b (commit phase)
Note over B: Bob measures in random bases, cannot determine b
A->>B: Later reveals b, basis, and bit values (reveal phase)
B->>B: Checks consistency with recorded measurements
B-->>A: Accept or Reject commitment
flowchart TD
C[Alice prepares state for bit b] --> S[Send qubits to Bob]
S --> M[Bob measures randomly]
M --> H{Commit phase complete}
H --> R[Reveal phase: Alice announces b]
R --> V[Bob verifies consistency]
V -->|Consistent| ACC[Commitment accepted]
V -->|Inconsistent| REJ[Commitment rejected]Pseudocode
Protocol QuantumBitCommitment(b):
Commit Phase (Alice):
for i in 1..n:
r[i] = random(0,1)
basis[i] = (b == 0) ? RECT : DIAG
qubit[i] = encode(r[i], basis[i])
send qubit[1..n] to Bob
Commit Phase (Bob):
for i in 1..n:
bBasis[i] = random(RECT, DIAG)
measurement[i] = measure(qubit[i], bBasis[i])
store measurement[1..n], bBasis[1..n]
Reveal Phase (Alice):
send (b, basis[1..n], r[1..n]) to Bob
Reveal Phase (Bob):
matches = 0
errors = 0
for i in 1..n:
if bBasis[i] == basis[i]:
matches += 1
if measurement[i] != r[i]:
errors += 1
if errors / matches < threshold:
accept b
else:
reject
Step-by-Step Example
Suppose I let Alice commit to $b=0$ using 6 qubits in the rectilinear basis with random values $101100$. Bob independently measures each qubit in a randomly chosen basis: RECT, DIAG, RECT, RECT, DIAG, RECT. His bases match Alice’s true basis (RECT) at positions 1, 3, 4, and 6. During the reveal phase, Alice announces $b=0$, her basis (RECT for all six), and her bit string $101100$. Bob checks positions 1, 3, 4, 6 against his recorded measurements. If his outcomes at those positions read $1, 1, 1, 0$ and Alice’s values there were also $1,1,1,0$, the commitment is accepted. If Alice had instead tried to cheat and claim $b=1$ during reveal, she would need her original qubits to be consistent with the diagonal basis too, which for simple product states is detectable — but as the MLC theorem shows, with entangled preparation she could in principle pass this check for either bit.
Time Complexity
I count the number of qubits transmitted and processed as $n$. Both the commit and reveal phases involve $O(n)$ quantum operations (encoding, transmission, measurement) and $O(n)$ classical verification steps. So:
$$ T(n) = O(n) $$
Space Complexity
Alice must store $n$ random bits and $n$ basis choices until the reveal phase, and Bob must store $n$ measurement outcomes and $n$ basis choices, giving:
$$ S(n) = O(n) $$
Correctness Analysis
I consider the protocol correct, in the honest case, whenever Alice’s later revealed values consistently match Bob’s recorded measurements at the positions where their bases coincided. Statistically, if Alice is honest, the error rate at matching positions should be near zero (barring physical channel noise), so Bob accepts with overwhelming probability. However, “correctness” in the security sense — proving that binding actually holds against an adversarial Alice — is precisely where the MLC theorem intervenes: no matter how the protocol is designed, if hiding is information-theoretically perfect, binding cannot also be information-theoretically perfect, because a cheating Alice using entanglement can always find a way to satisfy the verification check for either bit value at reveal time.
Advantages
- Conceptually elegant, tying cryptographic guarantees directly to the laws of quantum physics.
- Basis-uncertainty gives good practical hiding against adversaries without large-scale entangled storage.
- Forms the conceptual seed for relativistic and noisy-storage bit commitment protocols that do achieve practical security.
- Encouraged deep foundational research connecting cryptography and quantum information theory (e.g., the MLC theorem itself).
Disadvantages
- Fundamentally impossible to make unconditionally secure in both hiding and binding simultaneously, as proven by Mayers, Lo, and Chau.
- Susceptible to entanglement-based cheating strategies if the committer has quantum memory and control.
- Requires practical safeguards like computational assumptions, bounded quantum storage assumptions, or relativistic signaling constraints to be genuinely secure.
- Real hardware noise complicates the honest verification threshold, opening room for subtle attacks disguised as noise.
Applications
- Building block for larger protocols such as quantum coin flipping and quantum zero-knowledge proofs.
- Secure multi-party computation frameworks that need a commitment primitive.
- Relativistic bit commitment schemes used in some experimental secure auction and timestamp systems.
- Research testbed for exploring the limits of information-theoretic security in quantum protocols.
Implementation in C
I again implement a classical simulation, focusing on the honest-party logic and a simple consistency check, since true QBC needs quantum hardware and, per the MLC theorem, cannot be unconditionally secure regardless of implementation.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20 /* number of qubits simulated */
#define RECT 0
#define DIAG 1
int random_bit() { return rand() % 2; }
int main() {
srand((unsigned)time(NULL));
int b = 1; /* the bit Alice wants to commit to */
int aliceBasis = (b == 0) ? RECT : DIAG; /* fixed basis tied to the committed bit */
int aliceBits[N];
int bobBasis[N], bobMeasure[N];
/* Commit phase */
for (int i = 0; i < N; i++) {
aliceBits[i] = random_bit();
}
for (int i = 0; i < N; i++) {
bobBasis[i] = random_bit();
if (bobBasis[i] == aliceBasis) {
bobMeasure[i] = aliceBits[i]; /* correct measurement */
} else {
bobMeasure[i] = random_bit(); /* random, wrong basis */
}
}
/* Reveal phase: Alice announces b, basis, and her bit string */
int revealedB = b;
int revealedBasis = aliceBasis;
int matches = 0, errors = 0;
for (int i = 0; i < N; i++) {
if (bobBasis[i] == revealedBasis) {
matches++;
if (bobMeasure[i] != aliceBits[i]) {
errors++;
}
}
}
double errorRate = matches > 0 ? (double)errors / matches : 0.0;
printf("Revealed bit: %d\n", revealedB);
printf("Matches: %d, Errors: %d, Error rate: %.2f\n", matches, errors, errorRate);
if (errorRate < 0.1) {
printf("Bob ACCEPTS the commitment.\n");
} else {
printf("Bob REJECTS the commitment.\n");
}
return 0;
}
Sample Input and Output
A typical honest run might produce:
Revealed bit: 1
Matches: 11, Errors: 0, Error rate: 0.00
Bob ACCEPTS the commitment.
Optimization Techniques
- Increasing $n$ reduces the chance a cheating party slips through statistical checks unnoticed, at the cost of more quantum resources.
- Using error-correcting or error-tolerant verification thresholds accounts for real channel noise without opening large security gaps.
- Combining QBC with relativistic constraints (multiple separated agents, timed responses) sidesteps the MLC impossibility by adding a non-quantum assumption.
- Bounded or noisy-storage assumptions let designers regain security guarantees by limiting how much quantum memory a cheating party can use.
Common Mistakes
- Assuming any quantum protocol automatically achieves unconditional security — the MLC theorem specifically forbids this for bit commitment.
- Overlooking that a cheating committer can use entangled ancilla qubits to delay her real commitment, which single-round protocols cannot detect.
- Setting the error-tolerance threshold too loose, letting adversarial noise-based cheating pass as “channel imperfection.”
- Confusing bit commitment with key distribution — QBC and QKD solve different problems even though they share technical machinery.
Further Reading
- Mayers, D., “Unconditionally Secure Quantum Bit Commitment is Impossible,” Physical Review Letters, 1997. https://arxiv.org/abs/quant-ph/9605044
- Lo, H.-K., Chau, H. F., “Is Quantum Bit Commitment Really Possible?,” Physical Review Letters, 1997. https://arxiv.org/abs/quant-ph/9603004
- Brassard, G., Crépeau, C., Jozsa, R., Langlois, D., “A Quantum Bit Commitment Scheme Provably Unbreakable by Both Parties,” FOCS 1993. https://ieeexplore.ieee.org/document/366852
- Kent, A., “Unconditionally Secure Bit Commitment,” Physical Review Letters, 1999 (relativistic protocol). https://arxiv.org/abs/quant-ph/9810068
- Damgård, I., Fehr, S., Salvail, L., “Secure Identification and QKD in the Bounded-Quantum-Storage Model,” CRYPTO 2005. https://arxiv.org/abs/quant-ph/0508220
