Next: Aftermath Up: Heads or Tails? Quantum Previous: Brassard, Crépeau, Jozsa, Langlois:

# The Quantum Computer bites the Quantum Cryptographer

Three years passed before Lo and Chau, and Mayers discovered the flaws of BCJL93, more or less simultaneously. The advances in quantum computing theory provided them with better formalisms on quantum physics and quantum computations and allowed them to frame the problem with a clearer perspective. Their papers were first published online ([16], [11]) and later appeared together on Physical Review Letters ([17], [12]). To prove that quantum bit commitment is impossible, a general structure or scheme of a QBC protocol is needed, encompassing all possible such protocols. The authors at the time had doubts on the generality of the ones they had used. Lo and Chau's 1998 article [13] and review [7] have definitively settled the issue.6

The general idea of a protocol involves three quantum systems, one for Alice, one for Bob, and one for a communications channel. According to quantum physics, the state of each one of these is a unitary7 vector on a Hilbert8 space, so we must consider state spaces HA, HB, and HCfor each of this characters. The complete state of all of them put together is a vector in the direct (tensor) product of the three, namely the space . Note that in as much as quantum physics encompasses classical physics, this is also a description for any classical (or mixed) protocol. The protocol will require A and B to prepare and manipulate their states, which involves computing and storage. Once again, from the point of view of quantum physics, the most general description of these are quantum computers. The assumption is, then, that A and B have a quantum computer each. With this gadgets they are able to perform manipulations on their state-spaces, namely, to rotate the state by any unitary transformation9.

• LC98 general Quantum Bit Commitment protocol
1.
Preparation of states.

(a)
Alice chooses b. She sets HA to one of two states specified by the protocol. Call them and . Thus Alice sets HA to which is either or .
(b)
Bob sets the initial states of both the communications channel and his side of the protocol. These initial states will be called and , respectively. So is set to state = .
(c)
, and are all specified by the protocol and known to both parties.
2.
Commitment.

(a)
Here Alice and Bob execute a commitment protocol. Each one of them, in turn, perform a unitary transformation involving their side and the communications channel. So Alice sees'' whereas Bob acts on . Each of these operations, of course, result in a unitary transformation of the whole state .
If we label this transformations UA1, UB1, ... ,UAn, UBn we conclude that the final state is10

3.
Disclosure

(a)
Alice sends Bob all her quantum particles and Bob takes a measurement on the composite system which convinces him of what the commitment was.

After the commitment phase, the entire system is in one of two states: Either the state originating from an initial b=0, which will be called or the one generated from b=1, namely, . Since all the protocol is known to both parties, they both know the entire matrix U of the whole computation process, the only difference being that Bignores what the initial state of HA was.

The key element at this point is that B must get no information whatsoever on what the value of b is. So both states and must look identical from his point of view. This said in mathematical terms, the trace with respect to HAof the observable associated with is identical to that of . We do this with a tool called Schmidt decomposition[7]: there are bases of HAand of HBC , and numbers such that

and the trace taken to bring the observable down to HBC yields11

Similarly, there are bases of HA and of HBC, and scalars such that

and

But since B cannot tell between each other, it must be the case that for all i, and . The only difference between the states lies inside HA which means now that A can manipulate it at will! This is the problem that ruins the whole setup. Alice does not need to have access to HBC in order to cheat. Here's what she should do:

• Alice cheats with a quantum computer
1.
Prepare as if she were committing to the bit 0.
2.
Go over the protocol with B.
3.
When the time comes to open the commitment, if she wishes it to be zero, does nothing. Otherwise uses her quantum computer to apply the basis change operator on HA. Now when B does his measurement, the state is and he is convinced that Alice was committed to 1 all along.
Perhaps all this quantum mathematical symbols were not even necessary. Suffice to say that, according to quantum mechanics, and according to Mayers, Lo and Chau, the two requirements for a bit commitment, which are that Bob cannot get early information, and that Alice can't cheat, are mutually exclusive because both committed'' states must be identical from Bob's point of view, so if Alice has the means, such as quantum storage and quantum computers, she can modify things up to the last minute.

Next: Aftermath Up: Heads or Tails? Quantum Previous: Brassard, Crépeau, Jozsa, Langlois:

1999-11-04