In the last two posts we covered quantum key exchange using the B92 and BB84 protocols. Both of those depended with their security on the no-cloning theorem. Today we are going to dedicate a third post to the topic of quantum key distribution, and this time around we will explore a variant of key distribution relying on the phenomenon of entanglement and quantum correlations.

Background & theory 🔗

At first glance, entanglement seems to be perfectly suited for distributing encryption keys. Thanks to entanglement, two parties could share a set of maximally entangled particle pair, each one making up a Bell state (EPR pairs), and then, provided no decoherence effects happened and the entanglement remains stable, be guaranteed that upon their respective measurements, they will receive identical results. This is something we already covered extensively in our earlier parts on entanglement.

The first to realize how useful entanglement could be for quantum key distribution was Artur Ekert from Oxford University, who in 1991 published a paper titled Quantum Cryptography Based on Bell’s Theorem. Ekert wrote:

In the following I describe a quantum channel which distributes the key without any “element of reality” associated with the key and which is protected by the completeness of quantum mechanics.

The major issue with protocols like BB84 or B92 is that the engaged parties need to open a quantum communication channel between them - after all, the qubits (particles) need to travel from one participant to the other as part of the protocol. This, naturally, creates a possible attack vector, as the eavesdropper might tap into that communication channel. With EPR pairs it is possible to avoid that altogether, if the entangled pairs are created by Alice and Bob together, when they were physically located together at some point in the past.

On top of that, with entanglement-based approach to quantum key distribution, there is no need to pre-create any classical data first - which is the case in both BB84 and B92 protocols, as those protocls encode classical data into qubits. Instead, in EPR quantum key schemes, the classical bits $0$ and $1$ are equally probable to emerge upon measurement carried out by one of the parties engaged in the protocol. This provides us with a further security feature - the created key is truly random, as guaranteed by the laws of nature, which is critical for the fidelity of the cryptographical activities. A different way of looking at it is - since the key effectively does not exist (until the two participants engage in the measurement process), the eavesdropper cannot steal it - and that is the ingenious idea behind using EPR pairs for quantum key distribution and something that Ekert pointed out in his original paper:

The eavesdropper cannot elicit any information from the particles while in transit from the source to the legitimate users, simply because there is no information encoded there. The information “comes into being” only after the legitimate users perform measurements and communicate in public afterwards.

To rephrase this, the idea of Ekert was simple. He suggested using maximally entangled states as tools to generate the shared key - and argued that since there is no key encoded in the qubits making up the EPR pairs, then there is nothing for the eavesdropper to steal. It is still possible for the eavesdropper to inject their own qubit into the process and trick the engaged parties this way (e.g. upon the EPR pair creation), but Ekert proposed to use Bell’s inequality test against that.

There is an additional benefit of using the entanglement based key distribution protocols such as the Ekert protocol, one that is of great significance when it comes to real life implementations. Namely, it lends itself very well to the concept of quantum privacy amplification, introduced in 1996 by Deutsch, Jozsa, Ekert, et al in the Quantum privacy amplification and the security of quantum cryptography over noisy channels paper - which in turn improves its performance and resistance to noise. As Bruß and Lütkenhaus observed in their paper reviewing various QKD protocols, Quantum Key Distribution: from Principles to Practicalities:

(…) by storing the states at both ends of the transmission line and coherent manipulation on each side between the accumulated states the performance of the key distribution could be enhanced. This technique is called quantum privacy amplification and effectively gives a new, shorter key with lower error rate.

Protocol steps 🔗

There are several variants of the EPR based protocol for quantum key distribution. In this post we will cover a simple version described by N. Yanofsky and M. Mannucci in their Quantum Computing for Computer Scientists book. That variant doesn’t require a Bell’s inequality test - something we have not covered yet in this series - and contrary to Ekert’s original paper, involves only two orthogonal bases, instead of three, thus simplifying the entire reasoning.

Let’s suppose that Alice and Bob start with a set of entangled qubits, each one holding one of the qubits, with each pair forming the Bell state $\ket{\Phi^+}$.

$$\ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$$

As we already determined in part 5 of this series, such a system with two maximally entangled pairs guarantees that if one of the qubits is measured to have the classical result $0$, the other will be guaranteed to be the same. On the other hand, if, which is equally probably to receiving a $0$, the measurement of one of them produces a classical $1$, the other will also follow. Thus, a set of such entangled EPR pairs will upon measurement equip both participants with identical classical bit sequences even if the parties are spatially separated.

In this version of the EPR QKD protocol, just like it was the case in BB84, Alice and Bob will utilize two bases for measurement - Pauli Z basis ${\ket{0}$,$\ket{1}}$ and Pauli X basis ${\ket{+}$,$\ket{-}}$. They are each randomly choosing between those two bases, as they work through their half of the entangled pair, each one independently measuring. If they choose the same basis, they will get perfectly correlated results, in other words - they will get the same classical bit value. If they do not agree on a basis, they will get different results. To better illustrate this, imagine if Alice chose ${\ket{0}$,$\ket{1}}$ basis and measured $\ket{0}$. If Bob chooses the same basis, he will get $\ket{0}$ with certainty. But if he chooses the ${\ket{+}$,$\ket{-}}$ basis, he will only get the same result as Alice 50% of the time because $\ket{0} = \frac{1}{\sqrt{2}}(\ket{+} + \ket{-})$.

In the next step, again, just like in BB84, Alice and Bob publicly compare the bases they randomly chose - they can do this over a public channel. They need to discard all the qubits for which they did not agree on the basis choice. Note that statistically, this should mean that they will discount about 50% of their qubits. The remaining qubits now form a key that they share between each other - it’s just that they are not necessarily forming a secret key yet.

In order to verify if their key is really secret, and to determine if any of the EPR pairs has not been tampered with, Alice and Bob they need to perform an eavesdropper check. Now, we already discussed that the possibility of eavesdropper’s interference in EPR QKD scheme is different from that in BB84 or B92 - as there is nothing to listen on once Alice and Bob are in the possession of their halves of the EPR pairs. However, theoretically, eavesdropper could have tampered with the pairs before Alice and Bob got in their possession - in other words Eve could have impersonated a truthful source responsible for producing the entangled pairs in the first place. Therefore, to be certain, similarly to BB84, Alice and Bob should sacrifice half of their remaining bits and compare them publicly. Since they agreed on the basis, they should have the same results 100% of time. This is of course assuming the perfect conditions and ignoring the disentangled pairs, as in reality a small number would have resulted in discrepancies due to environment noise. However, if the eavesdropper - Eve - interfered with any of the EPR pairs, then she must have attempted to guess the measurement basis too. Using the reasoning from above, this of course impacts the correlations that Alice and Bob expect to see for the pairs they measured in the same basis. If the discrepancy rate is higher than the acceptable error rate, Alice and Bob would determine that the eavesdropper presence was indeed dangerous and they should abort the protocol and restart with a new set of entangled particles.

EPR QKD implementation in Q 🔗

Let’s now go through a simple illustrative implementation of the EPR quantum key distribution in Q#. We will use the material from the previous two posts - about BB84 and B92 as the foundational work and avoid re-discussing some of the repeated snippets of code. This will save time and space, especially as we’ll use a few of them, mainly in the area of eavesdropper check, which will be identical to that of BB84. In case anything becomes unclear, I recommend you have a look at those two preceding posts again.

Just like with all our quantum key distribution examples, there will be no physical key distribution going on - instead we will simulate everything in a single Q# process. We start off by defining a Q# operation that we will use to test different configurations of the EPR QKD - with parameterized probability of eavesdropper participation and the length of the key. This is similar to our approach to BB84 and B92 in previous posts, and allows us to quickly compare and contrasts different situations from a single program execution.

operation RunEPRQKDProtocol(expectedKeyLength : Int, eavesdropperProbability : Double) : Bool {
    Message("***********");
    Message($"Running the EPR QKD protocol for expected key length: {expectedKeyLength}");
    
    mutable aliceResults = new Bool[0];
    mutable aliceBases = new Bool[0];

    mutable bobResults = new Bool[0];
    mutable bobBases = new Bool[0];
    
    // to do
}

We already know that we will need to keep track of Alice’s and Bob’s bases and classical measurement results, so we can already initialize the necessary empty arrays.

In the next step, for a key of length $n$, we will create $4n + \delta$ EPR pairs and let both Alice and Bob measure them. In principle a key of length $4n$ should suffice, as we will halve it twice (once throwing away the bases upon which Bob and Alice didn’t agree, and once for eavesdropper check), but at these relatively small sample sizes we may easily end up with too few bits in the end, so the $\delta$ gives us a small safety buffer. We learnt in part 5 of the series that we can create $\ket{\Phi^+}$ state by chaining $H$ and $CNOT$ gates, which is exactly what we do in the Q# code.

Since we already mentioned that the most realistic chance for the eavesdropper to meddle in the EPR quantum key distribution protocol is to tamper with the entangled qubits before Alice and Bob get their hands on them, we allow Eve to measure Bob’s qubit based on the passed in $eavesdropperProbability$.

for (i in 0..(4 * expectedKeyLength + 64)) {
    using ((aliceQubit, bobQubit) = (Qubit(), Qubit())) {

        // create entanglement between aliceQubit and bobQubit
        H(aliceQubit);
        CNOT(aliceQubit, bobQubit);

        // determine if eavesdropper should jump in
        // if so, let Eve interact with the qubit of Bob
        let shouldEavesdrop = DrawRandomBool(eavesdropperProbability);
        if (shouldEavesdrop) {
            let eveBasisSelected = DrawRandomBool(0.5);
            let eveResult = Measure([eveBasisSelected ? PauliX | PauliZ], [bobQubit]);
        }

        // Alice and Bob choose a random basis by drawing a random bit
        // 0 will represent {|0>,|1>} computational (PauliZ) basis
        // 1 will represent {|->,|+>} Hadamard (PauliX) basis
        let (aliceBase, aliceResult) = MeasureInRandomBasis(aliceQubit);
        set aliceBases += [aliceBase == PauliX];
        set aliceResults += [aliceResult];

        let (bobBase, bobResult) = MeasureInRandomBasis(bobQubit);
        set bobBases += [bobBase == PauliX];
        set bobResults += [bobResult];
    }
}

For both Alice and Bob, we use a helper operation $MeasureInRandomBasis(qubit : Qubit)$ which is shown next:

operation MeasureInRandomBasis(qubit : Qubit) : (Pauli, Bool) {
    let basisSelected = DrawRandomBool(0.5) ? PauliX | PauliZ;
    let aliceResult = Measure([basisSelected], [qubit]);
    let classicalResult = ResultAsBool(aliceResult);
    Reset(qubit);
    return (basisSelected, classicalResult);
}

The operation randomly chooses a basis - Pauli Z basis ${\ket{0}$,$\ket{1}}$ and Pauli X basis ${\ket{+}$,$\ket{-}}$ - based on the result of $DrawRandomBool(0.5)$ invocation, measures the qubit accordingly, resets it and then returns the chosen basis, together with the classical bit result, in a tuple. Those bases and classical results are then saved in the appropriate arrays we prepared in the beginning.

The next step of the protocol is for Bob and Alice to compare the bases they chose, and only keep the ones they agreed upon. They do not need to (and should not!) publicly share their results though. This is identical step to the comparison step in BB84. Assuming we started with about $4n$ EPR pairs, we should be down about $2n$ classical bit results now.

mutable aliceResultsAfterBasisComparison = new Bool[0];
mutable bobResultsAfterBasisComparison = new Bool[0];

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

What follows next, should be the check for the eavesdropper’s evil interference. To do that, as explained earlier, Alice and Bob sacrifice half of their current bits (thus bringing the remaining secret bits to around $n$). The check is identical to that we performed earlier in BB84 and B92, so I will not dive into it anymore - we will list it only for reference and completeness sake.

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(aliceResultsAfterBasisComparison)));
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
    if (aliceResultsAfterBasisComparison[i] != bobResultsAfterBasisComparison[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");
    Message("");
    return false;
} else {
    Message($"No eavesdropper detected.");
}

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

At this point, unless a disruptive presence of Eve was detected, Alice and Bob share a secret key. If we managed to successfully reach this point, it will likely be too long, so we should trim it to the expected length $n$.

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

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 shared key: {BoolArrayToString(trimmedKey)}");

return true;

Similarly to the earlier posts, we use a helper method $BoolArrayToString(array : Bool[])$ to conveniently print out the contents of a bit array to the console. And that’s really everything - the protocol is complete. We can invoke the operation using an entry point now. For example, if the eavesdropper is certain to be present, this would be done in the following way:

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

This code should produce output similar to the one below.

***********
Running the EPR QKD protocol for expected key length: 256
Performing eavesdropping check....
Error rate: 23.75%
Eavesdropper detected! Aborting the protocol

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

Conversely, if we switch off the eavesdropper, the protocol should succeed.

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

In this case the output (with the truly random key) should resemble the following.

***********
Running the EPR QKD protocol for expected key length: 256
Performing eavesdropping check....
Error rate: 0%
No eavesdropper detected.

Alice's key: 111011101110110101110000110110101111101001111001010111111001110101010101111011001101110010101111011011111000110001011011101100111011100101110110100011101001000010111010010100000001100001001100111100010011000101111110111010010100100011000011010010101001011011001110100010110011000011100000100000011110011101110101111 | key length: 315
Bob's key:   111011101110110101110000110110101111101001111001010111111001110101010101111011001101110010101111011011111000110001011011101100111011100101110110100011101001000010111010010100000001100001001100111100010011000101111110111010010100100011000011010010101001011011001110100010110011000011100000100000011110011101110101111 | key length: 315


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

Summary 🔗

Quantum key distribution using EPR pairs is an exciting and theoretically very secure approach to enhancing classical cryptography thanks to quantum computing. Once the initial entangled EPR pairs are distributed, it could be used over very long distances as it doesn’t require a quantum communication channel to be present between the engaged parties. The absence of “element of reality”, as Ekert put it, makes it very immune to eavesdroppers too. At the same time, unfortunately, it relies on the stability of the entangled particles, something that we are currently not in a position to achieve at the commercial scale. As Rieffel and Polak observe:

This protocol has the intriguing property that in theory Alice and Bob can prepare shared keys as they need them, never needing to store keys for any length of time. In practice, to prepare keys on an as-needed basis in this way, Alice and Bob would need to be able to store their EPR pairs so that they are not corrupted during that time. The capability of long-term reliable storage of entangled states does not exist at present.

This concludes our three-part mini series on quantum key distribution. In the next part of this series, we will start looking at some quantum algorithms!