This paper has appeared in the proceedings of the 34^{th} Symposium on Foundations of Computer Science, IEEE, 1993.

A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties

Gilles Brassard^{∗}

Université de Montréal^{†}

Claude Crépeau^{‡}

École Normale Supérieure ^{§}

Richard Jozsa

Université de Montréal^{†}

Denis Langlois^{‡}

Université Paris–Sud^{¶}

Abstract

Assume that a party, Alice, has a bit x in mind, to which she would like to be committed toward another party, Bob. That is, Alice wishes, through a procedure commit(x), to provide Bob with a piece of evidence that she has a bit x in mind and that she cannot change it. Meanwhile, Bob should not be able to tell from that evidence what x is. At a later time, Alice can reveal, through a procedure unveil(x), the value of x and prove to Bob that the piece of evidence sent earlier really corresponded to that bit. Classical bit commitment schemes (by which Alice’s piece of evidence is classical information such as a bit string) cannot be secure against unlimited computing power and none have been proven secure against algorithmic sophistication. Previous quantum bit commitment schemes (by which Alice’s piece of evidence is quantum information such as a stream of polarized photons) were known to be invulnerable to unlimited computing power and algorithmic sophistication, but not to arbitrary measurements allowed by quantum physics: perhaps more sophisticated use of quantum physics could have defeated them.

We present a new quantum bit commitment scheme. The major contribution of this work is to provide the first complete proof that, according to the laws of quantum physics, neither participant in the protocol can cheat, except with arbitrarily small probability. In addition, the new protocol can be implemented with current technology.

1 Introduction

Assume that a party, Alice, has a bit x in mind, to which she would like to be committed toward another party, Bob. That is, Alice wishes, through a procedure commit(x), to provide Bob with a piece of evidence that she has a bit x in mind and that she cannot change it. Meanwhile, Bob should not be able to tell from that evidence what x is. At a later time, Alice can reveal, through a procedure unveil(x), the value of x and prove to Bob that the piece of evidence sent earlier really corresponded to that bit.

Bit commitment schemes have several applications in the field of cryptographic protocols. In particular one can implement zero-knowledge proofs of a variety of statements using bit commitment schemes [GMR89, GMW91, BCC88]. The first implementations of bit commitment schemes were given in a computational complexity scenario [Blu82]. Unfortunately, proofs of their (computational) security have always required an unproved assumption since otherwise they would imply very strong results such as P ≠ N P.

Over the last two decades a number of researchers have investigated the connection between cryptography and quantum physics, starting with the work of Wiesner in the late 1960’s (though published much later [Wie83]), and continuing with the work of Bennett and Brassard [BBBW83, BB84, BB85, BBR88, BB89, BBBSS92] and later of Crépeau [CK88, Cré90, BC91, BBCS92, Cré93]. The security of these protocols would not be compromised if a cheater had unlimited computing power, but in essentially all cases it has not yet been ruled out that still more sophisticated use of quantum physics might defeat them.

The first quantum bit commitment scheme ever proposed is due to Bennett and Brassard [BB84] (actually, the protocol they describe is only claimed to implement coin tossing, but implicitly it implements bit commitment). Their scheme had two major flaws: it was impossible to use in practice because faint pulses of light would compromise the security of the scheme (it required individual photons to be transmitted), and the scheme could actually be cheated by Alice using the Einstein–Podolsky–Rosen effect [EPR35]. A later protocol of [BC91] did not suffer from these problems but was sensitive to transmission errors in the quantum channel and no formal proof of its security was, at the time, available.

∗Supported in part by Nserc’s E. W. R. Steacie Memorial Fellowship and Québec’s Fcar.

† Département d’Informatique et R.O., Université de Montréal, C.P. 6128, succursale “A”, Montréal (Québec), Canada H3C 3J7.

e-mail: {brassard}{jozsa}@iro.umontreal.ca.

‡ Part of this work was performed while visiting †.

§ Laboratoire d’Informatique de l’École Normale Supérieure, (CNRS ura1327), 45 rue d’Ulm, 75230 Paris CEDEX 05, France.

e-mail:crepeau@dmi.ens.fr.

¶ Labo. de Recherche en Informatique, Université Paris–Sud, Bâtiment 490, 91405 Orsay, France. e-mail: langlois@lri.lri.fr.

The protocol we describe in this current paper is an improvement on the protocol of [BC91], which can deal with transmission errors and is more efficient. We also provide the first mathematical proof that the protocol is perfectly secure, in the sense that neither party can cheat without arbitrarily high probability of detection, according to the laws of quantum physics.

As a side benefit, the current result and proof provide the missing piece to the protocol of [BBCS92] for quantum oblivious transfer. Thus, a proof of the security of that scheme is now within reach. In turn, an unconditionally secure quantum oblivious transfer protocol would allow for provably unconditionally secure discreet two-party computation and decision making.

2 The New Quantum Bit Commitment Scheme

Let \begin{matrix}c \\ ◯ \end{matrix}^{|} ^{p} denote the random variable that takes the binary value 0 with probability p and 1 with probability 1 − p. We often drop the index when p = \frac{1}{2} and write \begin{matrix}c \\ ◯ \end{matrix}^{|} instead of \begin{matrix}c \\ ◯ \end{matrix}^{|} ^{\frac{1}{2}} . Also, denote by [ ]_{i} the selection function such that [a_{0}, a_{1}, ..., a_{k}]_{i} = a_{i}. Let x ⊙ y denote the Boolean scalar product, i.e. if x_{i}, y_{i} are the

i^{th} bits of x and y we have x ⊙ y = ⨁_{i=1}^{n} x_{i} ∧ y_{i}.

Let ↔ ↕ = (|↔⟩, |↕⟩) and ↗ ↙ ↘ ↖ = (| ↗ ↙ ⟩, | ↘ ↖ ⟩) denote respectively the bases of rectilinear and diagonal polarization in the quantum state space of a photon. Please consult the Appendix for an explanation of this notation and a summary of relevant basic quantum physics.

2.1 The formal protocols

Let ε be an upper bound on the error rate of the quantum channel, i.e. the probability that a |↔⟩ polarized photon is detected as |↕⟩. In order for Alice to commit to a bit x, she uses protocol commit(x) with Bob. (an informal description of the protocol follows in Subsection 2.2)

Protocol 2.1 ( commit(x) )

1: Bob chooses a Boolean matrix G as the generating matrix of a binary linear (n, k, d)-code C such that the ratio d/n > 10ε and the ratio k/n = 0.52 and announces it to Alice

2: Alice chooses a non-zero random n-bit string r ← (\begin{matrix}c \\ ◯ \end{matrix}^{|} _{1}\begin{matrix}c \\ ◯ \end{matrix}^{|} _{2}...\begin{matrix}c \\ ◯ \end{matrix}^{|} _{n}) and announces it to Bob

3: Alice chooses a random n-bit codeword

c ← (\begin{matrix}c \\ ◯ \end{matrix}^{|} _{1}...\begin{matrix}c \\ ◯ \end{matrix}^{|} _{k})G from C such that c ⊙ r = x

4: DO_{i=1}^{n}

• Alice chooses a random bit b_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and defines her transmission basis (φ_{i}, φ_{i}^{⊥}) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{b_{i}}

• Alice sends to Bob a photon π_{i} with polarization [φ_{i}, φ_{i}^{⊥}]_{c_{i}}

5: DO_{i=1}^{n}

• Bob chooses a random bit b′_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and measures photon π_{i} in basis (θ_{i}, θ_{i}^{⊥}) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{b′_{i}}

• Bob sets c′_{i} ← \{ \begin{matrix}0 & if π_{i} is seen as θ_{i} \\ 1 & if π_{i} is seen as θ_{i}^{⊥} \end{matrix}

Let c′, b and b′ be the vectors c′ = (c′_{1}c′_{2} … c′_{n}) , b = (b_{1}b_{2} … b_{n}) , b′ = (b′_{1}b′_{2} … b′_{n}) . Alice keeps x, c and b secret until (and if) unveiling takes place, whereas Bob keeps c′ and b′ secret forever. Theorem 3.4 shows that an honest Alice does not reveal much about her secret bit x by sending codeword c on the quantum channel.

If Alice subsequently decides to unveil her commitment, she initiates the following protocol with Bob.

Protocol 2.2 ( unveil((c, b, x), (c′, b′)) )

1: Alice reveals c, b and x to Bob

2: Bob sets δ ← ∑_{i | b′_{i}=b_{i}} \frac{c_{i} ⊕ c′_{i}}{n/2}

3: if (δ < 1.4ε), (x = c⊙r) and (c is a codeword) then Bob outputs “accept” else Bob outputs “reject”

2.2 Intuition behind the protocols

Intuitively, Alice chooses a random vector r and a random codeword c such that c⊙r = x. She tells r to Bob in the clear, but she sends him c through the quantum channel. For this, she encodes each bit of c by a photon polarized in a randomly chosen basis (rectilinear or diagonal): bit c_{i} = 0 is thus encoded as |↔⟩ if b_{i} = 0 or as | ↗ ↙ ⟩ if b_{i} = 1, whereas bit 1 may be encoded either as |↕⟩ or | ↘ ↖ ⟩. Since Bob does not know in which bases the photons are polarized, he measures them in randomly chosen bases. When he chooses the correct basis (b′_{i} = b_{i}), which happens with probability \frac{1}{2}, he obtains the correct bit (c′_{i} = c_{i}) except with error probability at most ε. On the other hand, when he chooses the wrong basis (b′_{i} ≠ b_{i}), his bit is uncorrelated with Alice’s bit (c′_{i} = c_{i} with probability \frac{1}{2}). Therefore Bob’s reading of Alice’s word c is correct on roughly 75% of the bits. (We shall see later that a cheating Bob is able to get as much as about 85% of the bits correctly, and that this is the best possible.)

The binary linear code C is chosen so that there are exponentially many codewords around Bob’s received c′ that are at the same Hamming distance as Alice’s transmitted c. For this, the minimum distance between codewords should not be too large. Because r is chosen randomly, knowledge of r and c′ gives Bob an exponentially small amount of expected Shannon information on x = c ⊙ r. (See Theorem 3.4.) On the other hand, the minimum distance between codewords must be sufficiently large to prevent Alice from finding two different codewords c^{0} and c^{1} (together with possibly fake sending bases b^{0} and b^{1}) so that Bob would be willing to blame on transmission errors the differences between either codeword and his measured c′. (See Theorem 3.7.) Thus we see that a balancing act is needed in the choice of code C to prevent both Alice and Bob from cheating, thence the mysterious parameters 10ε and 0.52 in protocol commit.

3 Analysis

There are very few ways in which the above protocols might fail. This section is divided into four parts, each analysing one way in which failure could occur.

• Bob gets too much information about x

• Bob chooses an unsuitable G

• Alice changes x without detection

• Bob rejects a valid c

3.1 Analysis of Bob’s information about x

Given the public parameters G and r, all the information available to Bob about x is provided to him through the quantum transmission of c in step 4. We identify the measurement that Bob may perform in step 5 which will maximize his information about c (and x). Let us first define two magic constants that will be used later in the analysis:

κ = cos(π/8) ≈ 0.9238795

and

σ = sin(π/8) ≈ 0.3826834.

Let |B⟩ denote the state midway between |↔⟩ and | ↗ ↙ ⟩, and let |B^{⊥}⟩ denote the state midway between |↕⟩ and | ↘ ↖ ⟩, i.e.

|B⟩ = κ|↔⟩ + σ|↕⟩ and |B^{⊥}⟩ = −σ|↔⟩ + κ|↕⟩.

3.1.1 Optimal measurement

Theorem 3.1 The quantum measurement that will maximize (cheating) Bob’s information about x is the measurement of each photon π_{i} separately in the basis (θ_{i}, θ_{i}^{⊥}) = (B, B^{⊥}).

Proof. The density matrix ρ_{0} (please consult the Appendix) describing the quantum mixture of states sent to Bob to represent a 0 in step 4 of the original protocol commit is given by

ρ_{0} = \frac{1}{2}|↔⟩⟨↔| + \frac{1}{2}| ↗ ↙ ⟩⟨ ↗ ↙ |

= \frac{1}{2} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) + \frac{1}{2} ( \begin{matrix}\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{matrix} ) = ( \begin{matrix}\frac{3}{4} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} \end{matrix} )

and for a bit 1, the density matrix ρ_{1} is given by

ρ_{1} = \frac{1}{2}|↕⟩⟨↕| + \frac{1}{2}| ↘ ↖ ⟩⟨ ↘ ↖ | =

\frac{1}{2} ( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ) + \frac{1}{2} ( \begin{matrix}\frac{1}{2} & −\frac{1}{2} \\ −\frac{1}{2} & \frac{1}{2} \end{matrix} ) = ( \begin{matrix}\frac{1}{4} & −\frac{1}{4} \\ −\frac{1}{4} & \frac{3}{4} \end{matrix} ) .

Consider a protocol commit′ that is identical to commit except that step 4 becomes

4′: DO_{i=1}^{n}

• Alice chooses a random bit b_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} ^{κ^{2}} • Alice sends to Bob a photon π_{i} with

polarization [|B⟩, |B^{⊥}⟩]_{c_{i}⊕b_{i}}

For the modified protocol commit′ the density matrices ρ′_{0}, ρ′_{1} describing the quantum mixtures sent to Bob to represent a 0 and a 1 in step 4′ are the same as in commit:

ρ′_{0} = κ^{2}|B⟩⟨B| + (1 − κ^{2})|B^{⊥}⟩⟨B^{⊥}| =

κ^{2} ( \begin{matrix}κ^{2} & σκ \\ σκ & σ^{2} \end{matrix} ) + σ^{2} ( \begin{matrix}σ^{2} & −σκ \\ −σκ & κ^{2} \end{matrix} ) = ( \begin{matrix}\frac{3}{4} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} \end{matrix} )

ρ′_{1} = (1 − κ^{2})|B⟩⟨B| + κ^{2}|B^{⊥}⟩⟨B^{⊥}| =

σ^{2} ( \begin{matrix}κ^{2} & σκ \\ σκ & σ^{2} \end{matrix} )+κ^{2} ( \begin{matrix}σ^{2} & −σκ \\ −σκ & κ^{2} \end{matrix} ) = ( \begin{matrix}\frac{1}{4} & −\frac{1}{4} \\ −\frac{1}{4} & \frac{3}{4} \end{matrix} ) .

Furthermore, if we call ρ_{c} the density matrix associated with the mixture of states used in commit to send c and similarly, ρ′_{c} for commit′ we get

ρ_{c} = ρ_{c_{1}} ⊗ ρ_{c_{2}} ⊗ ⋯ ⊗ ρ_{c_{n}} = ρ′_{c_{1}} ⊗ ρ′_{c_{2}} ⊗ ⋯ ⊗ ρ′_{c_{n}} = ρ′_{c}

where the operation ⊗ is the tensor product. Finally, the density matrices ϱ_{0}, ϱ_{1}, ϱ′_{0}, ϱ′_{1} describing the quantum mixtures of states sent to Bob to commit to a 0 (or a 1) with the protocols commit and commit′ are given by

ϱ_{0} = ∑_{\{c∈C|c⊙r=0\}} \frac{ρ_{c}}{2^{k−1}} = ∑_{\{c∈C|c⊙r=0\}} \frac{ρ′_{c}}{2^{k−1}} = ϱ′_{0}

and

ϱ_{1} = ∑_{\{c∈C|c⊙r=1\}} \frac{ρ_{c}}{2^{k−1}} = ∑_{\{c∈|c⊙r=1\}} \frac{ρ′_{c}}{2^{k−1}} = ϱ′_{1}.

Thus Bob is able to get exactly the same information about c and x in protocol commit as in commit′. (This follows from a theorem of quantum physics stipulating that mixtures with identical density matrices cannot be distinguished by any quantum measurement whatsoever.) We also observe that in the protocol commit′ the measurement that will optimize Bob’s information about c (and thus x) consists of measuring every single photon π_{i} in basis (B, B^{⊥}) since in that basis he gets all the information available! (All the photons sent are either polarized as |B⟩ or |B^{⊥}⟩.) We thus conclude that the optimal measurement for Bob in protocol commit is the same. In particular, any more general joint measurement on all the photons together will be of no advantage. (This was the main open question of [BC91].) _{3.1} 3.1.2 Further analysis

Despite the fact that the honest Bob is not expected to perform the above optimal measurement, we show that even if he did he would get very little information about x.

We start with a lemma stating that the vector c′ received by Bob must be fairly far from the vector c sent by Alice. Let γ = H^{−1}(1/2) ≈ 0.1100279.

Lemma 3.2 Even if (cheating) Bob performs the optimal measurement, there exists a positive constant α < 1 such that he ends up with a vector c′ at distance less than γn from c with probability at most α^{n}.

Proof. Assume that the quantum channel is noiseless (in reality things are even worse for a cheating Bob). When Bob performs the optimal measurement, his distribution on c′ is ruled by the fact that for all i, 1 ≤ i ≤ n, we have [Prob(c_{i} = c′_{i}) = κ^{2}]. Therefore the number of differences between c and c′ is expected to be σ^{2}n ≈ .1464466n. We can use “Bernshtein’s law of large numbers” [Kra86] to estimate the probability that the number of errors will be less than γn.

Theorem 3.3 (Bernshtein) Let x_{1}, x_{2}, ..., x_{n} be independent Bernoulli variables. If Prob(x_{i} = 1) = p for 1 ≤ i ≤ n then for all 0 < δ ≤ p(1 − p) we have

Prob(| ∑_{i=1}^{n} \frac{x_{i}}{n} − p| ≥ δ) ≤ 2e^{−nδ^{2}}.

Let x_{i} be the indicator variable of c_{i}, c′_{i}, i.e. x_{i} = c_{i}⊕c′_{i}. The number of differences between c and c′ is given by ∑_{i=1}^{n} x_{i} and Prob(x_{i} = 1) = σ^{2}. Therefore the probability that c′ is at distance less than γn of c is given by

Prob(∑_{i=1}^{n} \frac{x_{i}}{n} ≤ γ) ≤ Prob(| ∑_{i=1}^{n} \frac{x_{i}}{n} − σ^{2}| ≥ σ^{2} − γ)

≤ 2e^{−n(σ^{2}−γ)^{2}} ≈ 2e^{−0.00132632n}.

3.2

We conclude that most of the time c′ is at distance at least γn from c.

Theorem 3.4 Even if Bob knew the exact Hamming distance d ← d_{H}(c, c′), he would have very little information about x, when d > γn.

Proof. The number of words at Hamming distance d from c′ is \binom{n}{d}. Using the fact that d > γn and the standard approximation [MS77]

\frac{2^{H(λ)n}}{\sqrt{8nλ(1 − λ)}} ≤ \binom{n}{λn} ≤ \frac{2^{H(λ)n}}{\sqrt{2πnλ(1 − λ)}} ,

we get the lower bound

\binom{n}{d} > \binom{n}{γn} ≥ \frac{2^{H(γ)n}}{\sqrt{n}} = \frac{2^{n/2}}{\sqrt{n}}

because 8λ(1 − λ) ≤ 1 precisely when λ ≥ κ^{2} or λ ≤ 1 − κ^{2}, and also because H(γ) = 1/2. If we divide by 2^{n−k} (the number of symdroms of the code C) we get:

E(number of codewords at distance d) > \frac{2^{k−n/2}}{\sqrt{n}}

which is exponentially large in n as long as \frac{k}{n} > \frac{1}{2}. Indeed, we show that

Lemma 3.5 The number of codewords at distance d from c′ is at least \frac{2^{k−n/2−αn}}{\sqrt{n}} except with probability 2^{−αn} for any α > 0.

Proof. Let S_{w} be the syndrome of a word w. Let N_{d}(x, y) be the number of words with syndrome y at distance d from a fixed word w with syndrome x (this function is well defined because its value is independent of the specific choice of w; moreover, N_{d}(x, y) = N_{d}(0, x ⊕ y) = N_{d}(y, x)). We first show

that N_{d}(S_{c′}, S_{c}) ≥ 2^{−r} \frac{\binom{n}{d}}{2^{n−k}} with probability at least 1 − 2^{−r} for any security parameter r > 0.

Starting from word c, each syndrome s occurs N_{d}(S_{c}, s) times among the words at distance d from c. Therefore syndrome s has probability N_{d}(S_{c}, s)/\binom{n}{d} = N_{d}(s, S_{c})/\binom{n}{d} of being selected, i.e. of being that of the actual c′. Thus, any syndrome s for which N_{d}(s, S_{c}) <

2^{−r} \frac{\binom{n}{d}}{2^{n−k}} (which would be bad because it would mean less uncertainty for Bob) has probability of occurrence

less than (2^{−r} \frac{\binom{n}{d}}{2^{n−k}})/\binom{n}{d} = \frac{1}{2^{n−k}} 2^{−r}. Even if all but one syndrome were in that category, their collective probability would still be less than 2^{−r}. This estab-

lishes the claim that N_{d}(S_{c′}, S_{c}) ≥ 2^{−r} \frac{\binom{n}{d}}{2^{n−k}}, except with probability less than 2^{−r}. Given that \binom{n}{d} ≥ \frac{2^{n/2}}{\sqrt{n}}, setting r = αn leads to the result of the lemma. _{3.5}

From Bob’s point of view, the codeword c is one of the, at least \frac{2^{k−n/2−αn}}{\sqrt{n}} many, equally likely codewords at distance d from c′ forming a set E. The following lemma says how much information Bob will consequently have about c ⊙ r for a random r.

Lemma 3.6 ([BBR88]) If Bob has narrowed down the value of c to a set E of equally likely candidates and if a random subset of the bits of c is chosen, the expected amount of Shannon information available to Bob about the parity of the bits in this subset is less than 2/|E| ln 2 bit.

In our case, this means that the number of bits of information Bob has after seeing c′ is less than \frac{2\sqrt{n}}{2^{k−n/2−αn} ln 2}. This number of bits is exponentially small as soon as k > n/2 + αn. Thus, if we pick α = 0.1 we find that the number of bits of information is at most 2^{−0.1n}\sqrt{n}/ ln 2 whenever k/n > 0.51, even if he knew the exact number of errors d. _{3.4}

In reality, Bob’s situation is much more difficult: he may not perform the optimal measurement, his measuring apparatus may be imperfect, and he does not even know the exact number of errors. Since his information about x would be very small even if he knew d and made no mistakes, his actual knowledge can only be worse.

3.2 Analysis of Bob’s probability of choosing an unsuitable G

It is a well known fact [MS77] that a random binary matrix G of size k×n defines a binary linear code with minimal distance at least d except with probability 2^{−αn} as long as

k < n − H(d/n)n − αn.

In particular if we set ε ≤ 1% we find that a random binary matrix defines a binary linear code with minimal distance at least 10εn except with probability 2^{−0.01n} as long as

k/n = 0.52 < 1 − H(0.1) − 0.01.

Therefore, Bob may choose G at random of size 0.52n × n and only with probability 2^{−0.01n} will the code thus defined have minimal distance less than 10εn, again, as long as ε ≤ 1%.

3.3 Analysis of Alice’s probability of changing x without detection

Although an honest Bob would not have as much information about x as the cheating Bob who reads each photon in basis (|B⟩, |B^{⊥}⟩), he would have something more: the honest Bob has the ability to check that Alice is indeed committed to some bit.

Theorem 3.7 There exists a positive constant α < 1 with the following property: the probability that Alice is able to announce either pair (c^{0}, b^{0}) or pair (c^{1}, b^{1}) at her choosing in protocol unveil leading Bob to accept a 0 and a 1, is less than α^{n}.

Proof. Let (c^{0}, b^{0}) and (c^{1}, b^{1}) be any pairs of n-bit strings such that c^{0} ⊙ r = 0 and c^{1} ⊙ r = 1. Since c^{0}⊙r ≠ c^{1}⊙r, it must be that c^{0} ≠ c^{1}. By construction of the code C, any two codewords must be at distance at least 10εn from each other. Let I be the set of indices on which c^{0} and c^{1} disagree: I = {i | c_{i}^{0} ≠ c_{i}^{1}}. We show that whatever Alice does, with high probability, I_{0} ← {i ∈ I | c_{i}^{0} ≠ c′_{i} ∧b_{i}^{0} = b′_{i}} or I_{1} ← {i ∈ I | c_{i}^{1} ≠ c′_{i} ∧b_{i}^{1} = b′_{i}} has size more than 0.7εn. Since I_{0} ∩ I_{1} = ∅, and thus |I_{0} ∪ I_{1}| = |I_{0}| + |I_{1}|, it suffices to show

Lemma 3.8 Except with probability α^{n} for some constant α < 1,

I_{0} ∪ I_{1} = {i ∈ I | c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i}}

has size more than 1.4εn.

Proof. For each i ∈ I consider

Prob(c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i}).

The size of I_{0} ∪ I_{1} can be estimated by a binomial distribution with respect to a lower bound for this probability. We start by giving such a lower bound.

Lemma 3.9 For each i ∈ I,

Prob(c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i}) ≥ σ^{2}

Proof. First notice that for i ∈ I, if b_{i}^{0} = b_{i}^{1} then

Prob(c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i}) = 1/2 (1)

since Bob has probability \frac{1}{2} of choosing the same basis b_{i}^{0} = b′_{i} = b_{i}^{1}. The more complicated question is to determine this probability for b_{i}^{0} ≠ b_{i}^{1}. Without loss of generality we may assume b_{i}^{1} = c_{i}^{0} ≠ c_{i}^{1} = b_{i}^{0}, since the only other possibility b_{i}^{0} = c_{i}^{0} ≠ c_{i}^{1} = b_{i}^{1}, is treated similarly. Then we get

Prob(c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i})
= Prob(c′_{i} = b′_{i})  (2)

because

Prob(c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i})
= Prob(b_{i}^{1} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨b_{i}^{0} ≠ c′_{i}∧b_{i}^{1} = b′_{i})
= Prob(c′_{i} = b′_{i} = b_{i}^{0}∨c′_{i} = b′_{i} = b_{i}^{1})
= Prob(c′_{i} = b′_{i})

(The other case leads to Prob(c′_{i} ≠ b′_{i}))

But how small can Alice make these probabilities?

Assume first that Alice sends Bob a photon π_{i} polarized as a pure state |Ψ⟩ at step i (please consult the Appendix for the notion of pure states).

Prob(c′_{i} = b′_{i}) = \frac{1}{2}⟨↔|Ψ⟩^{2} + \frac{1}{2}⟨ ↘ ↖ |Ψ⟩^{2}

= \frac{1}{2} [(1, 0)\binom{cos θ}{sin θ}]^{2} + \frac{1}{2} [(\frac{−1}{\sqrt{2}}, \frac{1}{\sqrt{2}})\binom{cos θ}{sin θ}]^{2}

for the θ such that |Ψ⟩ = (cos θ)|↔⟩ + (sin θ)|↕⟩. Therefore

Prob(c′_{i} = b′_{i}) = \frac{1}{2} cos^{2} θ + \frac{1}{2} (\frac{sin θ − cos θ}{\sqrt{2}} )^{2}
= \frac{\frac{1}{2} + cos^{2} θ − sin θ cos θ}{2} .

The minimum and maximum of this expression are σ^{2} and κ^{2}. So, for any pure state |Ψ⟩,

σ^{2} ≤ Prob(c′_{i} = b′_{i}) ≤ κ^{2}  (3)
(and similarly σ^{2} ≤ Prob(c′_{i} ≠ b′_{i}) ≤ κ^{2}).

It is a fact of quantum physics that the polarization of any photon can be described by a mixture of pure states (see the Appendix). Therefore, if π_{i} is not in a pure state, it may be represented as a mixture of pure states |Ψ_{1}⟩, |Ψ_{2}⟩, ..., |Ψ_{m}⟩ with probabilities p_{1}, p_{2}, ..., p_{m} such that ∑ p_{j} = 1. We get the same result in this case since it holds for each |Ψ_{j}⟩ individually. We therefore conclude from (1), (2) and (3) that in all cases, for each i ∈ I

σ^{2} ≤ Prob(c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i}) ≤ κ^{2}

3.9

Now, since |I| ≥ 10εn, |I_{0} ∪ I_{1}| will be given by a binomial distribution with mean at least 10σ^{2}εn over |I| trials. Let u_{i} be the characteristic function of I_{0} ∪ I_{1}, i.e.

u_{i} ← \{ \begin{matrix}1 & if c_{i}^{0} ≠ c′_{i}∧b_{i}^{0} = b′_{i}∨c_{i}^{1} ≠ c′_{i}∧b_{i}^{1} = b′_{i} \\ 0 & otherwise \end{matrix}

The probability that |I_{0}∪I_{1}| < 1.4εn is therefore going to be very small:

Prob(|I_{0} ∪ I_{1}| < 1.4εn)

= Prob(∑_{i∈I} u_{i} < 1.4εn)
= Prob(∑_{i∈I} \frac{u_{i}}{10εn} < 0.14)
≤ Prob(∑_{i∈I} \frac{u_{i}}{|I|} < 0.14)
= Prob(∑_{i∈I} \frac{u_{i}}{|I|} − σ^{2} < 0.14 − σ^{2})
≤ Prob(| ∑_{i∈I} \frac{u_{i}}{|I|} − σ^{2}| ≥ σ^{2} − 0.14)
≤ 2e^{−|I|(σ^{2}−0.14)^{2}}
≤ 2e^{−10εn(σ^{2}−0.14)^{2}}
≈ 2e^{−0.000415587εn}.

3.8

We conclude from the lemma, that except with probability 2e^{−0.000415587εn}, at least one of I_{0} or I_{1} must have size more than 0.7εn and thus Bob would necessarily reject either (c^{0}, b^{0}) or (c^{1}, b^{1}) at step 3 of protocol unveil. _{3.7}

3.4 Analysis of Bob’s probability of rejecting a valid c

Despite the good will of Alice, there is a small probability that Bob will reject the correct pair (c, b) because of unlikely extreme noise in the quantum channel. We finally show that this event occurs with exponentially small probability.

Theorem 3.10 If Alice is honest, then there exists a constant α < 1 such that an honest Bob rejects (c, b, x) with probability less than α^{n}.

Proof. An error will be observed by Bob exactly if b_{i} = b′_{i}, while c_{i} ≠ c′_{i}. The probability of such an event due to noise is less than \frac{ε}{2}, by definition of ε and because Prob(b′_{i} = b_{i}) = \frac{1}{2}. What is therefore the probability of observing at least 0.7εn errors?

Let

v_{i} = \{ \begin{matrix}1 & if b_{i} = b′_{i}∧c_{i} ≠ c′_{i} \\ 0 & otherwise \end{matrix}

be the characteristic function of the observation of errors. The probability of observing more than 0.7εn errors is given by Prob(∑_{i=1}^{n} v_{i} > 0.7εn) and is bounded as follows

Prob(∑_{i=1}^{n} v_{i} > 0.7εn)

= Prob(∑_{i=1}^{n} \frac{v_{i}}{n} − 0.5ε > 0.2ε)

≤ Prob(| ∑_{i=1}^{n} \frac{v_{i}}{n} − 0.5ε| > 0.2ε)
≤ 2e^{−n(0.2ε)^{2}} = 2e^{−0.04ε^{2}n}.

3.10

4 Conclusion and Open Questions

We have described a complete protocol for Bit Commitment based on the transmission of polarized photons. We have shown that under the laws of quantum physics, this protocol cannot be cheated by either party except with exponentially small probability (exponential in the running time needed to implement the honest protocol).

A more thorough analysis is required to adjust all the constants used in this paper to get the best performance from our construction. Better performances may probably be achieved by using a third conjugate transmission-reception basis of circular polarization. This analysis will appear in the final version of this paper.

Acknowledgements

We wish to thank Charles H. Bennett, Joe Kilian, Asher Peres, Louis Salvail, and Miklòs Santhà, for support, suggestions and comments on this work. We are grateful to Joe Kilian for noticing that a single codeword is sufficient in protocol commit, and to Louis Salvail for asking “Who will choose the code C?”.

Finally, we thank God for playing dice.

References

[BBBSS92] C. H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin. Experimental quantum cryptography. Journal of Cryptology, 5:3–28, 1992.

[BB84] C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, pages 175–179. IEEE, 1984.

[BB85] C. H. Bennett and G. Brassard. An update on quantum cryptography. In Advances in Cryptology: Proceedings of Crypto ’84, Lecture Notes in Computer Science, Vol. 196, pages 475–480. Springer-Verlag, 1985.

[BB89] C. H. Bennett and G. Brassard. The dawn of a new era for quantum cryptography: the experimental prototype is working! SIGACT News, 20(4):78–82, 1989.

[BBBW83] C. H. Bennett, G. Brassard, S. Breidbart, and S. Wiesner. Quantum cryptography, or unforgeable subway tokens. In Advances in Cryptology: Proceedings of Crypto ’82, pages 267–275. Plenum Press, 1983.

[BBCS92] C. H. Bennett, G. Brassard, C. Crépeau, and M.-H. Skubiszewska. Practical quantum oblivious transfer. In Advances in Cryptology: Proceedings of Crypto ’91, Lecture Notes in Computer Science, Vol. 576, pages 351–366. Springer-Verlag, 1992.

[BBR88] C. H. Bennett, G. Brassard, and J.–M. Robert. Privacy amplification by public discussion. SIAM Journal on Computing, 17(2):210–229, April 1988.

[Blu82] M. Blum. Coin flipping by telephone. In Proceedings of IEEE Spring Computer Conference, pages 133–137. IEEE, 1982.

[BCC88] G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37:156–189, 1988.

[BC91] G. Brassard and C. Crépeau. Quantum bit commitment and coin tossing protocols. In Advances in Cryptology: Proceedings of Crypto ’90, Lecture Notes in Computer Science, Vol. 537, pages 49–61. Springer-Verlag, 1991.

[Cré90] C. Crépeau. Correct and Private Reductions among Oblivious Transfers. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990. Supervised by Silvio Micali.

[Cré93] C. Crépeau. Cryptographic primitives and quantum theory. In Proceedings of Workshop on Physics and Computation, PhysComp 92, pages 200–204, 1993.

[CK88] C. Crépeau and J. Kilian. Achieving oblivious transfer using weakened security assumptions. In 29^{th} Symposium on Foundations of Computer Science, pages 42–52. IEEE, 1988.

[EPR35] A. Einstein, B. Podolsky, and N. Rosen. Can quantum-mechanical description of physical reality be considered complete? Physical Review, 47:777, 1935.

[GMW91] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity, or All languages in N P have zero-knowledge proof systems. Journal of the ACM, 38:691–729, 1991.

[GMR89] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal on Computing, 18:186–208, 1989.

[Hel76] C. W. Helstrom. Quantum Detection and Estimation Theory. Academic Press, 1976.

[Kra86] E. Kranakis. Primality and cryptography. John Wiley and Sons, 1986.

[MS77] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.

[Sud86] A. Sudbery. Quantum Mechanics and the Particles of Nature — an Outline for Mathematicians. Cambridge University Press, 1986.

[Wie83] S. Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, 1983. Manuscript written circa 1970, unpublished until it appeared in SIGACT News.

Appendix: Outline of Some Relevant Quantum Theory

In quantum physics, the state space of a single photon is the collection of all unit vectors in a two dimensional complex Hilbert space H. We use the Dirac bracket notation ([Sud86] chapter 2), commonly used in physics, to denote the states. In this notation the state vectors are written using right-handed pointed brackets. If \binom{u}{v} is a state in H (given in terms of its components with respect to some basis) we write

|ψ⟩ = \binom{u}{v}.

The corresponding left-handed bracket, enclosing the same symbol, denotes the complex conjugate transpose

⟨ψ| = (u^{∗}, v^{∗})

and juxtaposition represents matrix multiplication. Thus if

|ψ_{1}⟩ = \binom{u_{1}}{v_{1}} |ψ_{2}⟩ = \binom{u_{2}}{v_{2}}

then

⟨ψ_{1}|ψ_{2}⟩ = (u_{1}^{∗}, v_{1}^{∗}) (\begin{matrix}u_{2} \\ v_{2} \end{matrix})
= u_{1}^{∗}u_{2} + v_{1}^{∗}v_{2}

is a complex number giving the inner product of the states and

|ψ_{1}⟩⟨ψ_{2}| = (\begin{matrix}u_{1} \\ v_{1} \end{matrix}) (u_{2}^{∗}, v_{2}^{∗})
= ( \begin{matrix}u_{1}u_{2}^{∗} & u_{1}v_{2}^{∗} \\ v_{1}u_{2}^{∗} & v_{1}v_{2}^{∗} \end{matrix} )

is an outer product giving a linear operation on H, which maps a vector |ξ⟩ to the vector |ψ_{1}⟩⟨ψ_{2}|ξ⟩. In particular |ψ⟩⟨ψ| is the operation of orthogonal projection into the one dimensional subspace of H in the direction of the unit vector |ψ⟩.

The states of horizontal and vertical polarization, denoted |↕⟩ and |↔⟩, form an orthonormal basis of H (called the rectilinear basis) as do the states of diagonal polarization (at 45^{∘} and 135^{∘}) defined by

| ↗ ↙ ⟩ = (|↕⟩ + |↔⟩) /\sqrt{2}
| ↘ ↖ ⟩ = (|↕⟩ − |↔⟩) /\sqrt{2}.

Another important basis is |B⟩, |B^{⊥}⟩ defined in Section 3.1, which corresponds to linear polarization in directions midway between the above two bases. (In this paper we do not use photons with circular polarization, which correspond to linear combinations of |↕⟩ and |↔⟩ with complex, rather than real, coefficients.)

According to the formalism of quantum physics, any physical measurement on a photon is described in terms of a decomposition of the Hilbert space H into a family of orthogonal subspaces, one for each measurement outcome^{1}. When a measurement is performed on a photon in state |ψ⟩ each outcome may occur with probability given by the squared length of the projection of |ψ⟩ into the corresponding subspace. As a result of the measurement, the original state |ψ⟩ is obliterated and replaced by the projected vector (renormalized to unit length) corresponding to the seen outcome. Thus, we may associate a measurement to any orthogonal basis of H. The rectilinear and diagonal bases have the following “conjugacy” property: if a measurement in one basis is carried out on either vector of the other basis, then the two outcomes always occur with probability \frac{1}{2} and all information about the measured state is obliterated. Thus we get zero information about which of the two basis states was supplied. However if a basis vector is measured in the same basis, then it is identified with certainty and the state is left unchanged.

In certain situations, the state of a photon may not be describable by a “pure” state in H (that is, a vector in the Hilbert space). This occurs in two possible ways (see [Sud86] chapter 5) (a) the state is known only to the extent of being one of a “mixture” of states |ψ_{1}⟩, …, |ψ_{n}⟩ with probabilities p_{1}, …, p_{n}; (b) the photon is “entangled” with some other system and only the larger joint system has a description as a pure state (in a larger Hilbert space). The situation (a) occurs in step 4 of protocol commit — Alice’s signal to Bob for the value c_{i} = 0 is one of two possible (non orthogonal) states randomly chosen with probability \frac{1}{2} (and similarly for the value 1). To the general mixture in (a) above we associate the density matrix

ρ = ∑_{i} p_{i} |ψ_{i}⟩⟨ψ_{i}|,

which is the average projection operator for the state distribution. For the special case of a pure state |ψ⟩, the density matrix is simply |ψ⟩⟨ψ|. A straightforward extension of the measurement theory outlined above shows that the results of any physical measurement whatever on the mixture depend on the states and probabilities constituting the mixture only through the combination ρ. This is rather curious since the same density matrix may arise from very different mixtures of states. Thus any two such mixtures, having the same density matrix, cannot be distinguished by any physical measurement. We exploit this property of quantum measurement theory in Theorem 3.1, using the fact that a (\frac{1}{2}, \frac{1}{2}) mixture of the non orthogonal states |↕⟩ and | ↘ ↖ ⟩ has the same density matrix as the (1 − κ^{2}, κ^{2}) mixture of the orthogonal states |B⟩ and |B^{⊥}⟩.

1Actually there is a more general notion of measurement, the so called POM or “Positive-Operator-Valued” measurements (see [Hel76, pp. 74–83] for details) which we omit for the sake of clarity. However it is straightforward to see that the argument in the proof of Theorem 3.1 also covers these more general measurements.

With regard to the situation (b), the most famous example of an entangled state is the joint state of two particles occurring in the Einstein–Podolsky–Rosen effect [EPR35]. If a photon is entangled with any other system then it can be shown ([Sud86] chapter 5) that the photon alone may always be described by a suitable density matrix, i.e. as far as measurements on the photon alone are concerned, it is physically indistinguishable from a suitable mixture of states, and follows the analysis of (a). This fact is relevant in the proof of Lemma 3.9 (where Alice may attempt to cheat by entangling her photons with each other or with some other system, which is precisely how the 1984 quantum bit commitment scheme of Bennett and Brassard could be broken [BB84]). Thus the density matrix formalism provides a uniform way of describing a single photon or an arbitrarily complex set of photons in the most general possible situation.