Unconditionally secure quantum bit commitment is impossible

Dominic Mayers

Département IRO, Université de Montréal

C.P. 6128, succursale Centre-Ville,Montréal (Québec), Canada H3C 3J7. (December 5, 1996)

The claim of quantum cryptography has always been that it can provide protocols that are unconditionally secure, that is, for which the security does not depend on any restriction on the time, space or technology available to the cheaters. We show that this claim does not hold for any quantum bit commitment protocol. Since many cryptographic tasks use bit commitment as a basic primitive, this results implies a severe setback for quantum cryptography. We claim that the model used encompasses all reasonable implementations of quantum bit commitment protocols in which the participants have not met before, including those that make use of the theory of special relativity.

a. Introduction Quantum cryptography is often associated with a task called key distribution and it has obtained a lot of success in this area. However, quantum cryptographers have also proposed quantum protocols for other tasks and bit commitment is a basic primitive that has been used in most if not all of these other proposals. For a review on quantum key distribution and on quantum cryptography in general see [5]. Here, we focus on bit commitment.

We introduce bit commitment in terms of quantum states which is not standard in cryptography but is appropriate for our purposes. A bit commitment state is a random state |ψ_{b}⟩ ∈_{R} {|ψ_{0}⟩, |ψ_{1}⟩} of a system H_{A} × H_{B} × H_{E} such that the two following conditions hold. First, a party usually called Bob having access to H_{B} only should not be able to obtain any information at all about the bit b. We say that a bit commitment state must be concealing. Second, another participant usually called Alice having only access to H_{A} can unveil the bit b to Bob, but she should not be able to change her mind about the value of the bit b. We say that a bit commitment state must be binding. Note that this definition encompasses the classical notion of bit commitment. The system H_{E} stands for the environment and his necessary to include the notion of classical bits, mixtures, etc. in the picture.

Many cryptographic applications such as the zero knowledge proofs are based on bit commitment. In a zero knowledge proof, Alice wants to convince Bob that she knows at the least one element x in a fixed set L which is known by both participants. For instance, L could be the set of all possible proofs for a given theorem. The difficulty is that Alice wants to convince Bob that she knows x without unveiling any information or almost any information about it. This amazing task has been shown to be possible on top of bit commitment for a large class of sets L.

Also, the work of Kilian and many others [14,10,7,9] has shown that any multi-party computation can be built on top of oblivious transfer [4,8] which can itself be executed by a quantum protocol on top of bit commitment [19,16]. An example of multi-party computation is the millionaire’s problem. In this task, two millionaires want to find out who is the richest, but they do not want to unveil any additional information about their respective fortune.

All the known protocols that attempt to realize this kind of tasks via exchange of classical informations only are based upon a restriction on the amount of time available to the cheater. This is what we call computational security. Furthermore, on top of it, they are all based on some unproven computational assumptions such as the assumption that no algorithm can factorize a large number in a reasonable number of steps.

In quantum cryptography, we want to realize this kind of tasks even against a cheater that has unlimited computational power! This means that there should be no restriction on the amount of time, on the amount of space or on the technology available to the cheater. A protocol that works even against such a powerful cheater is said to be unconditionally secure.

A quantum protocol has been proposed in 1993 to realize bit commitment [6], and the unconditional security of this protocol has been generally accepted for around two or three years. At this time, much optimisism prevailed. Then, Salvail get interested in the design of possibly more efficient quantum bit commitment protocols [17]. In all these protocols, Alice sent a mixture to Bob to commit a bit b. The mixture was different when b = 0 than when b = 1, but to make sure that these protocols were secure against Bob, these two mixtures had a same density matrix. However, it was noticed that in these protocols Alice could change her mind via a transformation on her side only. This problem has been presented to Wootters and he made the point that it was the immediate consequence of a general theorem [12] which says that because the two density matrices are identical, Alice can change her mind via a transformation on her side. The connection with the BCJL protocol was made later in the fall of 1995. After the discovery that BCJL was insecure, researchers have tried to find alternative protocols. Some of them were based on the theory of special relativity. For additional historical information see [5]. See also [15].

Here, it is shown that, if no component in the protocol can be simultaneously trusted by both participants, an unconditionally secure bit commitment protocol is impossible. It is assumed that the protocol begins in some standard initial state, but the proof can be easily extended to any initial state where Alice’s system and Bob’s system are not entangled. We claim that the model used encompasses all reasonable protocols, including those based on the theory of special relativity.

b. The model In our model, every quantum bit commitment protocol is described in terms of quantum registers that are acted upon by quantum gates [1]. At every step, every register is an input for one and only one gate, possibly a gate that executes the identity transformation.

For simplicity, we assume that all quantum registers are two dimensional quantum systems. This is not really a restriction on the set of protocols because higher dimensional systems can be simulated via two dimensional registers [1].

If one needs a random classical bit in this model, one must transform a quantum register which is initially in a state |ϕ⟩ = α|0⟩ + β|1⟩ into a mixture. So, one introduces another register in the state |0⟩^{(E)} and executes a controlled-not (|y⟩^{(E)}|x⟩ ↦ |y ⊕ x⟩^{(E)}|x⟩) and throws the additional register away in an area called the environment. The environment has the property that any register that is thrown away in this area is lost for ever. The resulting state α|0⟩^{(E)}|0⟩ + β|1⟩^{(E)}|1⟩ corresponds to a random classical bit with probability distribution p_{0} = |α|^{2} and p_{1} = |β|^{2}.

If we assume that the cheater is so powerful that he can reverse any process that may occur when a quantum register interacts with a real environment, then it may be that there exists no area in which quantum registers are lost for ever. However, we need an area of this kind to include classical bits and the classical world in general in our model.

Communication is made by exchange of quantum registers in a deterministic manner. In our model, a register cannot be in a superposition of being sent and not being sent. Intuitively, we claim that there is no loss of generality because the same physical processes can be expressed in terms of a register that is systematically sent, but is in a surperposition of containing the information or not. Similarly, a participant cannot choose at random whether or not he will send a register.

c. The BB84 quantum bit commitment protocol It is well known that no protocol can allow the creation of a bit commitment state via exchange of classical information between Alice and Bob only. This is true even if the participants are honest and have the best will in the world. So, it is of interest that a two-party quantum protocol has been proposed in 1984 that realizes bit commitment when the participants are honest [2]. The protocol fails when Alice cheats. In fact, the authors themselves have first explained their protocol together with an attack.

The BB84 bit commitment protocol makes use of the BB84 coding scheme. In this scheme, every bit is coded either in a so called rectilinear basis ( |0⟩_{+}, |1⟩_{+} ) or in the diagonal basis ( |0⟩_{×}, |1⟩_{×}), where |0⟩_{×} = 1/\sqrt{2}(|0⟩_{+} + |1⟩_{+}) and |1⟩_{×} = 1/\sqrt{2}(|0⟩_{+} − |1⟩_{+}).

In this protocol, Alice creates a string of random bits w = w_{1} … w_{n}. Then she codes each bit w_{i} using the BB84 coding scheme. She always uses the rectilinear basis θ = + if she wants to commit a 0 and the diagonal basis θ = × if she wants to commit a 1. She sends these registers to Bob. Then, Bob chooses a string of random bases θ̂ = θ̂_{1} … θ̂_{n} ∈ {+, ×}^{n}, measures the register i in the basis θ̂_{i} and notes the outcomes ŵ_{i}. To unveil the bit b, Alice has simply to announce the string w. Bob can figure out what is b by looking at positions i where w_{i} ≠ ŵ_{i}: at each of these positions it must be that θ ≠ θ̂_{i}. Before the opening, the bit commitment state is concealing because both b = 0 and b = 1 correspond to the same fully mixed density matrix on Bob’s side. Also, it is binding because to change her mind Alice would have to guess what are the bits obtained by Bob when θ̂_{i} ≠ θ. These bits are perfectly random. She could guess what these bits are, but she would only succeed with a very small probability. This is fine: unconditional security does not mean a perfect protocol. As explained previously, it only means that the protocol should do what it claims to do against a cheater that has unlimited computational power.

Now, in our model, this protocol will look slightly more complicated because each random bit must be created using two quantum registers. Here is the state that Alice must create for each i:

1/\sqrt{2}(|0⟩_{θ}^{(E)}|0⟩_{θ}^{(A)}|0⟩_{θ}^{(B)} + |1⟩_{θ}^{(E)}|1⟩_{θ}^{(A)} |1⟩_{θ}^{(B)}).

The first register to the left is the one that she throws away in the environment, the second corresponds to the random classical bit that she keeps on her side and the third one is the register that she sends to Bob. For simplicity, we have assumed that the basis θ is not only used to encode the random classical bit in the third register which is sent to Bob, but also to compute it in the first two registers which Alice keeps on her side.

d. The attack against the BB84 bit commitment A dishonest Alice executes the honest commit algorithm for b = 0, except that she never throws anything away in the environment. In other words, she creates the state:

1/\sqrt{2}(|0⟩_{+}^{(A)}|0⟩_{+}^{(A)}|0⟩_{+}^{(B)} + |1⟩_{+}^{(A)}|1⟩_{+}^{(A)} |1⟩_{+}^{(B)}).

This is cheating because there exists a unitary transformation that Alice can execute on her side that will transform this state into the state:

1/\sqrt{2}(|0⟩_{×}^{(A)}|0⟩_{×}^{(A)}|0⟩_{×}^{(B)} + |1⟩_{×}^{(A)}|1⟩_{×}^{(A)} |1⟩_{×}^{(B)}),

which is exactly the state that she would have created with a 1 in mind. The transformation is simple. She simply executes a controlled-not on the first two photons using the rectilinear basis, and then another controllednot on the same photons but, this time, using the diagonal basis.

e. The main result To obtain the impossibility of bit commitment we need to make some assumptions about the initial state. Otherwise, in the extreme case, the initial state could be a bit commitment state. We claim that all protocols that start in a product state of Alice’s system and Bob’s system are insecure. However, for simplicity we deal only with protocols where initially all quantum registers are set to |0⟩ and the environment is empty. We prove that no quantum bit commitment protocol that starts in this state is unconditionally secure, unless one or more gates can be trusted by both participants simultaneously. A gate or a set of gates trusted by both participants is called a trusted party. We do not accept trusted party in our proof.

We can assume that the protocol is unconditionally secure against Bob, because otherwise the proof is done. As suggested by the BB84 example, the main idea of Alice’s strategy is to execute the honest algorithm with the bit b of her choice, but never to throw anything away in the environment except when she must send a classical bit x to Bob. When Alice sends a classical bit x to Bob, we have a term of the form |x⟩^{(E)}|x⟩^{(A)}|x⟩^{(B)} which can be factorized out. Similarly, one can factorize the terms that are associated with the classical bits that Bob sends to Alice. Let ξ represents all these terms associated with classical bits which are shared between Alice and Bob. At the end of the commit phase, for a given ξ, the state of the overall system has collapsed into a state |ξ⟩|ψ_{b}⟩. In the remainder of this letter, we do not consider the registers which have been factorized out as a part of the overall quantum system that remains after the commit phase. Also, the state |ψ_{b}⟩ depends on ξ, but we have suppressed this dependence in the notation. Note that, once we have factorized out |ξ⟩, there is nothing in the environment on Alice’s side. So, on her side of the quantum system, Alice is free to execute the transformation of her choice. However, because Bob is honest, he might have thrown some registers away in the environment on his side.

Now we must argue that the two density matrices ρ_{B}(|ψ_{0}⟩) and ρ_{B}(|ψ_{1}⟩) on Bob’s side, associated with b = 0 and b = 1 respectively, are identical or almost identical. We would like to use the fact that Bob can cheat using the same strategy that has been used by Alice. However, the rule of the game to attack a protocol in cryptography is that Alice and Bob cannot cheat at the same time. Fortunately, the overall algorithm that is executed when Alice does not cheat and Bob does cheat is exactly the same as when Alice cheats and Bob does not cheat. Therefore, the density matrices ρ_{B}(|ψ_{0}⟩) and ρ_{B}(|ψ_{1}⟩) are the same in both cases. So, we can use the fact that Bob cannot obtain much information when he cheats, to conclude that the density matrices must be identical or almost identical when he does not cheat. For simplicity, we first deal with the case where the density matrices are identical.

In this case, Alice can change her mind about the value of b because the work of Hughson, Jozsa and Wootters [12] implies that if

ρ_{B}(|ψ_{0}⟩) = ρ_{B}(|ψ_{1}⟩) =^{def} ρ_{B}

on Bob’s side, then there exists a unitary transformation on Alice’s side which maps |ψ_{0}⟩ into |ψ_{1}⟩. We give the proof of this theorem. Consider the respective Schmidt decomposition [12,18] of |ψ_{0}⟩ and |ψ_{1}⟩ given by

|ψ_{0}⟩ = ∑_{i} \sqrt{λ_{i}}|e_{i}^{(0)}⟩ ⊗ |f_{i}⟩
|ψ_{1}⟩ = ∑_{i} \sqrt{λ_{i}}|e_{i}^{(1)}⟩ ⊗ |f_{i}⟩.

In the above formula, λ_{i} are eigenvalues of the three density matrices ρ_{B}, ρ_{A}(|ψ_{0}⟩) and ρ_{A}(|ψ_{1}⟩). The fact that these three density matrices share the same positive eigenvalues with the same multiplicity is part of the Schmidt decomposition theorem [12,18]. The states |e_{i}^{(b)}⟩ and |f_{i}⟩ are respectively eigenstates of ρ_{A}(|ψ_{b}⟩) and ρ_{B} associated with the same eigenvalue λ_{i}. The coefficients \sqrt{λ_{i}} are real numbers, but any phase can be included in the choice of |e_{i}^{(b)}⟩. Clearly, the same unitary transformation that maps |e_{i}^{(0)}⟩ into |e_{i}^{(1)}⟩ also maps |ψ_{0}⟩ into |ψ_{1}⟩. The cheater can compute the states e_{i}^{(b)} and thus this unitary transformation with an arbitrary level of precision. This concludes the proof.

f. The non ideal case In the ideal case, the cheater could transform |ψ_{0}⟩ into |ψ_{1}⟩ because the two density matrices ρ_{B}(|ψ_{0}⟩) and ρ_{B}(|ψ_{1}⟩) were identical. This was sufficient to conclude that the protocol is insecure. Now, we must use the fact that the distinguishability D between these two density matrices must be small, to obtain that the cheater can transform |ψ_{0}⟩ into a state |ψ_{01}⟩ which is very close to |ψ_{1}⟩. This is exactly what a theorem of Uhlmann says. Any state |ψ_{01}⟩ of the overall system such that ρ_{B}(|ψ_{01}⟩) = ρ_{B}(|ψ_{0}⟩) is called a purification of the density matrix ρ_{B}(|ψ_{0}⟩). Uhlmann’s theorem [13] says that there exists a purification |ψ_{01}⟩ of ρ_{B}(|ψ_{0}⟩) such that

⟨ψ_{01}|ψ_{1}⟩ ≥ 1 − D.  (1)

The fact that |ψ_{01}⟩ is a purification of ρ_{B}(|ψ_{0}⟩) implies that Alice can transform |ψ_{0}⟩ into |ψ_{01}⟩ as in the ideal case. Inequality 1 says that |ψ_{01}⟩ is close to |ψ_{1}⟩. This result is sufficient to conclude that the protocol is insecure against Alice.

However, it is also useful to express the result in other terms. In [11], our result is translated in a language that do not involve quantum mechanics. More precisely, Bob’s information about the bit b is measured in terms of the probability p_{E} that the best guess that Bob can make about the bit b turns out to be wrong. One must also take into account the probability p_{H} that the bit b is accepted by Bob when Alice is honest. Normally, p_{H} should be 1 or very close to 1 and p_{E} should be \frac{1}{2} or very close to \frac{1}{2}. A lower bound on the probability p_{C} with which Alice can successfully change her mind must be given in terms of p_{E} and p_{H}. The result of [11] is

p_{C} > p_{H} − 4\sqrt{|p_{E} − \frac{1}{2}|}.

g. Generality of the result One could think that, if we could constraint the cheater to do what is requested by the protocol, then we would have a secure protocol. However, the problem is that in our attack the cheater does what is requested by the protocol, except that he does not throw anything away unless it is expected by the other. Therefore, no verification whatsoever can be used to detect such a cheater. In particular, any verfication based on the theory of special relativity is useless.

The above argument make sense in our model, but is our model really general? We claim that it is, but it is not possible to rigorously prove this kind of statements because there will always be some arbitrariness in the concept of protocols itself. An issue that needs to be discussed is the concept of communication via a deterministic exchange of registers. This issue has already been briefly discussed when we have introduced the model. Another issue is the impact of the superselection rules in quantum mechanics.

h. Conclusions Because we have shown that bit commitment is impossible, we can only hope to realize cryptographic tasks which are not known to be powerful enough to obtain bit commitment. For instance, coin tossing and most multi-party computations are possible candidates because it is not known how to build bit commitment on top of them. However, some tasks might not be powerful enough to obtain bit commitment and yet be impossible. What are the fundamental principles that make some tasks possible and other tasks impossible? One could think that all the tasks which involve only two parties are impossible. This would explain why quantum key distribution is possible and bit commitment impossible. However, there might be other principles involved. For instance, in bit commitment an asymmetry is created. It could be that only the asymmetrical tasks are impossible. In this case, coin tossing would be possible. What tasks are possible is a fundamental question which yet remain to be answered.

i. Acknowledgments I acknowledge fruitful discussions with Lior Goldenberg, Jeroen van de Graaf, Tal Mor, Lev Vaidman, and William Wootters.

[1] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter, PRA, Volume 52, Issue 5 - November 1995, pp. 3457-3467.

[2] Charles H. Bennett and Gilles Brassard, Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, December 1984, pp. 175 – 179.

[3] C.H. Bennett, F. Bessette, G. Brassard, L. Salvail and J. Smolin, Journal of Cryptology, vol. 5, no. 1, 1992, pp. 3 – 28.

[4] Charles H. Bennett and Gilles Brassard, Claude Crépeau, Marie-Hélène Skubiszewska, Proceedings of CRYPTO’91, vol. 576, Springer – Verlag, Berlin, 1992, pp. 351 – 366.

[5] G. Brassard, Sigact News, Vol. 27, no. 3, September 1996, pp. 13-24.

[6] Gilles Brassard, Claude Crépeau, Richard Jozsa, Denis Langlois, in Proceeding of the 34th annual IEEE Symposium on foundations of Computer Science, November 1993, pp. 362 – 371.

[7] D. Chaum, I. B. Damgård and J. van de Graaf, Advances in Cryptology – Crypto’87 Proceedings, august 1987, Springer – Verlag, pp. 87 – 119.

[8] Claude Crépeau Journal of Modern Optics, vol. 41, no. 12, December 1994, pp. 2445 – 2454.

[9] Claude Crépeau, Jeroen van de Graaf, Alain Tapp, Advances in Cryptology: Proceeding of Crypto ’95, Vol 963, Springer – Verlag, Berlin, 1995, pp. 110 – 123.

[10] O. Goldreich, S. Micali and A. Wigderson, Proceedings of 19th ACM Symposium on Theory of Computing, may 1987, pp. 218 – 229.

[11] ..., D. Mayers,..., “Title to be determined” Submitted to Journal of Cryptology.

[12] L. P. Hughston, Richard Jozsa and William K. Wootters, Physics Letters A, vol. 183, pp. 14 – 18, 1993.

[13] Richard Jozsa, Fidelity for mixed quantum states, Journal of Modern Optics, vol. 41, no. 12, pp. 2315 – 2323, 1994.

[14] Joe Kilian, Proceedings of the 20th symposium on Theory of Computing, may 1988, pp. 20 – 31.

[15] H-K. Lo and H. F.Chau, Is quantum bit commitment really possible?, Los Alamos preprint archive

                                                            quant-ph/9603004, March 1996.

[16] D. Mayers, “Quantum key distribution and string oblivious transfer on noisy channels”, Advances in Cryptology: Proceeding of Crypto’96, août 1996, Springer – Verlag, pp. 343 – 357.

[17] L. Salvail, personal communication.

[18] E. Schmidt, Math. Ann. 63 (1906) 433.

[19] Andrew Yao, In Proceedings of the 26th Symposium on the Theory of Computing, June 1995; pp. 67 – 75.