In the last part of this series we started talking about the area of quantum cryptography, or more accurately, quantum key distribution. We dissected, in considerable amount of detail, the BB84 protocol, and discussed how it can lead to effectively unbreakable cryptography.

Today we shall continue with quantum key distribution by looking at a sibling to BB84, the B92 protocol.

Background 🔗

In 1992, Charles Bennett from IBM Research, the co-author of BB84 protocol, published a paper entitled Quantum Cryptography Using Any Two Nonorthogonal States, in which he proposed a simplified variant of BB84, which later became known as the quantum key distribution B92 protocol. This shorthanded name, just like in the case of BB84, was derived from the first letter of the author’s last name, and the year of the publication.

The main difference between BB84 and B92 was that instead of using fours separate photon polarization states, making up two orthogonal bases, on which BB84 relied, Bennett suggested to use only two distinct polarizations, constituting a single non-orthogonal base. This was a very clever idea, which simplified the amount of negotiation needed between the two parties engaging in the quantum key distribution. Bennett wrote in his paper:

(…) the security of non-EPR key distribution schemes is derived from the fact that any measurement which fails to disturb each of two nonorthogonal states also fails to yield any information distinguishing them. This naturally suggests the possibility that key distribution might be performed using only two nonorthogonal states, instead of the four.

Due their similarity, both BB84 and B92 have been experimentally realized many times, including the first successful key distribution over long distance optical fiber network by Hughes, Morgan and Peterson in Los Alamos National Laboratory in 1999. They wrote there:

From the perspective of the physics involved B92 and BB84 are so similar that demonstration of one protocol indicates that the other will also be possible under the same physical conditions.

Theory 🔗

As we recall from linear algebra, two vectors are orthogonal if their inner product is zero. This is expressed in the following way:

$$\braket{0|1} = 0$$

In quantum computing, as it should be blatantly clear at this point (we are, after all, already at part 10 of this series!), we work with qubits using orthonormal vectors - meaning vectors that are orthogonal and unit vectors at the same time. In a two dimensional Hilbert space, two orthonormal vectors form a basis for a vectors space when any element of that space could be expressed as a linear combination of those two basis vectors. We can always find infinitely many bases for a given vectors space - as long as the two chosen states (in Hilbert space, we call unit vectors “state vectors”) that represent classical bits of 0 and 1 are orthonormal, and thus distinguishable. The most common is of course the computational basis ${\ket{0}$,$\ket{1}}$.

And this brings us to the gist of the idea. As mentioned above, in B92, instead of using two randomly interchanged orthogonal bases like it was the case in BB84, we rely on a single non-orthogonal basis to encode a value of the classical bit. Given a classical bit $x$, this can be summarized as:

$$\ket{\psi} =
\begin{cases}
\ket{0} & \text{when x = 0} \
\frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) = \ket{+} & \text{when x = 1} \
\end{cases}
$$

Protocol steps 🔗

Before diving deeper into the steps involved in B92, I recommend you have a look (in case you haven’t yet) at the last post about BB84. There is a lot of overlap between the two, and for the sake of not repeating myself too much, I will try to mainly focus on highlighting the parts of B92 that are different from BB84.

Alice and Bob would like to securely share a key of an arbitrary bit length between them. The protocol starts by Alice generating a random set of classical bits that she will encode in qubits that will be sent over to Bob. For reasons that should soon become clear, for a desired key length of $n$, she will need to generate $8n$ bits - and thus use that many qubits to encode those. The encoding process follows the simple rule that we mentioned earlier - if Alice generates a random $0$, she puts the qubit in state $\ket{0}$, and when she generates $1$, the qubit will need to be transformed into $\frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) = \ket{+}$. Let’s call that Alice’s classical bit which she encoded into a qubit, an $x$.

At this point the qubits are sent over to Bob using a quantum communication channel. Bob receives them and can proceed to make measurements. However, to do that, he will need to choose a basis for the measurement and similarly to BB84 protocol, he doesn’t know which one should be used. He could measure in the Pauli Z basis, which would be the correct one for roughly half of the qubits that Alice sent, namely those where $0$ was encoded as $\ket{0}$. But with equal probability, he could pick the Pauli X (Hadamard) basis measurement, which is relevant for the other half of Alice’s qubits - those where $1$ was encoded as $\ket{+}$. So Bob generates a random classical bit (or flips the proverbial coin) - let’s call it $y$. If $y = 0$, then he measures the qubit in the Pauli Z basis, and if $y = 1$, he uses the X basis. Upon measurement, irrespective of the basis chosen, Bob obtains a classical measurement result $z$, which could be $0$ or $1$.

Let’s pause here for a moment and recap quickly. Alice generated a classical bit $x$, encoded it into a qubit using the rules we defined above and sent it over to Bob. Bob chooses the measurment basis the qubit using a random bit $y$ and obtains a classical result $z$. This loop can be repeated a number of times - namely $8n$ for a key of length $n$.

In the next step, instead of comparing the bases they chose, as Alice and Bob did in BB84, Bob publishes over a public channel his classical results $z$ for each of the measured qubit. When $z = 1$, the given classical bit $y$ (Bob’s) bit corresponding to this measurement result and the related $x$ (Alice’s) bit are discarded by Bob and Alice respectively, leaving them only with $x$ and $y$ pairs for which $z = 0$. What remains is the a key of length $2n$. Why would Alice and Bob discard the bits for which the qubit measurement result was $z = 1$? To answer this question, let’s go over the possibilities that they faced. The four outcome variants for Bob are as follows:

1. generate $y = 0$, measure in the Pauli Z basis and get a classical measurement result $z = 0$. He cannot really say if Alice encoded $x = 0$, sent $\ket{0}$ and he measured in the correct basis, or whether she encoded $x = 1$, sent $\ket{+}$ and by measuring the qubit in the incorrect basis it simply collapsed to $\ket{0}$ (and thus $z = 0$). Therefore such $y$ (and the corresponding $x$) must be discarded.
2. generate $y = 0$, measure in the Pauli Z basis and get a classical measurement result $z = 1$. He is now certain that Alice generated $x = 1$, sent him $\ket{+}$ and it collapsed to $\ket{1}$, because she would never send $\ket{1}$ encoded in the Z basis. The remaining pair is ${x = 1,y = 0}$
3. generate $y = 1$, measure in the Pauli X basis and get a classical measurement result $z = 0$. Similarly to our first point, he cannot really say if Alice encoded $x = 1$, sent $\ket{+}$ and he measured in the correct basis, or whether she encoded $x = 0$, sent $\ket{0}$ and by measuring the qubit in the incorrect basis it simply collapsed to $\ket{+}$ (and thus $z = 0$). Therefore such $y$ (and the corresponding $x$) must be discarded.
4. generate $y = 1$, measure in the Pauli Z basis and get a classical measurement result $z = 1$. He is now certain that Alice generated $x = 0$, sent him $\ket{0}$ and it collapsed to $\ket{-}$, because she would never send $\ket{-}$ encoded in the X basis. The remaining pair is ${x = 0,y = 1}$

At this point it should also be clear why Alice and Bob started with $8n$ qubits and are left with only $2n$. For cases where Bob picked the correct basis to measure, the qubits have been discarded, leaving only $4n$ qubits. In the remaining pool, the invalid basis was chosen, so in half of cases the measurement result was $z = 0$, which also meant those qubits were discarded too - resulting in only $2n$ bits left. The final thing worth noting is that the remaining ${x,y}$ pairs are not equal to each other - they are perfectly correlated but have opposite values. This means that while for Alice her obtained key is simply her collection of remaining $x$ bits, Bob has to flip the value of each of his $y$ bits.

What we have not touched upon yet is the eavesdropper check. Since at this point in the protocol Alice and Bob have $2n$ bits remaining, they are in a position to sacrifice half of them to perform and integrity check against an eavesdropper. They do it by publicly comparing some of their ${x,y}$ pairs and if the perfect correlation (in reality there’d be an error rate to consider too, but let’s omit that for simplicity of the discusiion) is broken, it means that an eavesdropper tapped into the quantum communication channel between them and measured the qubits Alice sent. In such case, they would abort the protocol and retry again.

B92 implementation in Q 🔗

We shall demonstrate Q# implementation of using last post’s BB84 implementation as a foundation - I will therefore not dive into some of the helper methods that we defined previously and will simply reuse in this discussion.

Just like we did in BB84, we will allocate qubits in chunks of 16, and repeat that as “roundtrips” until we reach the required key length. The operation will have the general structure as shown below:

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

    // we want to transfer 8n + 𝛿 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 protocol execution. In our case we assume 𝛿 = 8 * chunk (32)
    let roundtrips = (8 * expectedKeyLength + 4 * chunk) / chunk;

    Message("***********");
    Message($"Running the B92 protocol for expected key length: {expectedKeyLength}");
    
    mutable aliceValues = new Bool[0]; // x values
    mutable bobValues = new Bool[0];  // y values
    mutable bobResults = new Bool[0]; // z values

    for (roundtrip in 0..roundtrips-1) {
        using (qubits = Qubit[chunk]) {
        
            // prepare Alice's qubits
            for (qubit in qubits) {
                // omitted for brevity
            }

            // eavesdropper!!!
            for (qubit in qubits) {
                // omitted for brevity
            }

            // measure Bob's qubits
            for (qubit in qubits) {
                // omitted for brevity
            }             
        }
    }
    
    // continue with the protocol, comparison
    // eavesdropper detection and so on
}

The operation will run in process of our Q# program and thus will only simulate the actual quantum key distribution between two spatially separated parties, but all the quantum paradigms with regards to qubit measurement and value encoding are still applicable. The expected length of the key is captured in the $expectedKeyLength$ variable and is used to determine the amount of roundtrips needed. As we discussed above, for a key of length $n$, we need to transfer $8n$ qubits. In this Q# code, we actually add a small buffer because at relatively small sample sizes (e.g. key length of 256), we may easily end up with not enough bits at the end, because B92 is probabilistic and even a uniform superposition may not distribute its results ideally 50-50.

We will first let Alice act upon the qubits - to encode her bits. Then Eve will get a chance to eavesdrop, and interfere with the quantum communication between Alice and Bob. And finally, Bob will perform his measurements, which will be followed by the conclusion of the protocol - comparisons and eavesdropper checks. The bit values that during the protocol discussion we named $x$, $y$ and $z$, will be kept in three arrays $aliceValues$, $bobValues$ and $bobResults$ respectively.

// prepare Alice's qubits
for (qubit in qubits) {
    // Alice chooses random bit
    let x = DrawRandomBool(0.5)
    if (x) { H(qubit); }
    set aliceValues += [x];
}

Alice chooses a random bit $x$ using the Q# function $DrawRandomBool$. If the value is $0$, she keeps the qubit as is, that is encodes the value into computational basis state $\ket{0}$. Conversely, if she generates $1$, she applies the $H$ gate to create state $\frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) = \ket{+}$. The algebraic reasons behind this should be clear - we covered them in part 2 of this series. The $x$ bits are persisted into $aliceValues$ array.

Let’s skip Eve for now and jump straight to Bob:

// measure Bob's qubits
for (qubit in qubits) {
    let y = DrawRandomBool(0.5);
    set bobValues += [y];
    let bobResult = Measure([y ? PauliX | PauliZ], [qubit]);
    // |0> or |+>  maps to a classical 0 
    // |1> or |->  maps to a classical 1
    let z = ResultAsBool(bobResult);
    set bobResults += [z];
    Reset(qubit);
}  

Bob draws a random bit $y$ as well and persists it into $bobValues$ array. He then proceeds to make a measurement - but because he doesn’t know which basis to choose, he uses the rule that we mentioned above - if $y = 0$, perform Pauli Z measurement, otherwise Pauli X. The resulting classical bit $z$ is saved into $bobResults$ array.

We can now return to Eve, to complete the first part of the protocol, one that focuses on generation and quantum communication.

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

Eve will be allowed to tap into the qubit communication between Alice and Bob based on the $eavesdropperProbability$ which is an argument on our protocol operation. $1.0$ means a certainty that she will listen in, while $0.0$ means that she’d never eavesdrop. Such arrangement - similarly to our BB84 setup, gives us a chance to replay the protocol multiple time with different eavesdropping configurations and compare the outcomes. Since Eve doesn’t know which measurement basis to use too, she will use the same mechanism as Bob to determine her basis.

In the next step Bob should publish his results $z$ (so the array $bobResults$) and Alice and Bob shall only keep their $x$ and $y$ bits, stored in $aliceValues$ and $bobValues$ arrays for which $z = 1$.

Message("Sharing Bob's results....");
mutable aliceValuesAfterBobResultsCheck = new Bool[0];
mutable bobValuesAfterBobResultsCheck = new Bool[0];

for (i in 0..Length(bobResults)-1) {
    if (bobResults[i] == true) {
        // Alice's valsue is a
        set aliceValuesAfterBobResultsCheck += [aliceValues[i]];
        // Bob's value (1 - a)
        set bobValuesAfterBobResultsCheck += [not bobValues[i]];
    }
}

Alice copies the filtered $x$ bits to $aliceValuesAfterBobResultsCheck$ array, while Bob does the same and puts his $y$ bits in $bobValuesAfterBobResultsCheck$. Since he knows that at this point $x$ and $y$ are perfectly correlated but inverses of each other, he also flips his bits to produce a (hopefully) identical bit array to Alice.

Next, Alice and Bob sacrifice half of their remaining bits to perform an eavesdropper check. This is identical to BB84 so I will not go into it - just post it for reference. It is based on an idea of picking random indices and comparing their values for any differences. In a perfect setup, ignoring errors, there should be no differences.

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(aliceValuesAfterBobResultsCheck)));
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]];
    }
}

// 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 (aliceValuesAfterBobResultsCheck[i] != bobValuesAfterBobResultsCheck[i]) {
        set differences += 1;
    }
}
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.");
}

// remove values used for eavesdropping check from comparison
let aliceKey = Exclude(eavesdropppingIndices, aliceValuesAfterBobResultsCheck);
let bobKey = Exclude(eavesdropppingIndices, bobValuesAfterBobResultsCheck);

After the eavesdropping check, Alice and Bob are left with their keys - $aliceKey$ and $bobKey$ which are identical and can be used to engage in symmetric cryptography. They should just check if the length of the key is as expect - if it’s too short, they should restart the protocol, and if it is too long, they can trim the keys. Note that they should not share those keys with anyone, after all the goal was to equip them with secrets, but for the sake of verifying that our Q# code works we can perform the comparison in Q# - to check if the keys are indeed identical.

This concludes our protocol operation:

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;

We can now invoke this operation from a regular Q# program, and as mentioned earlier, we are able to pass in different parameters into it to check how the protocol behaves. For example for a key of length $n = 256$ and without any eavesdropper, we could write:

@EntryPoint()
operation Start() : Unit {
        
    let result = RunB92Protocol(256, 0.0);

    Message("Running the protocol for 256 bit key with eavesdropping probability 0.0 resulted in " + (result ? "succcess" | "failure"));
}

Running our program like this, should produce the output similar to the one below:

***********
Running the B92 protocol for expected key length: 256
Sharing Bob's results....
Performing eavesdropping check....
Error rate: 0%
No eavesdropper detected.

Alice's key: 110111010101011000011101101001011100010000111001100101111110111001100100010000111100000011011010010011010010101110010111001100111100101100001100110001001111011100111011000011100001011111001001001001000010001010000110110110101111000011001010011100000011110111011 | key length: 261
Bob's key:   110111010101011000011101101001011100010000111001100101111110111001100100010000111100000011011010010011010010101110010111001100111100101100001100110001001111011100111011000011100001011111001001001001000010001010000110110110101111000011001010011100000011110111011 | key length: 261

Keys are equal? True

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

This is great - we can see that Alice and Bob shared successfully a private key, and confirmed that there was no eavesdropper in the process!

If we tweak some parameters now and let Eve listen in on the quantum channel between Alice and Bob, e.g. with probability 50%, Alice and Bob should be able to detect her presence by seeing discrepancies in the correlation between their $x$ and $y$ values. This is shown next.

@EntryPoint()
operation Start() : Unit {
        
    let result = RunB92Protocol(256, 0.5);

    Message("Running the protocol for 256 bit key with eavesdropping probability 0.5 resulted in " + (result ? "succcess" | "failure"));
}

And the sample program output:

***********
Running the B92 protocol for expected key length: 256
Sharing Bob's results....
Performing eavesdropping check....
Error rate: 20.72072072072072%
Eavesdropper detected! Aborting the protocol
Running the protocol for 256 bit key with eavesdropping probability 0.5 resulted in failure

This aligns with our expectations - as outlined by Bennett in B92.

Summary 🔗

B92 provides an interesting alternative to BB84 in the area of quantum key distrubtion. While the protocol is considerably simpler to reason about, there is an intrinsic inefficiency that is the price to pay for it. As we determined in last part of this seriess, in BB84 we needed to transfer (under perfect conditions) $4n$ qubits to obtain a shared key of length $n$. In B92 the need for qubits doubled, or, to put it differently, the efficiency halved - we now need $8n$ qubits to be transmitted (again, under idealized conditions) in order to achieve the required key length. This point is reiterated mutliple times in the scientific publications, for example by Abu-Ayyash and Ajlouni:

B84 probability of matching the bases is 50% from all received pulses, test for Eve takes around 50% from the matched bases which leaves only 25% to start error correction and privacy amplification. (…) B92 probability of agreeing on the bit is 25%, testing for Eve also takes 50% which leaves only 12.5% to start error correction and privacy amplification

Nevertheless, B92 equips us with yet another useful theoretical model that can be used to learn the basics and foundations of quantum computing. This concludes our discussion for today - in the next part of this series, we shall cap off our adventures in quantum key distribution by exploring the E91 protocol.