Quantum Key Distribution, BB84 Protocol

Table of Contents

1. Quantum Key Distribution
2. BB84 Protocol

Quantum Key Distribution

How can two parties communicate securely in public? The problem of encrypted communication has been researched since the mid-1970s, but has become especially relevant with the internet.

Despite being a public channel open to the entire world, secure communication is what keeps the internet functioning, from encrypted messages to transporting credit card or other sensitive information.

To understand a bit of the basics of cryptographic communication, let's start by going over Diffie–Hellman key exchange, a simple cryptographic protocol. Diffie–Hellman, like most other widely used cryptographic protocols, relies on both public keys and private keys.

Classical asymmetric cryptographic protocols are created such that the private keys can be easily verified using the public keys, but it is computationally hard to obtain the private keys from just the public keys. Sound familiar?

Anyway, to set up Diffie–Hellman, Alice and Bob first publicly agree to use a modulus $p$ and base $g$.¹ Alice has a private key $a$ and Bob has a private key $b$. Alice sends Bob her public key $A=g^a \bmod p$, and Bob sends Alice his public key $B=g^b \bmod p$.

Then, Alice can compute $s=B^a \bmod p$ and Bob can compute $s=A^b \bmod p$, and the result will always be equal since we know that

This secret $s$ can now be used to verify messages, with the guarantee that the initial agreement of $s$ cannot be intercepted by an intruder.

That is, unless someone could figure out the solution to $g^{ab} \bmod p = g^{ba} \bmod p$ only knowing $p$, $g$, $g^a \bmod p$, and $g^b \bmod p$.

It turns out that you can do this efficiently using a quantum computer with the period-finding scheme for Shor's algorithm. The trick is using a bivariate function. If we let $y=g^k$, we can let $f(x_1,x_2)=g^{x_1} y^{x_2}$.

We can then use the period-finding algorithm to find a pair $(\omega_1, \omega_2)$ such that $f(x_1+\omega_1, x_2+\omega_2)=f(x_1,x_2)$. If we let $q=p-1$ be the period of $y$, this means that $\omega_1+k\omega_2 \equiv 0 \, (\bmod \, q)$. There are $q$ pairs that produce this result: one is $(0,0)$, which won't help us, but any of the other $q-1$ pairs will give us $k=-\omega_1/\omega_2 \bmod q$, which will be one of the private keys $a$ or $b$. We can then easily derive the other one.

Don't worry if you didn't get all of that. Many period-finding applications are more complicated than Shor's algorithm, and can involve multiple dimensions. I just wanted to show this example to illustrate that period-finding can have a wide range of uses, particularly in cryptography.

But if most classical encryption schemes rely on the hardness of period-finding, how can we communicate securely? This is where quantum key distribution comes in.

I want to preface our discussion by saying that there are two big disadvantages to quantum key distribution.

The first is that Alice and Bob need a quantum channel to communicate with. The most common physical channel that would work is an optical fiber, but without an amplifier, like most in the ground have today, since it would destroy quantum coherence.

The second is that Alice and Bob need a pre-authenticated classical channel, i.e. a channel where they already share a secret and can send messages without the chance of hijacking. This condition is the reason that QKD is not the solution to Shor's algorithm breaking classical encryption.²

These restrictions seem tough. But the advantage is that over the quantum channel, the eavesdropper, Eve, can try to do whatever she wants in accordance with the laws of physics to try to find Alice and Bob's private keys and will not be successful. The lack of reliance on a computationally hard problem, which could be broken by Shor's algorithm or some other clever algorithm discovered in the future, is what makes quantum key distribution interesting.

BB84 Protocol

Let's discuss the most simple QKD protocol, known as BB84. Suppose that Alice wants to send a private key to Bob. She starts by creating two bitstrings of length $n$, which we'll call $a$ and $b$. She then creates the quantum state

where $a_i$ and $b_i$ are the $i$-th bits of $a$ and $b$ respectively, and $|\psi_{00}\rangle=|0\rangle$, $|\psi_{10}\rangle=|1\rangle$, $|\psi_{01}\rangle=|+\rangle$, and $|\psi_{11}\rangle=|-\rangle$.

Notice that $b_i$ decides whether the quantum state is in the computational basis or the Hadamard basis. That means if Eve were to intercept this quantum state as it was being sent to Bob, she wouldn't be able to deduce any meaningful information about it without knowing the dictionary of bases $b$ that each qubit was measured in.

When Alice sends $|\psi\rangle$ over the quantum channel $\mathcal{E}$, Bob will receive a potentially intercepted and/or noisy state $\mathcal{E}(|\psi\rangle\langle\psi|)$. If Eve has intercepted this state, she can't do anything with it without measuring the state. If she measures any qubit in the wrong basis, Alice and Bob will be able to tell that the state has been affected. So we can be sure that the state is safe from interception.

Once Bob receives Alice's quantum state, he generates a string of $n$ random bits $b'$ and then measures Alice's quantum state, with the basis he measures each qubit in in depending on the value of each bit in $b'$, resulting in a bitstring $a'$. Bob then announces that he has received Alice's message and Alice publishes $b$. We know that she can safely do this since the state has been measured by Bob, i.e. the quantum information cannot be restored.

Now, Bob use the secure classical channel to share $b'$ with Alice, and Alice and Bob discard each bit $a_i$ and $a'_i$ respectively where $b_i \neq b'_i$. They then take a few of the remaining qubits and confirm that they match to ensure that Eve didn't measure anything, and then the rest of the qubits can form their secret key.

Let's go over an example for $n=11$. Suppose that Alice starts with $a=01000111100$ and $b=00110110000$, which means that her quantum state is

Bob then generates the random $b'=00011010100$ and measures

Alice then announces $b$, and Bob shares $b'$ in thier classical channel, leaving them both with the shorter bitstring $\text{01+−100}$. Now, let's say they choose the second, third, and sixth terms to verify. Once they see that they are equal, they are left with the string $\text{0−10}$, which can be converted to a classical bitstring $0110$ by deciding to set $+$ to $0$ and $−$ to $1$.

That's all there is to it! Using BB84, Alice and Bob have shared a secret key in a way that does not rely on the hardness of some mathematical problem, but rather on the laws of physics.

The problem that remains, though, is quantum noise. Alice and Bob would either need to use a highly fault-tolerant quantum channel or quantum error correction to protect their transmissions from noise. Effective fault-tolerant quantum computing and implementable quantum error correction schemes are widely considered to be pretty far off.

There are more sophisticated QKD protocols, but I just wanted to give a taste of the vast field of quantum cryptography. I encourage you to look into more protocols and try to implement them.³

1. I am omitting a bit of important information here. When I say that $g$ is a base, I mean that $g$ is a primitive root modulo $p$, i.e. the period of $f(k)=g^k \bmod p$ is $q=p-1$. More broadly, this scheme is often presented using the terminology of group theory, but I am trying to simplify it a bit for those without abstract algebra experience.

2. For a description of an encryption scheme that is believed to be resistant to Shor's algorithm, see this week's addendum.

3. And I welcome you to tell me about them! QKD is probably the widely-known quantum algorithm I am the least familiar with. Despite my computer science background, most of my quantum computing experience has been in Hamiltonian simulation, which hasn't seemed to have much overlap with it. I am always interested in learning more about quantum cryptography!