8.3. Quantum Cryptography

We now describe the quantum key-exchange algorithm due to Bennett and Brassard. The original paper also talks about a practical implementation of the algorithm—an implementation using polarization of photons. For this moment, we do not highlight such specific implementation issues, but describe the algorithm in terms of the conceptual computational units called qubits.

The usual actors Alice and Bob want to agree upon a shared secret using communication over an insecure channel. A third party who gave her name as Carol plans to eavesdrop during the transmission. Alice and Bob repeat the following steps. Here, H stands for the Hadamard transform.

Algorithm 8.1. Quantum key-exchange algorithm

The algorithm works as follows. Alice generates a random bit i and a random decision x whether she is going to use the Hadamard transform H. If x = 0, she sends the quantum bit |0〉 or |1〉 to Bob. If x = 1, she sends either or to Bob. At this point Bob does not know whether Alice applied H before the transmission. So Bob makes a random guess and accordingly skips/applies the Hadamard transform on the qubit received. If x = y = 0, then Bob has the qubit B = H⁰H⁰|i〉 = |i〉 and a measurement of this qubit reveals i with probability 1. On the other hand, if x = y = 1, then B = H²|i〉 = |i〉, since H² is the identity transform (Exercise 8.5). In this case also, Bob retrieves Alice’s classical bit i with certainty by measuring B.

If x ≠ y, then B is generated from Alice’s initial choice |i〉 using a single application of H, that is, in this case. A measurement of this bit outputs 0 or 1, each with probability , that is, Bob gathers no idea about the initial choice of Alice. So after it is established that x ≠ y, they both discard the bit.

If we assume that x and y are uniformly chosen, Bob and Alice succeed in having x = y about half of the time. They eventually set up an n-bit secret after about 2n invocations of the above protocol. Table 8.1 illustrates a sample session between Alice and Bob. After 20 iterations of the above procedure, they agree upon the shared secret 0001110111.

Table 8.1. A sample session of the quantum key-exchange algorithm

Iteration	i	x	A	y	B	j	Common bit
1	0	1		0		1
2	0	0	|0〉	1		1
3	0	1		1	|0〉	0	0
4	0	1		0		0
5	1	1		0		1
6	0	0	|0〉	0	|0〉	0	0
7	0	0	|0〉	0	|0〉	0	0
8	1	0	|1〉	0	|1〉	1	1
9	0	0	|0〉	1		0
10	1	1		0		0
11	0	1		0		1
12	0	0	|0〉	1		0
13	1	0	|1〉	1		1
14	1	1		1	|1〉	1	1
15	1	1		1	|1〉	1	1
16	0	1		1	|0〉	0	0
17	1	1		1	|1〉	1	1
18	1	0	|1〉	0	|1〉	1	1
19	0	1		0		0
20	1	0	|1〉	0	|1〉	1	1

What remains to explain is how this protocol guards against eavesdropping by Carol. Let us model Carol as a passive adversary who intercepts the qubit A transmitted by Alice, investigates the bit to learn about Alice’s secret i and subsequently transmits the qubit to Bob. In order to guess i, Carol mimics the role of Bob. At this point Carol does not know x, so she makes a guess z about x, accordingly skips/applies the Hadamard transform on the intercepted qubit in order to get a qubit C, measures C to get a bit value k and sends the measured qubit D to Bob. (Recall from Theorem 8.1 that it is impossible for Carol to make a copy of A, work on this copy and transmit the original qubit A to Bob.) Bob receives D, assumes that it is the qubit A transmitted by Alice and carries out his part of the work to generate the bit j. Bob and Alice later reveal x and y. If x ≠ y, they anyway reject the bits obtained from this iteration. Carol should also reject her bit k in this case. So let us concentrate only on the case that x = y. The introduction of Carol in the protocol changes A to D and hence Alice and Bob may eventually agree upon distinct bits. A sample session of the protocol in presence of Carol is illustrated in Table 8.2. The three parties generate the secret as:

Table 8.2. Eavesdropping during a key-exchange session

Iteration	i	x	A	z	C = HzA	k	D	y	B = HyD	j
1	0	1		1	|0〉	0	|0〉	1		0
2	1	0	|1〉	0	|1〉	1	|1〉	0	|1〉	1
3	1	0	|1〉	1		0	|0〉	0	|0〉	0
4	0	1		0		0	|0〉	1		1
5	0	1		1	|0〉	0	|0〉	1		1
6	1	1		1	|1〉	1	|1〉	1		1
7	1	1		0		0	|0〉	1		0
8	1	0	|1〉	0	|1〉	1	|1〉	0	|1〉	1
9	1	1		0		0	|0〉	1		1
10	0	1		0		1	|1〉	1		1
11	0	0	|0〉	1		0	|0〉	0	|0〉	0
12	0	0	|0〉	0	|0〉	0	|0〉	0	|0〉	0
13	1	1		1	|1〉	1	|1〉	1		1
14	0	0	|0〉	0	|0〉	0	|0〉	0	|0〉	0
15	1	0	|1〉	0	|1〉	1	|1〉	0	|1〉	1
16	1	0	|1〉	1		1	|1〉	0	|1〉	1

In this example, Alice and Bob’s shared secrets differ in five bit positions. Carol’s intervention causes a shared bit to differ with a probability of (Exercise 8.11). Thus, the more Carol eavesdrops, the more she introduces different bits in the secret shared by Alice and Bob.

Once Alice and Bob generate a shared secret of the desired bit length, they can check for the equality of their secret values without revealing them. For example, if the shared secret is a 64-bit DES key, Alice can send Bob one or more plaintext–ciphertext pairs generated by the DES algorithm using her shared key. Bob also generates the ciphertexts on Alice’s plaintexts using his secret key. If the ciphertexts generated by Bob differ from those generated by Alice, Bob becomes confident that their shared secrets are different and this happened because of the presence of some adversary (or because of communication errors). They then repeat the key-exchange protocol.

Another possible way in which Alice and Bob can gain confidence about the equality of their shared secrets is the use of parity checks. Suppose Alice breaks up her secret in blocks of eight bits and for each block computes the parity bit and sends these bits to Bob. Bob generates the parity bits on the blocks of his secret and compares the two sets of parity bits. If the shared secrets of Alice and Bob differ, it is revealed by this parity check with high probability.

A minor variant of the key-exchange algorithm just described comes with an implementation strategy. The polarization of a photon is measured by an angle θ, 0° ≤ θ < 180°.^[1] A photon polarized at an angle θ passes through a φ-filter with the probability cos²(φ – θ) and gets absorbed in the filter with the probability sin²(φ – θ). Therefore, a photon polarized at the angles 0°, 90°, 45°, 135° can be used to represent the quantum states |0〉, |1〉, , respectively. Alice and Bob use 0°- and 45°-filters. Alice makes a random choice (x) among the two filters. If x = 0, she sends a photon polarized at an angle 0° or 90°. If x = 1, a photon polarized at an angle 45° or 135° is sent. When Bob receives the photon transmitted by Alice, he makes a random guess y. If y = 0, he uses the 0°-filter to detect its polarization, and if y = 1, he uses the 45°-filter to detect its polarization. Then, Alice and Bob reveal their choices x and y and if the two choices agree, they share a common secret bit. See Exercise 8.12 for a mathematical formulation of this strategy.

^[1] Ask a physicist!

One of the most startling features of this Bennett–Brassard algorithm (often called the BB84 algorithm) is that there has been successful experimental implementations of the strategy. The first prototype was designed by the authors themselves in the T. J. Watson Research Center. They used a quantum channel of length 32 cm. Using longer channels requires many technological barriers to be overcome. For example, fiber optic cables tend to weaken and may even destroy the polarization of photons. Using boosters to strengthen the signal is impossible in the quantum mechanical world, since doing so produces an effect similar to eavesdropping. Interference pattern (instead of polarization) has been proposed and utilized to build longer quantum channels for key exchange. At present, Stucki et al. [293] hold the world record of performing quantum key exchange over an (underwater) channel of length 67 km between Geneva and Lausanne.

Exercise Set 8.3

8.10	We have exploited the property that H2 = I in order to prove the correctness of the quantum key-exchange algorithm. Exercise 8.5 lists some other operators (X and Z) which also satisfy the same property (X2 = Z2 = I). Can one use one of these transforms in place of H in the quantum key-exchange algorithm?
8.11	Assume that Carol eavesdrops (in the manner described in the text) during the execution of the quantum key-exchange protocol between Alice and Bob. Derive for different choices of i, x and z the following probabilities Pixz of having i ≠ j in the case x = y. i x z Pixz 0 0 0 0 0 0 1 1/2 0 1 0 1/2 0 1 1 1/2 1 0 0 0 1 0 1 1/2 1 1 0 1/2 1 1 1 1/2 If all these choices of i, x, z are equally likely, show that the probability that Carol introduces mismatch (that is, i ≠ j) in a shared bit during a random execution of the key-exchange protocol with x = y is 3/8. (Note that if x = y = z = 0, that is, if the execution of the algorithm proceeds entirely in the classical sense, Carol goes unnoticed. It is the application of the classically meaningless Hadamard transform, that introduces the desired security in the protocol.)
8.12	In the key-exchange algorithm described in the text, Bob (and also Carol) always measure qubits in the classical basis {|0〉, |1〉}. Now, consider the following variant of this algorithm. Alice sends, as before, one of the four qubits |0〉, |1〉, , depending on her choice of i and x. Bob upon receiving the qubit A generates a random guess . If y = 0, Bob measures A in the classical basis, whereas if y = 1, Bob measures A in the basis {H|0〉, H|1〉}. After this, they exchange x and y, and retain/discard the bits as in the original algorithm. Assume that there is no eavesdropping. Argue that this modified strategy works, that is, if x = y, we have i = j, whereas if x ≠ y, then i = j with probability . Explain the role of a passive adversary (Carol) in this modified strategy. Calculate for this variant the probability that Carol introduces an error in a shared bit (when x = y).