Quantum Bit Commitment and Coin Tossing Protocols

Gilles Brassard ^{∗}

Département d’informatique et de R.O. Université de Montréal C.P. 6128 succ. “A” Montréal, Québec Canada H3C 3J7

Claude Crépeau ^{†}

Laboratoire de Recherche en Informatique Université de Paris-Sud Bâtiment 490 91405 Orsay France

1 Introduction

In the late 1960’s a physicist, Stephen Wiesner, had the idea that the uncertainty principle could be used for cryptography (though he published his result much later [Wie83]). His idea was that it would be possible to transmit the values of two pieces of information using beams of photons in a way that would make only one of them readable at the receiver’s choosing. This notion, which he called “multiplexing” is remarkably similar to the “one-out-of-two Oblivious Transfer” to be reinvented many years later [EGL83]. A decade after his original invention, Charles H. Bennett and Gilles Brassard brought Wiesner’s idea back to life in a Crypto ’82 talk. Subsequently, they used quantum cryptographic principles to implement basic cryptographic protocols, such as secret key exchange and coin flipping by telephone [BB84]. There has been very recently renewed interest in quantum cryptography because a working prototype of the quantum key exchange channel has been successfully built at the IBM T. J. Watson Research Laboratory, Yorktown Heights [BBBSS90].

In recent times, the importance of cryptographic primitives has been brought to light by the work of many researchers whose goal is to characterize precisely the primitives sufficient for the implementation of various cryptographic protocols. One of these primitives is a Bit Commitment Scheme. The importance and usefulness of such a primitive is enlightened by the work of [GMW86,BCC88] to mention just a few.

While such primitives are usually built under computational complexity assumptions, it is sometimes possible to build such things based on assumptions of a different nature as pointed out by the work mentioned earlier of [Wie83,BB84]. The current paper presents the state-of-the-art in the technology of building a bit commitment scheme on a quantum mechanical assumption. The applications are numerous, including secure two-party computation.

∗Supported in part by Canada NSERC grant A4107.

†Supported in part by NSERC Postgraduate and Postdoctorate Scholarships. This research was performed in part while the author was a graduate student at M.I.T. and while visiting the IBM Almaden Research Center.

Figure 1: The behaviour of a photon passing through a Wallaston prism

2 Physics background

For a complete coverage of the physics of quantum cryptography, please consult [BB84]. The linear polarization of photons is a quantum state. In general, the value of this variable cannot be determined exactly. According to quantum mechanics, although the value of the polarization can be any angle in the (real) interval [0^{∘}, 180^{∘}), only a boolean (two states) predicate can be measured about this variable. Moreover, only one such measurement can be performed on any given photon because the measurement itself necessarily destroys the information. For instance, let Θ be the polarization of a photon. Assuming that it is known a priori that Θ is either 0^{∘} or 90^{∘}, the predicate “Is Θ = 0^{∘}?” can be measured accurately for these two quantum states. On the other hand, even if Θ is known to be either 0^{∘} or 45^{∘}, then no measuring apparatus can distinguish between these two states with certainty, although some probabilistic information can be obtained. If we have no constrain on the set of possible values for Θ then answering “Is Θ = 0^{∘}?” will result in a probabilistic answer determined by the value of Θ: it will always be “yes” if Θ = 0^{∘}, otherwise it will be “no” with a probability that ranges from 0 to 1 as Θ ranges from 0^{∘} to 90^{∘}.

It is not a matter of technology, it is not that no one has a good enough device to figure out Θ; quantum theory claims that it is impossible to determine this value with certainty. In a sense, the value does not really exist: it is just a probability distribution.

However, it is possible to build a device that always says “yes” if Θ = 0^{∘} and always says “no” when Θ = 90^{∘}. In general, with such a device, Prob(device says “yes”|Θ) = cos^{2}(Θ). This can be obtained by combining a Wallaston prism with two photomultipliers (photon detectors). See figure 1. Consider a Wallaston prism set for distinguishing polarization angles φ from φ + 90^{∘}. A photon polarized at angle Θ will come out of this Wallaston prism on the right side with probability cos^{2}(Θ − φ) (and will then be repolarized at angle φ) and on the left side with complement probability sin^{2}(Θ − φ) (and will then be repolarized at angle φ + 90^{∘}). According to quantum mechanics, this device is the best that can be built with respect to measuring Θ.

3 Review of earlier quantum protocols

3.1 A bit commitment scheme

Consider two parties: S and R. Assume that S has a bit b in mind, to which she would like to be committed toward R. That is, S wishes to provide R with a piece of evidence that she has a bit in mind and that she cannot change it. Meanwhile, R should not be able to tell from that evidence what b is.

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 it is obvious how to modify it in order to implement bit commitment). Let us briefly review this protocol and its main weakness before describing our new scheme in Section 4. Assume that S wishes to commit to bit b toward R. Let s be a security parameter.

Protocol 3.1 ( BB-commit(b) )

1: S chooses a vector B = (b_{1}, b_{2}, ..., b_{s}) of s random bits

2: R chooses a vector Θ = (φ_{1}, φ_{2}, ..., φ_{s}) of s random φ_{i} ∈ {0^{∘}, 45^{∘}}

3: DO_{i=1}^{s} S sends a photon with polarization b × 45^{∘} + b_{i} × 90^{∘} that R reads at angle φ_{i}.

R sets b′_{i} ← \{ \begin{matrix}0 & if photon came out on the right \\ 1 & if photon came out on the left \end{matrix}

4: R keeps Θ and B′ = (b′_{1}, b′_{2}, ..., b′_{s}) secret

5: S keeps b and B secret until (and if) decommittal

Notice that since b_{i} is chosen at random, the received bit b′_{i} reveals no information about b. Therefore receiving B′ = (b′_{1}, b′_{2}, ..., b′_{s}) reveals nothing about b. In fact, a much stronger statement can be proved: quantum mechanics tells us that no measuring apparatus can distinguish a commitment to 0 from a commitment to 1 unless it is possible to communicate information faster than the speed of light. But why is S committed?

To open her commitment, S initiates the following protocol with R.

Protocol 3.2 ( BB-decommit((B, b), (B′, Θ)) )

1: S reveals b and B to R

2: DO_{i=1}^{s} R checks that b′_{i} = b_{i} whenever φ_{i} = b × 45^{∘}

3: if this condition is satisfied for all i then R outputs “accept” else R outputs “reject”

First note that if S is honest then the condition is always satisfied. Now suppose that a cheating S tries to “commit” in a way that will enable her to open B as b or b̄ at her later choice. In order to achieve this, she must find two strings B^{0} and B^{1} such that B^{b} satisfies the condition above when trying to open as b ∈ {0, 1}. This implies that b_{i}^{0} = b′_{i} whenever φ_{i} = 0^{∘} and that b_{i}^{1} = b′_{i} whenever φ_{i} = 45^{∘}.

When both S and R are honest, S knows that Prob(b_{i} = b′_{i}) = \frac{3}{4}. When only R is honest, the maximum information that S may get about each b′_{i} is by sending her bits b_{i} using angle 22\frac{1}{2}^{∘} + b_{i} × 90^{∘}, which gives her Prob(b_{i} = b′_{i}) = cos^{2}(22\frac{1}{2}^{∘}) ≈ 85% (it is an easy exercise to figure out that this is S’s optimal strategy). Still, S will always have a probability of sin^{2}(22\frac{1}{2}^{∘}) ≈ 15% of guessing b′_{i} incorrectly.

Now for all the indices i where b_{i}^{0} = b_{i}^{1}, S has at least probability sin^{2}(22\frac{1}{2}^{∘}) that b_{i}^{0} ≠ b′_{i} and b_{i}^{1} ≠ b′_{i}. When b_{i}^{0} ≠ b_{i}^{1} it is even worse since one of b_{i}^{0} or b_{i}^{1} is necessarily wrong. Because S has no information about φ_{i}, she has no information about which of b_{i}^{0} or b_{i}^{1} she should set as 0 or 1. Therefore her probability of failure in this second case is \frac{1}{2}. We conclude that the probability of success that S builds such B_{0} and B_{1} is at most (cos^{2}(22\frac{1}{2}^{∘}))^{s}.

3.2 Coin tossing

Bennett and Brassard used this bit commitment scheme in order to implement a protocol for coin tossing by (quantum!) “telephone” [Blu81] as follows:

Protocol 3.3 ( BB-cointoss )

1: S chooses a random bit b_{0} and uses BB-commit(b_{0}) with R

2: R chooses a random bit b_{1} and sends it to S

3: S runs BB-decommit(b_{0}) with R

4: R wins the coin toss if and only if b_{1} = b_{0}

The resulting protocol can be broken exactly if the bit commitment scheme can be broken.

3.3 The problem of dependence

As mentioned in [BB84] the bit commitment scheme of section 3.1 and the resulting coin tossing protocol can be defeated in theory using the consequences of the Einstein-Podolsky-Rosen “paradox”. The interested reader can consult their paper for a more detailed explanation. We call this problem “dependence” because E-P-R is based on the fact that it is possible to create pairs of photons with a dependence relation between their polarizations (it is possible to have some correlation between measurements). In practice, this kind of attack is rather improbable because the technology necessary to perform it is far beyond the current available technology, and because even a small failure in the cheater’s technology will result in loss of his possibility of cheating. Nevertheless, from a theoretical point of view, it is important to get around this difficulty.

In the next section we offer our new bit commitment scheme, which cannot be broken through E-P-R.

4 A new bit commitment scheme

4.1 How to commit

In order to commit to a bit b, S builds a random s × s boolean matrix:

B = ( \begin{matrix}b_{1,1} & … & b_{1,s} \\ ⋮ & ... & ⋮ \\ b_{s,1} & … & b_{s,s} \end{matrix} )  (1)

with the following property:

∀1 ≤ i ≤ s [⨁_{j=1}^{s} b_{i,j} = b]  (2)

and sends it to R using the following protocol.

Protocol 4.1 ( BC-commit(b) )

1: S builds a random s × s boolean matrix B as indicated above

2: DO_{i=1}^{s}DO_{j=1}^{s} S chooses a random φ_{i,j} ∈ {0^{∘}, 45^{∘}} and R chooses a random φ_{i,j} ∈ {0^{∘}, 45^{∘}}

3: DO_{i=1}^{s}DO_{j=1}^{s} S sends a photon with polarization φ_{i,j} + b_{i,j} × 90^{∘} that R reads at angle φ_{i,j}.

R sets b′_{i,j} ← \{ \begin{matrix}0 & if photon came out on the right \\ 1 & if photon came out on the left \end{matrix}

4: R keeps B′ and Θ (see below) secret

5: S keeps b, B and Φ (see below) secret until (and if) decommittal

where

B′ = ( \begin{matrix}b′_{1,1} & … & b′_{1,s} \\ ⋮ & ... & ⋮ \\ b′_{s,1} & … & b′_{s,s} \end{matrix} ) , Θ = ( \begin{matrix}θ_{1,1} & … & θ_{1,s} \\ ⋮ & ... & ⋮ \\ θ_{s,1} & … & θ_{s,s} \end{matrix} ) , Φ = ( \begin{matrix}φ_{1,1} & … & φ_{1,s} \\ ⋮ & ... & ⋮ \\ φ_{s,1} & … & φ_{s,s} \end{matrix} )  (3)

If both participants are honest, B′ is such that

∀1 ≤ i ≤ s, 1 ≤ j ≤ s [Prob(b_{i,j} = b′_{i,j}) = \frac{3}{4}]  (4)

However, if R uses angle φ_{i,j} = 22\frac{1}{2}^{∘} he will end up getting maximum information about B. That is ∀1 ≤ i ≤ s, 1 ≤ j ≤ s [Prob(b_{i,j} = b′_{i,j}) = cos^{2}(22\frac{1}{2}^{∘})]. Nevertheless, even then the matrix B′ reveals very little about b. We measure this fact by computing Prob(b = 0|B′) and Prob(b = 1|B′) for every possible B′. We are satisfied if there exists a positive constant α < 1 such that

|Prob(b = 0|B′) − Prob(b = 1|B′)| ≤ α^{s}

for every B′. Since Prob(b = 0|B′) + Prob(b = 1|B′) = 1, the following condition is sufficient for this result:

Theorem 4.1 There exists a positive constant α < 1 such that

\frac{1}{2} − α^{s} ≤ Prob(b = 0|B′) ≤ \frac{1}{2} + α^{s}

Proof.

Provided in the journal version of the paper. □

Lemma 4.2 \frac{1}{2} − s(2p − 1)^{s} ≤ Prob(b|B′) ≤ \frac{1}{2} + s(2p − 1)^{s}

Proof. Let B_{i} and B′_{i} be the i^{th} line of B and B′. Let b_{i} = ⨁_{j=1}^{s} b_{i,j} and define b′_{i} similarly.

Prob(b|B′) = \frac{Prob(B′|b)Prob(b)}{Prob(B′)}  (5)
= \frac{Prob(B′|b)Prob(b)}{Prob(b)Prob(B′|b) + Prob(b̄)Prob(B′|b̄)}  (6)
= \frac{Prob(B′|b)}{Prob(B′|b) + Prob(B′|b̄)}  (7)

since Prob(b) = Prob(b̄) = \frac{1}{2}

= \frac{1}{1 + \frac{Prob(B′|b̄)}{Prob(B′|b)}}  (8)

Now we focus our attention on this ratio:

\frac{Prob(B′|b̄)}{Prob(B′|b)} = \frac{Prob(B′ ∧ b̄)}{Prob(B′ ∧ b)}  (9)

= \frac{∑_{B} Prob(B′ ∧ B ∧ b̄)}{∑_{B} Prob(B′ ∧ B ∧ b)}  (10)

= \frac{∑_{B|b_{1}=b_{2}=...=b_{s}=b̄} Prob(B′ ∧ B)}{∑_{B|b_{1}=b_{2}=...=b_{s}=b} Prob(B′ ∧ B)}  (11)

= \frac{∑_{B_{i}|b_{i}=b̄,1≤i≤s} Prob(B′_{1} ∧ B_{1} ∧ ... ∧ B′_{s} ∧ B_{s})}{∑_{B_{i}|b_{i}=b,1≤i≤s} Prob(B′_{1} ∧ B_{1} ∧ ... ∧ B′_{s} ∧ B_{s})}  (12)

= \frac{∑_{B_{i}|b_{i}=b̄,1≤i≤s} Prob(B′_{1} ∧ B_{1})...Prob(B′_{s} ∧ B_{s})}{∑_{B_{i}|b_{i}=b,1≤i≤s} Prob(B′_{1} ∧ B_{1})...Prob(B′_{s} ∧ B_{s})}  (13)

since these events are all independent

= ∏_{i=1}^{s} \frac{∑_{B_{i}|b_{i}=b̄} Prob(B′_{i} ∧ B_{i})}{∑_{B_{i}|b_{i}=b} Prob(B′_{i} ∧ B_{i})}  (14)

= ∏_{i=1}^{s} \frac{∑_{B_{i}|b_{i}=b̄} Prob(B′_{i}|B_{i})}{∑_{B_{i}|b_{i}=b} Prob(B′_{i}|B_{i})}  (15)

but this ratio is

\frac{∑_{B_{i}|b_{i}=b̄} Prob(B′_{i}|B_{i})}{∑_{B_{i}|b_{i}=b} Prob(B′_{i}|B_{i})} = \{ \begin{matrix}\frac{Prob(an even number of errors occurred)}{Prob(an odd number of errors occurred)} & if b′_{i} = b̄ \\ \frac{Prob(an odd number of errors occurred)}{Prob(an even number of errors occurred)} & if b′_{i} = b \end{matrix}  (16)

= (\frac{Prob(an odd number of errors occurred)}{Prob(an even number of errors occurred)})^{(−1)^{b′_{i}⊕b}}  (17)

= (\frac{\begin{aligned}⌊ & \frac{s−1}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned} \binom{s}{2j + 1}p^{s−2j−1}(1 − p)^{2j+1}}{\begin{matrix}⌊ & \frac{s}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{s}{2j}p^{s−2j}(1 − p)^{2j}} )^{(−1)^{b′_{i}⊕b}}  (18)

Now notice that

\begin{matrix}⌊ & \frac{s}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{s}{2j}p^{s−2j}(1 − p)^{2j} + \begin{aligned}⌊ & \frac{s−1}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned} \binom{s}{2j + 1}p^{s−2j−1}(1 − p)^{2j+1}  (19)

= ∑_{j=0}^{s} \binom{s}{j}p^{s−j}(1 − p)^{j}  (20)
= 1  (21)

and

\begin{matrix}⌊ & \frac{s}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{s}{2j}p^{s−2j}(1 − p)^{2j} − \begin{aligned}⌊ & \frac{s−1}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned} \binom{s}{2j + 1}p^{s−2j−1}(1 − p)^{2j+1}  (22)

= ∑_{j=0}^{s} \binom{s}{j}p^{s−j}(p − 1)^{j}  (23)
= (2p − 1)^{s}  (24)

therefore we get by adding these two equations

\begin{aligned}⌊ & \frac{s−1}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned} \binom{s}{2j + 1}p^{s−2j−1}(1 − p)^{2j+1} = \frac{1 − (2p − 1)^{s}}{2}  (25)

\begin{matrix}⌊ & \frac{s}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{s}{2j}p^{s−2j}(1 − p)^{2j} = \frac{1 + (2p − 1)^{s}}{2}  (26)

returning to equation 18 we get

\frac{∑_{B_{i}|b_{i}=b̄} Prob(B′_{i}|B_{i})}{∑_{B_{i}|b_{i}=b} Prob(B′_{i}|B_{i})} = (\frac{1 − (2p − 1)^{s}}{1 + (2p − 1)^{s}} )^{(−1)^{b′_{i}⊕b}}  (27)

using equation 15 and defining for simplicity ε = \frac{(2p−1)^{s}}{2} .

\frac{Prob(B′|b̄)}{Prob(B′|b)} = ∏_{i=1}^{s} (\frac{1 − 2ε}{1 + 2ε})^{(−1)^{b′_{i}⊕b}}  (28)

= (\frac{1 − 2ε}{1 + 2ε})∑_{i=1}^{s}(−1)^{b′_{i}⊕b}  (29)

Now, we bound this ratio in the following way

(\frac{1 − 2ε}{1 + 2ε})^{s} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ (\frac{1 − 2ε}{1 + 2ε})^{−s}  (30)
(\frac{1 − 2ε}{1 + 2ε})^{s} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ (\frac{1 + 2ε}{1 − 2ε})^{s}  (31)
(1 − \frac{4ε}{1 + 2ε})^{s} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ (1 + \frac{4ε}{1 − 2ε})^{s}  (32)
∑_{i=0}^{s} \binom{s}{i} (\frac{−4ε}{1 + 2ε})^{i} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ ∑_{i=0}^{s} \binom{s}{i} (\frac{4ε}{1 − 2ε})^{i}  (33)
1 − ∑_{i=1}^{s} \binom{s}{i} (\frac{4ε}{1 + 2ε})^{i} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ 1 + ∑_{i=1}^{s} \binom{s}{i} (\frac{4ε}{1 − 2ε})^{i}  (34)
1 − ∑_{i=1}^{s} (\frac{4sε}{1 + 2ε})^{i} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ 1 + ∑_{i=1}^{s} (\frac{4sε}{1 − 2ε})^{i}  (35)
1 − ∑_{i=1}^{∞} (\frac{4sε}{1 + 2ε})^{i} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ 1 + ∑_{i=1}^{∞} (\frac{4sε}{1 − 2ε})^{i}  (36)
1 − \frac{\frac{4sε}{1+2ε}}{1 − \frac{4sε}{1+2ε}} ≤ \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ 1 + \frac{\frac{4sε}{1−2ε}}{1 − \frac{4sε}{1−2ε}}  (37)

in order to get

2 − \frac{\frac{4sε}{1+2ε}}{1 − \frac{4sε}{1+2ε}} ≤ 1 + \frac{Prob(B′|b̄)}{Prob(B′|b)} ≤ 2 + \frac{\frac{4sε}{1−2ε}}{1 − \frac{4sε}{1−2ε}}  (38)

(2 + \frac{\frac{4sε}{1−2ε}}{1 − \frac{4sε}{1−2ε}} )^{−1} ≤ Prob(b|B′) ≤ (2 − \frac{\frac{4sε}{1+2ε}}{1 − \frac{4sε}{1+2ε}} )^{−1}  (39)
\frac{1 − \frac{4sε}{1−2ε}}{2 − \frac{4sε}{1−2ε}} ≤ Prob(b|B′) ≤ \frac{1 − \frac{4sε}{1+2ε}}{2 − \frac{12sε}{1+2ε}}  (40)
\frac{1}{2} − \frac{\frac{2sε}{1−2ε}}{2 − \frac{4sε}{1−2ε}} ≤ Prob(b|B′) ≤ \frac{1}{2} + \frac{\frac{2sε}{1+2ε}}{2 − \frac{12sε}{1+2ε}}  (41)
\frac{1}{2} − \frac{sε}{1 − 2ε − 2sε} ≤ Prob(b|B′) ≤ \frac{1}{2} + \frac{sε}{1 + 2ε − 6sε}  (42)
\frac{1}{2} − 2sε ≤ Prob(b|B′) ≤ \frac{1}{2} + 2sε  (43)

this last statement is true if sε < \frac{1}{6}. Finally by definition of ε we get

\frac{1}{2} − s(2p − 1)^{s} ≤ Prob(b|B′) ≤ \frac{1}{2} + s(2p − 1)^{s}  (44)

□

The theorem follows immediately by choosing α = \sqrt{2p − 1}, as long as s is chosen large enough for s(2p − 1)^{\frac{s}{2}} < 1. □

4.2 How to decommit

The above theorem shows that an honest S does not reveal much about her secret bit b by sending the matrix B through the quantum channel. But now, for this to be a commitment to b, it should be possible for S to convince R of what bit she has just committed to. She should not be able to convince him of the contrary (that she committed to b̄).

To open her commitment, S initiates the following protocol with R.

Protocol 4.2 ( BC-decommit((B, Φ, b), (B′, Θ)) )

1: S reveals b, B and Φ to R

2: DO_{i=1}^{s} R checks that ⨁_{j=1}^{s} b_{i,j} = b

3: DO_{i=1}^{s}DO_{j=1}^{s} R checks that b′_{i,j} = b_{i,j} whenever φ_{i,j} = φ_{i,j}

4: if this condition is satisfied for all i and j, then R outputs “accept” else R outputs “reject”

If s is chosen large enough, when S tries to change b to b̄, she will create errors in the revealed

matrix with high probability. Let b_{i} = ⨁_{j=1}^{s} b_{i,j} and define b′_{i} similarly. It is extremely unlikely that

S finds two pairs of matrices B^{0}, Φ^{0} and B^{1}, Φ^{1} such that each of the b_{i}^{0}’s is 0, while each of the b_{i}^{1}’s is 1 and such that

∀i, j[(φ_{i,j}^{0} = φ_{i,j}) ⇒ (b_{i,j}^{0} = b′_{i,j}) and (φ_{i,j}^{1} = φ_{i,j}) ⇒ (b_{i,j}^{1} = b′_{i,j})]

Theorem 4.3 The probability that S finds two pairs of matrices B^{0}, Φ^{0} and B^{1}, Φ^{1} that could be both accepted by R is at most α^{s} for some α < 1.

Proof.

Let B̃ be the best approximation to B′ that S can get. When both S and R are honest, B̃ = B and S knows that Prob(b_{i,j} = b′_{i,j}) = \frac{3}{4}. To increase her knowledge of B′, S can cheat and send B̃ by using some angles φ̃_{i,j} that are not 0^{∘} or 45^{∘}. When only R is honest, the maximum information that S may get about each b′_{i,j} is by sending her bits b̃_{i,j} using angle 22\frac{1}{2}^{∘} + b̃_{i,j} × 90^{∘}, which gives her Prob(b̃_{i,j} = b′_{i,j}) = cos^{2}(22\frac{1}{2}^{∘}). Still, S will always have a probability of sin^{2}(22\frac{1}{2}^{∘}) of guessing b′_{i,j} incorrectly.

Whichever way B̃ is chosen, we get that at least one of B^{0} or B^{1} must have \frac{s}{2} lines that do not match with B̃. This is true because B^{0} and B^{1} have s lines that do not match. Assume without lost of generality that B^{0} has at least as many lines not matching B̃ as B^{1}.

Each time S changes a bit b̃_{i,j} to its complement in order to claim B^{0} instead of B̃ she has probability \frac{1}{2} of revealing an angle φ_{i,j}^{0} = φ_{i,j} in which case she has at least probability sin^{2}(22\frac{1}{2}^{∘}) that

b_{i,j}^{0} ≠ b′_{i,j}. Therefore for each bit changed, S will create an error with probability at least \frac{sin^{2}(22 \frac{1}{2}^{∘})}{2}.

Her probability of creating no error when revealing B^{0} is therefore at most (\sqrt{1 − \frac{sin^{2}(22 \frac{1}{2}^{∘})}{2}})^{s}.

From this we conclude that S may succeed in opening B in both ways with probability at most α^{s} for some α < 1. □

Notice, however, that even a few transmission errors will lead R to believe that S is cheating and thus to reject her commitments even when she is honest. The solution to this problem is not at all addressed in the current paper and will be the topic of another paper dealing with transmission errors in quantum protocols. That paper is currently in preparation with Charles Bennett [BBC90].

Finally, we have Theorem 4.4 This protocol cannot be broken using E-P-R. Proof.

Provided in the journal version of the paper. □

4.3 Can this new scheme be broken?

One thing not ruled out by quantum mechanics is the possibility of evaluating predicates on several photons at once. Such a possibility is known to the world of quantum mechanics as coherent measurements. For instance, there are functions f such that given two photons of polarization φ_{1} and φ_{2}, there might exist a way to find out more about f(φ_{1}, φ_{2}) than what can be obtained by applying f to what can be measured about φ_{1} and φ_{2} separately.

Such a possibility could make the commitment scheme described above totally insecure if the ⊕ of the values carried by many photons could be evaluated at once. The value of b could be

recovered easily using equation 2: ⨁_{j=1}^{s} b_{i,j} = b and taking majority on the rows.

Actually this possibility is, as far as the authors know, the only possible way to cheat our protocol. Fortunately, not only is no technology available to do coherent measurements, but also physicists do not even know how to get photons to interact in ways that could lead to such a measurement. Therefore, although such a possibility exists in theory, in practice there should be very little concern that the protocol be broken this way.

5 Have we won anything?

As it turns out, having two different schemes is better than one: One can build a Coin Tossing Protocol that can be broken only if one can implement both the E-P-R attack and coherent measurements. Consider the following protocol:

Protocol 5.1 ( BC-cointoss )

1: S chooses a random bit b_{0} and uses BB-commit(b_{0}) with R

2: R chooses a random bit b_{1} and uses BC-commit(b_{1}) with S (the roles of R and S are temporarily interchanged)

3: S runs BB-decommit(b_{0}) with R

4: R runs BC-decommit(b_{1}) with S

5: R wins the coin toss if and only if b_{1} = b_{0}

This protocol can be broken only if S can implement the E-P-R attack as well as the coherent measurement attack. R has no way to cheat whatsoever, unless he can design an apparatus that can transmit information faster than the speed of light. The proof of these claims will be provided in the journal version of the paper.

6 Conclusion

In the light of ongoing progress in physics, it is reasonable to fear that the E-P-R attack on the bit commitment scheme (or coin flipping protocol) of [BB84] could be implemented. The commitment scheme we have presented in this paper does not yield to this attack. Unfortunately, we can still describe a possible attack on this new scheme, which is based on an unverified belief about quantum mechanics (unlike E-P-R, which has been verified experimentally). Can one build such a scheme, unbreakable in an absolute way, based solely on the equations of quantum mechanics? We cannot answer this question at this time.

Still we have been able to build a coin-tossing protocol that is secure unless both attacks can be implemented. This seems to indicate that maybe Bit Commitment is more than Coin-Tossing since, at this time, we are unable to offer a Bit Commitment scheme with this same level of security.

7 Acknowledgements

We wish to thank Charles H. Bennett and Joe Kilian for suggestions and comments on this work. Claude would especially like to thank Silvio Micali for the collossal work he contributed while writing and polishing this text which first appeared in part in Claude’s Ph.D. thesis.

References

[BBBSS90] Bennett, C. H., F. Bessette, G. Brassard, L. Salvail, and J. Smolin, “Experimental quantum cryptography”, Advances in Cryptology: Proceedings of Eurocrypt ’90, Aarhus, Denmark, Springer–Verlag, to appear, 1990.

[BB84] Bennett, C. H. and G. Brassard, “Quantum cryptography: public key distribution and coin tossing”, Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, pp. 175–179, 1984.

[BBC90] Bennett, C. H., G. Brassard, and C. Crépeau, “Practical Quantum Oblivious Transfer”, in preparation.

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

[Blu81] Blum, M., “Three applications of the oblivious transfer: Part I: Coin flipping by telephone; Part II: How to exchange secrets; Part III: How to send certified electronic mail”, Technical Report, Department of EECS, University of California, Berkeley, CA, 1981.

[EGL83] Even, S., O. Goldreich, and A. Lempel. “A randomized protocol for signing contracts”, In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proceedings CRYPTO 82, pages 205–210, New York, 1983. Plenum Press.

[GMW86] Goldreich, O., S. Micali, and A. Wigderson, “Proofs that yield nothing but their validity and a methodology of cryptographic protocol design”, Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 174–187, Toronto, 1986.

[Wie83] Wiesner, S., “Conjugate coding”, Sigact News, Vol. 15, no. 1, pp. 78–88, 1983. manuscript written circa 1970, unpublished until it appeared in Sigact News.