This is already part 9 of the series (time flies!). So far we have covered a wide array of topic around the nature of quantum computational units called qubits, superposition, entanglement, single-qubit gates, multi-qubit gates and some interesting concepts from the area of quantum information theory. In this post we will shift our attention to another interesting field in the quantum landscape - quantum cryptography. More specifically, we will explore a reference protocol for quantum key distribution, called BB884, discuss why it’s secure even when using a public channel to exchange qubits and realize a simple demonstrative implementation using Q#.

History of quantum key exchange protocol 🔗

In 1984, Charles Bennett from IBM Research and Gilles Brassard from the University of Montreal, published a paper entitled Quantum cryptography: Public key distribution and coin tossing, in which they proposed, for the first time, to use the principles of quantum information theory for distribution of random cryptographic keys. The paper is also considered to have laid foundations for the entire new branch of quantum research - quantum key distribution, and was one of the most influential papers in the history of quantum cryptography. The protocol has since become a staple for quantum information teaching curriculum and even earned a popular short name, BB84, which comes from the year the paper was published and the first letters of the authors last names.

Contrary to many other historically important papers and ideas in quantum computing, the ingenuity of the BB84 protocol lies in its remarkable simplicity. One only needs to know two fundamental quantum mechanical concepts to be able to grasp the inner workings and ideas behind it. The first is the concept superposition, and more importantly, the fact that we mentioned multiple times in this series already, namely, that superposition is basis dependent. Therefore, a qubit may be in one of the orthogonal states in one basis, say, $\ket{0}$ or $\ket{1}$ in the Pauli Z basis, but at the same time in a uniform superposition in another basis, say, $\ket{+}$ or $\ket{-}$ in the Pauli X, or Hadamard, basis. If you still find this notion I recommend a quick refresher of part 1 and part 2 of this series where we dug deep into this problem area.

The second concept that underpins BB84 protocol is the no-cloning theorem. We also already discussed it in detail in part 6 - it is the fact that a qubit in an unknown quantum state cannot be reliably copied. This at first glance severe limitation for quantum computing - after all, computers work by copying the data around - is actually an extremely attractive characteristic for the field of cryptography. As a security engineer, there is nothing that you’d welcome with open arms more that the ability to reliably detect if a given data packet (a qubit in this case) has been tapped into by a potential attacker or eavesdropper.

The remarkable feature of BB84 and quantum based key distribution is that two parties can use its ideas to securely exchange a symmetric encryption key over the public channel without sharing any prior information with each other. The only pre-requisite is that aside from the quantum communication channel over which the qubits will be transferred, there must exist a classic communication channel between them as well. Both of these channels can be public.

Bennett and Brassard wrote in their paper:

In this paper we use a radically different foundation for cryptography, viz. the uncertainty principle of quantum physics. (…) when information is encoded in non-orthogonal quantum states, such as single photons with polarization directions 0, 45, 90, and 135 degrees, one obtains a communications channel whose transmissions in principle cannot be read or copied reliably by an eavesdropper ignorant of certain key information used in forming the transmission. The eavesdropper cannot even gain partial information about such a transmission without altering it in a random and uncontrollable way likely to be detected by the channel’s legitimate users.

The details of BB84 🔗

Let us now go through the details of the BB84 quantum key distribution protocol. As we are already used to in our quantum discussions, the two parties - the sender and the recipient of the key - will be named Alice and Bob, while the potential eavesdropper will be called Eve. Alice would like to send a truly random key to Bob, which they can later use to engage in symmetric cryptography, while Eve will attempt to hijack it in transit.

Let’s imagine that Alice wants to share a key of bit length $n$. What she needs to do, according to BB84, is to select $4n$ random classical bits. Why is it $4n$, instead of simply $n$ will hopefully become apparent soon. To encode those classical bits into qubits, Alice will use two distinct bases, Pauli Z and Pauli X, switching between them randomly. Thus, she shall use one of the following four quantum states denoted by $\ket{\psi}$ to send a classical bit value encoded into a qubit to Bob:

$$\ket{\psi_0} = \ket{0}$$
$$\ket{\psi_1} = \ket{1}$$
$$\ket{\psi_2} = \ket{+} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$$
$$\ket{\psi_3} = \ket{-} = \frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$$

In this scheme, $\ket{\psi_0}$ and $\ket{\psi_2}$ can be used to represent classical bit value $0$, while $\ket{\psi_1}$ and $\ket{\psi_3}$ can be used to represent classical $1$. At the end of this, Alice possesses $4n$ qubits containing her original bit values encoded using two different bases.

In the next step, Alice sends the qubits to Bob over a public channel, who then proceeds to measure them. Of course Bob has no idea which basis Alice chose to encode the bits, so he has to guess - and that is exactly what he does. Upon each qubit’s measurement, he guesses whether he should measure in the Pauli Z or Pauli X basis. Statistically speaking, Bob will choose the correct basis half of the time. If he guesses right, then he’d get the exact value that Alice encoded, but if he guesses wrong, he will run into a uniform superposition and therefore he’d get the correct value only 50% of the time.

At this point, Alice and Bob need to engage in a communication over a classical channel, and compare the bases they chose for each of the qubit measurement (not the results!). They throw away all the qubits for which they measured in different bases and leave only the ones for which the basis was the same. Given that, as mentioned, Bob can guess the correct basis half of the time, they should at this point be left with about $2n$ qubits (and thus the same amount of classical bit values encoded in them). Should that not be the case, which might happen especially for shorter keys, and they are left with less qubits than $2n$, they should abort the protocol and start over.

Next, Alice should randomly select $n$ of the remaining ~$2n$ qubits that will serve as eavesdropper check against Eve’s malicious activities. Alice and Bob publicly compare the measured values - this time not the bases, as they are already sure that the bases choses where the same - for those $n$ qubits. If there was no eavesdropper, the measured values should agree 100% (or a little less than that if we factor in potential quantum errors, but we will ignore that for simplicity).

Let’s now consider what happens to the qubits when Eve tries to intercept them in transit. Of course in an ideal scenario, she’d want to clone the qubit - which quantum mechanics explicitly prohibits. Therefore, the only attack she can mount is to measure the qubit, note the resulting bit and afterwards let the qubit continue on its way to Bob. The problem here (for Eve) and the strength of quantum key distribution (for Alice and Bob) is that a measurement changes the state of the qubit. Of course Eve doesn’t know in which basis to measure - just like Bob doesn’t know too - so, like him, she has to guess. Similarly to Bob, from the statistical point of view, she will be right about the basis about half of time. This is the core idea behind BB84. Recall that in the earlier step, Alice and Bob discarded all the qubits where their bases did not agree. So in the remaining pool of $2n$ qubits, they are expecting full agreement of measured values. That is indeed the case if, in transit, Eve measured the qubit using a randomly chosen basis, which happened to be correct, and sent the qubit further to Bob. But she could have guessed correctly only about half of time, meaning in the other cases when she guessed wrong, she would have caused the qubit to assume one of the orthogonal basis vectors from the basis she chose. This in turn means that the qubit was in a superposition in respect to the basis chosen by Bob (which was, of course, also the original basis chosen by Alice), and thus would yield a random result when measured in that basis - classical $0$ 50% of time and classical $1$ the other 50% of time. Therefore, if there was an eavesdropper who tapped into the communication channel and measured each qubit in transit, the results of Bob’s measurements for the $n$ sample selected for eavesdropper check would disagree with values encoded by Alice about 25% of time. Should Bob and Alice determine that their values disagree even though their bases agree, they should abort the protocol as it means they managed to sniff out an attacker.

In the case there was no attacker detected, Alice and Bob can discard the $n$ bits they used for an eavesdropper check and the remaining $n$ bits can be used as their intended key. Hopefully at this point it is clear why, in order to produce a key of bit length $n$, we ended up encoding and using $4n$ qubits.

In order to fully illustrate the protocol, let’s now express it in Q# code.

BB84 in Q 🔗

Since there is no currently available publicly accessible technology that allows us to physically send qubits from one place to another, we will, as it was the case with the earlier demos in this series, run the entire protocol inside a single process. It will be a de facto simulation of BB84 using Q#. That said, Q# still provides us with a great tool to test and verify the concepts behind BB84.

In the sample below, we will try to execute the BB84 for an $n = 256$ bit key. This means that we’d need to allocate at minimum $4n$ qubits - way beyond the capabilities of current quantum computing hardware. What we can do instead though, is we can run the protocol in a number of roundtrips - using $16$ qubit chunks in each roundtrip. The skeleton of the operation should look as follows:

operation RunBB84Protocol(expectedKeyLength : Int, eavesdropperProbability : Double) : Bool {
    let chunk = 16;

    // we want to transfer 4n + 𝛿 required bits
    // n = expectedKeyLength
    // chunk = amount of qubits to allocate and send in a single roundtrip
    // 𝛿 = extra bits in case the low sample size causes us to end up with less than required bits
    // at the end of the protocl execution. In our case we assume 𝛿 = 2 * chunk (32)
    let roundtrips = (4 * expectedKeyLength + 2 * chunk) / chunk;
    
    mutable aliceValues = new Bool[0];
    mutable aliceBases = new Bool[0];
    mutable bobResults = new Bool[0];
    mutable bobBases = new Bool[0];
    
    for (roundtrip in 0..roundtrips-1) {
        using (qubits = Qubit[chunk]) {
        
         // continue with the protocol 
              
        }
    }

In this introductory snippet, we introduced a $chunk$ size to represent amount of qubits handled at once - just like we mentioned earlier. Additionally, the expected key length is a parameter that can be passed into the operation, so that we could test this program with different key sizes. Finally, the eavesdropper probability is represented by a double number (to express percentages), which will let us invoke the code without eavesdropper at all and with eavesdropper at certain probability rates.

The amount of roundtrips is determined by taking the $4n$ - as defined by the BB84 protocol, adding a certain safety value $𝛿$ to it, to offset possible sways in probabilities related to randomness built into the BB84 (this is not necessary but advisable to avoid unnecessary aborting of the protocol) and finally dividing by the chunk size.

Finally, we initialize mutable arrays - since arrays are immutable by default in Q# - to hold the classical bit values for both Alice (source bits) and Bob (result bits) and the bases they chose - Alice for encoding, and Bob for measuring the qubit. As we discussed in the BB84 protocol logic earlier, all these arrays will end up having the same length.

The next step is to start the loop representing the roundtrips, allocate the amount of qubits defined in a single roundtrip ($chunk = 16$) and let Alice prepare those qubits.

// prepare Alice's qubits
for (qubit in qubits) {

    // Alice chooses random bit
    let valueSelected = DrawRandomBool(0.5);
    if (valueSelected) { X(qubit); }
    set aliceValues += [valueSelected];

    // Alice chooses random basis by drawing a random bit
    // 0 will represent |0> and |1> computational (PauliZ) basis
    // 1 will represent |-> and |+> Hadamard (PauliX) basis
    let aliceBasisSelected = DrawRandomBool(0.5);
    if (aliceBasisSelected) { H(qubit); }
    set aliceBases += [aliceBasisSelected];
}

For each qubit in the roundtrip (chunk) Alice needs to choose a random bit value, which she does using the helper operation $DrawRandomBool(successProbability : Double)$ from the $Microsoft.Quantum.Random$ namespace, which, given a success probability, returns a single Bernoulli trial that is true with the given probability. We (Alice, me and you, the reader) keep track of each value by adding it to the mutable $aliceValues$ array. If the random boolean was $true$, we shall apply the $X$ gate to the qubit.

Next, Alice will need to choose the relevant basis to use to encode the bit. In our example, we will do it again via $DrawRandomBool$ - adopting a rule that if it returns $false$, we will use computational basis Pauli Z ($\ket{0}$ and $\ket{1}$), while if it returns $true$, we will use Hadamard basis Pauli X ($\ket{+}$ and $\ket{-}$). The practical consequence is that in the latter case we need to additionally apply the $H$ unitary transformation to the qubit. Just like with the encoded values, we keep track of the randomly selected bases in the mutable array we created earlier - $aliceBasisSelected$ array. It should also be noticeable that the index of the value in the values array will correspond to the index of the basis used to encode that value in the bases array.

At this point we can - in our imagination at least - assume that the qubits fly over to Bob using a quantum communication link. Thus, in the next step, we can introduce Eve who will attempt to intercept and read those qubits. Since we already defined the eavesdropping probability as a $Double$, it will allow us to test the protocol with different conditions, such as 100% eavesdropper engagement, 0% and some in-between values. We have to, however, account for that in code, which we will do next.

//eavesdropper!!!
for (qubit in qubits) {
    let shouldEavesdrop = DrawRandomBool(eavesdropperProbability);
    if (shouldEavesdrop) {
        let eveBasisSelected = DrawRandomBool(0.5);
        let eveResult = Measure([eveBasisSelected ? PauliX | PauliZ], [qubit]);
    }
}

Eve gets a chance to interact with each of the qubits in batch, based on the $eavesdropperProbability$. This is then passed to the $DrawRandomBool(successProbability : Double)$ operation to create a kind of a biased coin type of result. If we have determined that eavesdropper can act on a given qubit, we proceed to the measurement. At this point Eve has to guess the measurement basis - since she doesn’t know how the qubit was encoded by Alice. She does that, obtains a result and then qubit then continues to Bob.

The final stage of the first part of BB84 protocol is for Bob to receive the qubits and measure them. He shall follow the exact same procedure as Eve had to go through - select a random basis and measure the qubits.

for (qubit in qubits) {
    // Bob chooses random basis by drawing a random bit
    // 0 will represent PauliZ basis
    // 1 will represent PauliX basis
    let bobBasisSelected = DrawRandomBool(0.5);
    set bobBases += [bobBasisSelected];
    let bobResult = Measure([bobBasisSelected ? PauliX | PauliZ], [qubit]);
    set bobResults += [ResultAsBool(bobResult)];
    Reset(qubit);
} 

Just like Alice did, Bob keeps track of his bases and measurements in the two arrays defined earlier - $bobBasisSelected$ and $bobResults$. Obviously the length of those two arrays, and the index positions for qubits, correspond to the bases and values arrays of Alice. This is critical for the subsequent steps, where comparisons will start.

At this point we can quickly regroup, to make sure we know exactly where we are in BB84. Alice has sent her random bits, encoded into qubits and stored them in $aliceValues$ array. Her (also random) bases to encode those values have been stored in $aliceBases$ array. Bob’s measurement results are located in $bobResults$ array, while his randomly chosen measurement bases are stored in $bobBases$ array. Eve interfered with the communication with the probability equal to $eavesdropperProbability$ though her measurement results and bases are not stored anywhere as they are irrelevant for the protocol - what is important is whether Alice and Bob will be able to detect here malicious presence at all.

In the next step, Alice and Bob will compare the bases they chose. As we said, in real BB84 implementation, they can do it over a public channel - in our case we just do it in process. If the bases for a given qubit agree for them, then they want to keep the corresponding value (Alice) or the corresponding measurement result (Bob). On the other hand, if they used a different basis, then that qubit’s value/measurement result should be discarded. Based on the law of probability, given that Bob was guessing the basis from two possible options, Alice and Bob should have about 50% of original qubits ($2n$) left. The comparison code is shown next:

Message("Comparing bases....");
mutable aliceValuesAfterBasisComparison = new Bool[0];
mutable bobValuesAfterBasisComparison = new Bool[0];

// compare bases and pick shared results
for (i in 0..Length(aliceValues)-1) {
    // if Alice and Bob used the same basis
    // they can use the corresponding bit
    if (aliceBases[i] == bobBases[i]) {
        set aliceValuesAfterBasisComparison += [aliceValues[i]];
        set bobResultsAfterBasisComparison += [bobResults[i]];
    }
}
Message("Bases compared.");

At this point we introduced two new arrays - $aliceValuesAfterBasisComparison$ and $bobResultsAfterBasisComparison$. They hold the classical bit values for the classical bit values for which Alice and Bob adopted the same basis. If there was no eavesdropper, those arrays are expected to be identical.

To facilitate the check for eavesdropper presence, Alice and Bob now randomly choose 50% of the remaining classical bits (so, $n$). This can be done in a number of ways, in our case we will choose a very simple, pragmatic method. We shall create a new array represented by indices of the entries in $aliceValuesAfterBasisComparison$. We will then chunk it using the $Chunks (nElements : Int, arr : ‘T[])$ function that Q# has built-in. It will allow us to create pairs of values corresponding to indices of $aliceValuesAfterBasisComparison$ in a following data structure:

[[0,1], [2,3], [4,5], [6,7] ...]

Then, we will simply iterate through this multidimensional array and randomly pick one of the pair values which ultimately gives us a random set of indices of $aliceValuesAfterBasisComparison$ that can be used for eavesdropper check. For example:

[1,3,4,7...]

The code is shown next:

Message("Performing eavesdropping check....");
// select a random bit of every 2 bits for eavesdropping check
mutable eavesdropppingIndices = new Int[0];
let chunkedValues = Chunks(2, RangeAsIntArray(IndexRange(aliceValuesAfterBasisComparison)));
for (i in IndexRange(chunkedValues)) {
    if (Length(chunkedValues[i]) == 1) {
        set eavesdropppingIndices += [chunkedValues[i][0]];
    } else {
        set eavesdropppingIndices += [DrawRandomBool(0.5) ? chunkedValues[i][0] | chunkedValues[i][1]];
    }
}

Bob and Alice can now use those selected indices, stored now in $eavesdropppingIndices$ array, to compare their bit values.

// compare results on eavesdropping check indices
mutable differences = 0;
for (i in eavesdropppingIndices) {
// if Alice and Bob get different result, but used same basis
// it means that there must have been an eavesdropper (assuming perfect communication)
    if (aliceValuesAfterBasisComparison[i] != bobResultsAfterBasisComparison[i]) {
        set differences += 1;
    }
}

At this point, after comparing the different randomly selected indices in their classical bit values/results arrays, Bob and Alice have compiled a running total of differences in bit values between them. Leaving quantum errors aside for simplicity of this discussion, if at this point there is any difference between Bob and Alice, it means that there was an eavesdropper on their quantum communication channel, as it should not be possible for them to possess different classical bit value if they chose the same basis. Of course as we already extensively discussed, Eve as the attacker could also guess the basis correctly and if all three of them agreed on a basis, then no difference would be recorded. But Eve will be wrong about 50% of time, which will then cause some discrepancies between Alice and Bob, and this is exactly what they are after.

let errorRate = IntAsDouble(differences)/IntAsDouble(Length(eavesdropppingIndices));
Message($"Error rate: {errorRate*IntAsDouble(100)}%");
if (errorRate > 0.0) {
    Message($"Eavesdropper detected! Aborting the protocol");
    return false;
} else {
    Message($"No eavesdropper detected.");
}

Using the running total of recorded differences and the total of bits selected for eavesdropping check, Alice and Bob can compute the error rate, which they can use as a confidence indicator that no one intercepted their communication. In this idealistic example, we shall use $0.0$ as the error threshold - if that level is exceeded, meaning there was any difference between the Alice’s and Bob’s bit values in the sampled set, the protocol will be aborted, which we indicate by returning false from the operation. Otherwise Alice and Bob can continue - and they are almost at the end now, as everything that’s left is to discard the eavesdropping check bits (using their indices) and construct the shared key out of what’s left. This can be conveniently done using the $Exclude (remove : Int[], array : ‘T[])$ function from $Microsoft.Quantum.Arrays$ namespace.

// remove indices used for eavesdropping check from comparison
let aliceKey = Exclude(eavesdropppingIndices, aliceValuesAfterBasisComparison);
let bobKey = Exclude(eavesdropppingIndices, bobResultsAfterBasisComparison);

Message($"Alice's key: {BoolArrayToString(aliceKey)} | key length: {IntAsString(Length(aliceKey))}");
Message($"Bob's key:   {BoolArrayToString(bobKey)} | key length: {IntAsString(Length(bobKey))}");
Message("");

let keysEqual = EqualA(EqualB, aliceKey, bobKey);
Message($"Keys are equal? {keysEqual}");
if (not keysEqual) {
    Message("Keys are not equal, aborting the protocol");
    return false;
}

if (Length(aliceKey) < expectedKeyLength) {
    Message("Key is too short, aborting the protocol");
    return false;
}

Message("");
let trimmedKey = aliceKey[0..expectedKeyLength-1];
Message($"Final trimmed {expectedKeyLength}bit key: {BoolArrayToString(trimmedKey)}");

return true;

Once the eavesdropping bits are dropped, Alice and Bob each have an identical key on their side. In this example we can compare them - to prove that our reasoning was correct, but in reality that is not necessary anymore. In fact, it’s actually not possible anymore since the key is supposed to be kept secret and the goal of BB84 is to provide a way to distribute a private key between parties that have no private secure communication channel.

However, we can still compare if the length of the key is not shorter than what was expected. Since everything is probability driven, the guessing game Bob and Eve play can tilt in either direction, possibly resulting in too few classical bits being left at the end of this entire protocol. In that case, the protocol must be aborted and started over. However, since we attempted to offset this possibility by adding a small safety pad to the amount of qubits transferred (we went for $4n + 2*chunkSize$) it is much more likely that we have more bits than required and thus a trimming activity is in order. This is what the final parts of the code above handle.

The remaining piece is to add the orchestration code - that will invoke the entire BB84 protocol we just written for different levels of eavesdropper possibilities. For example - obtaining a 256 bit key, where eavesdropper is present:

@EntryPoint()
operation Start() : Unit {
        
    let result1 = RunBB84Protocol(256, 1);
    Message("Running the protocol for 256 bit key with eavesdropping probability 1 resulted in " + (result1 ? "succcess" | "failure"));
}

If we execute this code now, the output should resemble the one shown below - obviously it will differ a little bit from run to run due to probabilistic nature of the protocol:

***********

Comparing bases....
Bases compared.

Performing eavesdropping check....
Error rate: 24.43609022556391%
Eavesdropper detected! Aborting the protocol
***********

Running the protocol for 256 bit key with eavesdropping probability 1 resulted in failure

This is aligned with our expectations - as discussed earlier, eavesdropper presence on each qubit should create about 25% error rate.

On the other hand, if we now execute the protocol again, but this time with eavesdropping probability dropped to 50%, we should reasonably expect the error rate to go down to ~12.5%, still too high for our ideal expectations, but much better.

@EntryPoint()
operation Start() : Unit {
        
    let result1 = RunBB84Protocol(256, 0.5);
    Message("Running the protocol for 256 bit key with eavesdropping probability 0.5 resulted in " + (result1 ? "succcess" | "failure"));
}

This produces the following (still random to certain degree) failure output:

***********

Comparing bases....
Bases compared.

Performing eavesdropping check....
Error rate: 11.150375939849624%
Eavesdropper detected! Aborting the protocol
***********

Running the protocol for 256 bit key with eavesdropping probability 0.5 resulted in failure

Finally, if we disable the eavesdropper, the error rate should go down to 0, and Alice and Bob should be able to exchange the key successfully.

@EntryPoint()
operation Start() : Unit {
        
    let result1 = RunBB84Protocol(256, 1.0);
    Message("Running the protocol for 256 bit key with eavesdropping probability 1.0 resulted in " + (result1 ? "succcess" | "failure"));
}

And that is exactly what we see in the output, when we run the code with these parameters:

***********

Comparing bases....
Bases compared.

Performing eavesdropping check....
Error rate: 0%
No eavesdropper detected.

Alice's key: 010001010011110010001110110001110101001100110101010110001110111011010101110010000111100100110100001110000110100110001110111011001001010010011100111111100011000000111011111110010010000110110111011101001011011100110101110000111101001111100110010001011100101110100011100000110001101 | key length: 279
Bob's key:   010001010011110010001110110001110101001100110101010110001110111011010101110010000111100100110100001110000110100110001110111011001001010010011100111111100011000000111011111110010010000110110111011101001011011100110101110000111101001111100110010001011100101110100011100000110001101 | key length: 279

Keys are equal? True

Final trimmed 256 bit key: 0100010100111100100011101100011101010011001101010101100011101110110101011100100001111001001101000011100001101001100011101110110010010100100111001111111000110000001110111111100100100001101101110111010010110111001101011100001111010011111001100100010111001011
Running the protocol for 256 bit key with eavesdropping probability 0.0 resulted in succcess

And this is it! We have managed to simulate the behavior of BB84 protocol and safely generated a symmetric 256 bit key with it.

One-time pad and quantum computing 🔗

The key transmitted as part of BB84 can then be used for, for example, a one-time pad message encryption technique. The critical aspect of that technique is that it is information-theoretically secure, that is, it cannot, in principle, be cracked because the ciphertext produced by it wouldn’t provide the attacker with any information about the original message. The prerequisites, however, for the one-time pad technique to be unbreakable, are that the key is completely random, it must be at least the length of the message to encrypt, must not be reused and, naturally, must be kept secret by both parties (especially in transit).

Quantum key distribution can provide guarantee to the parties engaging in cryptographic message exchange that the first and last requirements from the list above are going to be fulfilled. We already discussed the role of quantum computing in true random number generation in part 2. This is randomness guaranteed by the laws of nature and particularly enticing for this use case because most of the software based number generators in different programming frameworks and libraries are actually not suitable for high quality cryptographic application cases.

Additionally, as already discussed, BB84 provides a provable and reliable way of detecting and eavesdropper attempting to steal the key in transit between the two parties. This allows the engaged parties to abort the protocol if such intrusive behavior is determined, which dramatically improves the security of the key, as the two actors only have two focus on protecting the key once in their possession.

The biggest obstacle, on the other hand, for the protocol are the well-known problems of cheaply and reliably transferring qubits between two parties. Bennett and Brassard pointed that out in their paper too:

(…) the protocols are provably secure even against an opponent with superior technology and unlimited computing power, barring fundamental violations of accepted physical laws.
Offsetting these advantages is the practical disadvantage that quantum transmissions are necessarily very weak and cannot be amplified in transit.

Additionally - and we will not go into the physical details as it is out of scope for a text focused on quantum computational aspects of the protocol - the big weakness of the BB84 proposal was that it was based on a single photon source. This, on the other hand, greatly affects the scalability of the solution and trying to switch to multi-photon signals can greatly increase the possible attack surface. The practical consequence of this is discussed by Hoi-Kwong Lo and Yi Zhao in their Quantum Cryptography paper.

The original BB84 proposal requires a single photon source. However, most QKD implementations are based on faint lasers due to the great challenge to build perfect single photon sources. Faint laser pulses are weak coherent states that follow Poisson distribution for the photon number. The existence of multi-photon signals opens up new attacks such as photon-number-splitting attack. The basic idea of a photon-number-splitting attack is that Eve can introduce a photon-number-dependent transmittance. In other words, she can selectively suppress single-photon signals and transmit multi-photon signals to Bob. Notice that, for each multi-photon signal, Eve can beamsplit it and keep one copy for herself, thus allowing her to gain a lot of information about the raw key.

Summary 🔗

Overall the quantum key distribution based on BB84 is a pretty remarkable protocol - we have only used public channels to send the qubits and then engage in classical communication, but thanks to the innovative and clever scheme proposed by BB884, the two parties were able to securely exchange a random key that is now suitable for safe encryption use.

In the next post we shall continue the exploration of quantum cryptography, by looking at some alternative quantum key distribution protocols.