Quantum Key Distribution

[Genady]

(From Rieffel, Eleanor G.; Polak, Wolfgang H.. Quantum Computing: A Gentle Introduction.)

Exercise 2.9. In the BB84 protocol, how many bits do Alice and Bob need to compare to have a 90 percent chance of detecting Eve’s presence?

For the reference, here is a description of the BB84 protocol:

Quote

The aim of the BB84 protocol is to establish a secret key, a random sequence of bit values 0 and 1, known only to the two parties, Alice and Bob.

Suppose Alice and Bob are connected by two public channels: an ordinary bidirectional classical channel and a unidirectional quantum channel. The quantum channel allows Alice to send a sequence of single qubits to Bob; in our case we suppose the qubits are encoded in the polarization states of individual photons. Both channels can be observed by an eavesdropper Eve.

To begin the process of establishing a private key, Alice generates a random sequence of classical bit values. As we will see, a random subset of this sequence will be the final private key. Alice then randomly encodes each bit of this sequence in the polarization state of a photon by randomly choosing for each bit one of the following two agreed-upon bases in which to encode it: the standard basis,  

0→ |↑> 

1→ |→>,  

or the Hadamard basis,  

0→ |+> = 1/√2 (|↑> + |→>)

1→ |- > = 1/√2 (|↑> − |→>).  

She sends this sequence of photons to Bob through the quantum channel. 

Bob measures the state of each photon he receives by randomly picking either basis. Over the classical channel, Alice and Bob check that Bob has received a photon for every one Alice has sent, and only then do Alice and Bob tell each other the bases they used for encoding and decoding (measuring) each bit. When the choice of bases agrees, Bob’s measured bit value agrees with the bit value that Alice sent. When they chose different bases, the chance that Bob’s bit matches Alice’s is only 50 percent. Without revealing the bit values themselves, which would also reveal the values to Eve, there is no way for Alice and Bob to figure out which of these bit values agree and which do not. So they simply discard all the bits on which their choice of bases differed. An average of 50 percent of all bits transmitted remain. Then, depending on the level of assurance they require, Alice and Bob compare a certain number of bit values to check that no eavesdropping has occurred. These bits will also be discarded, and only the remaining bits will be used as their private key.  

To gain information, Eve must intercept the photons transmitted by Alice through the quantum channel. Eve must send photons to Bob before knowing the choice of bases made by Alice and Bob, because they compare bases only after Bob has confirmed receipt of the photons. If she sends different photons to Bob, Alice and Bob will detect that something is wrong when they compare bit values.

To gain information, Eve makes a measurement before sending the photons to Bob. Since Alice has not yet told Bob her sequence of bases, Eve does not know in which basis to measure each bit. If she randomly measures the bits, she will measure using the wrong basis approximately half of the time. When she uses the wrong basis to measure, the measurement changes the polarization of the photon before it is resent to Bob. This change in the polarization means that, even if Bob measures the photon in the same basis as Alice used to encode the bit, he will get the correct bit value only half the time.  

Overall, for each of the qubits Alice and Bob retain, if the qubit was measured by Eve before she sent it to Bob, there will be a 25 percent chance that Bob measures a different bit value than the one Alice sent. Thus, this attack on the quantum channel is bound to introduce a high error rate that Alice and Bob detect by comparing a sufficient number of bits over the classical channel.  If these bits agree, they can confidently use the remaining bits as their private key. So, not only is it likely that 25 percent of Eve’s version of the key is incorrect, but the fact that someone is eavesdropping can be detected by Alice and Bob. Thus, Alice and Bob run little risk of establishing a compromised key; either they succeed in creating a private key or they detect that eavesdropping has taken place.

 

My solution:

If eavesdropping has taken place, then about 25% of the pairs of bits don't match. In this case, when Alice and Bob pick a pair at random, there is 75% chance to pick a matching pair. If they continue and pick n pairs, there is 0.75ⁿ chance that they all match.  0.75⁸ = 0.1. So, if they compare 8 or more pairs, they have 90% or more chance to detect the eavesdropping.

Edited October 9, 2023 by Genady

[Genady]

Exercise 2.10. Analyze Eve’s success in eavesdropping on the BB84 protocol if she does not even know which two bases to choose from and so chooses a basis at random at each step.  

a. On average, what percentage of bit values of the final key will Eve know for sure after listening to Alice and Bob’s conversation on the public channel?  

b. On average, what percentage of bits in her string are correct?  

c. How many bits do Alice and Bob need to compare to have a 90 percent chance of detecting Eve’s presence?

 

My answers:

a. 0

b. 50%

c. 0.5ⁿ < 0.1; n > 3

 

Is it correct?

 

[Genady]

Exercise 2.11. B92 quantum key distribution protocol. In 1992 Bennett proposed the following quantum key distribution protocol. Instead of encoding each bit in either the standard basis or the Hadamard basis as is done in the BB84 protocol, Alice encodes her random string x as follows:  

0 ↦ |0〉 

1 ↦ |+〉 = 1/ √ 2 (|0〉 + |1〉)  

and sends them to Bob.

Bob generates a random bit string y. If y_i = 0, he measures the i-th qubit in the Hadamard basis {|+〉, |−〉}, if y_i = 1 he measures in the standard basis {|0〉, |1〉}.

In this protocol, instead of telling Alice over the public classical channel which basis he used to measure each qubit, he tells her the results of his measurements. If his measurement resulted in |+〉 or |0〉, Bob sends 0; if his measurement indicates the state is|1〉 or |−〉, he sends 1.

Alice and Bob discard all bits from strings x and y for which Bob’s bit value from measurement yielded 0, obtaining strings x' and y'. Alice uses x' as the secret key and Bob uses y'. Then, depending on the security level they desire, they compare a number of bits to detect tampering. They discard these check bits from their keys.

a. Show that if Bob receives exactly the states Alice sends, then the strings x' and y' are identical strings.  

b. Why didn’t Alice and Bob decide to keep the bits of x and y for which Bob’s bit value from measurement was 0?  

c. What if an eavesdropper Eve measures each bit in either the standard basis or the Hadamard basis to obtain a bit string z and forwards the measured qubits to Bob? On average, how many bits of Alice and Bob’s key does she know for sure after listening in on the public classical? If Alice and Bob compare n bit values of their strings x' and y', how likely are they to detect Eve’s presence?

 

My solution:

To clarify the protocol, let's make the table:

	1a	1b	2	3	4a	4b
xi:	0	0	0	1	1	1
yi:	0	0	1	0	1	1
Alice sends:	|0>	|0>	|0>	|+>	|+>	|+>
Bob measures:	|+>	|- >	|0>	|+>	|0>	|1>
Bob sends:	0	1	0	0	0	1
Action:	discard	keep	discsard	discard	discard	keep

a. As seen in the table, only the cases 1b and 4b are kept. In these cases, x_i and y_i are identical.

b. Otherwise, they would keep the mismatched cases 2 and 3.

c. Eve is only interested in cases 1b and 4b:

	1ba	1bb	4ba	4bb
xi:	0	0	1	1
Alice sends:	|0>	|0>	|+>	|+>
Eve measures standard:	|0>	|0>	|0>	|1>
Eve measures Hadamard:	|+>	|- >	|+>	|+>

If she measured in the standard basis, the only unambiguous result was when she got |1>, case 4bb, which constitutes 25%. Similarly, if she measured in the Hadamard basis, the only unambiguous result was in case 1bb, also 25%. So, Eve knows for sure 25% of the bits, on average.

Just like in the BB84 protocol, Eve sends to Bob 50% of the bits in a modified state. Of them, Bob will measure randomly a correct result in 50%. Thus, 25% of the final strings will differ. After comparing n bits, Alice and Bob will detect Eve's presence with 1-0.75ⁿ likelihood. 

Is it correct? I am not really sure in the last part. A table that includes what Eve sends to Bob and what Bob measures, would make the answer certain, but it is too much work.