quantum key distribution (QKD)

March 13, 2021

#physics #cryptography

One of the fundamental problems in cryptography is the key exchange problem. If I've written it well, this is a post that explains a quantum solution to the problem called quantum key distribution.

caveats and pre-requisites

1. This isn't a post about quantum physcis — in particular, I'm going to handwave through the physics of electromagnetic waves. Here's a beautiful introduction if you're interested:)
2. QKD is a really interesting cryptographical protocol, but it assumes that we have an authenticated channel of communication already. The algorithm is still secure, but it won't solve the classic key distribution problem.
3. This post focuses on the algorithm, not on implementation.

broad strokes

The big idea of quantum key distribution (and quantum cryptography at large) is using the intrinsic, physical properties of quantum particles as a basis for security. This is in contrast to RSA, which relies on the computational difficulty of a certain function (namely prime factorization).

In particular, we're going to take advantage of the fact that observation of a quantum system changes the state. The very act of observing and object changes the object being observed.¹

This property will allow us to figure out if anyone has been eavesdropping on the conversation. Together with the no-cloning theorem, which says that we can't make an identical copy of an unknown quantum state, there won't be any man in the middle attacks:)

always start with the laser

This sounds cool and interesting, but how do we actually send information as quantum pieces?

We're going to start with light with a certain wavelength coming from a laser. Quantum physics tells us the light from the laser comes in discrete packets called photons, and individual photons have properties of a wave. Each photon is wiggling in a certain direction, like up/down, left/right, diagonally etc.² Taken together, the light waves in the laser are wiggling in many directions.

We're going to use the direction ("polarization" from here on out) of the light to hold our information.

When we pass a light beam through a "polarizer", it absorbs all the light not wiggling in the right direction. Pass unpolarized light from our laser through a vertical polarizer, and all the light will be wiggling in the vertical direction when it comes out. Pass this vertically polarized light through a horizontal polarizer, and none of it will get through.

Some of you might have this nagging feeling:

What does "horizontal" and "vertical" even mean? If I tilt my head to the side, does horizontal and vertical change? Why are you using arbitrary directions? And also, while I'm at it, why are we still dealing with classical stuff? Where's the quantum?

Wait, how'd my notes get here?

arbitrary and abstract fences

If we pick two orthogonal directions, we call that a basis. It's important that they're orthogonal, but otherwise the choice is arbitrary. Let's say (humour me here) that we pick the horizontal/vertical basis. Then we can describe light polarized in any direction as a superposition of the horizontal state and vertical state.

Some piece of the wave is wiggling in the horizontal direction, and the other is wiggling in the vertical direction.³

Clasically, we'd imagine that when this light enters a vertical polarizer, it loses the horizontal component of the wave, so we get

So, for example, if we shine a laser that is 45° (diagonal) polarized through a vertical polarizer, it will lose half its intensity and come out vertically polarized. The same thing will happen if we put light that is vertically polarized through a diagonal polarizer.

However, quantum mechanics tells us that light arrives in discrete photons. If we shoot a single photon (not a beam) that's diagonally polarized through a vertical polarizer, what happens? We can't divide it, since it is the minimum measure amount of energy.

Here's where the quantum weirdness happens: the photon will either pass through and become vertically polarized (but with the same energy), or it'll get completely absorbed by the polarizer. It does either of those two things with equal probability.

What's going on here?

Before the photon hits the vertical polarizer, it's on the fence between horizontally and vertically polarized. The polarizer forces it to choose one way or another. If it chooses horizontal, it gets absorbed. If it chooses vertical, then it passes through no problem.

Using our superposition notation: $\Ket{\psi} = \cos(45^{\circ})\Ket{x} + \sin(45^{\circ})\Ket{y}.$ Once the photon passes through the polarizer, the superposition collapses (also called state-vector collapse or wave function collapse) into either $\Ket{x}$ or $\Ket{y}$.

The same thing happens if we rotate everything 45°. Let's say our original photon was vertically polarized and it's going to pass through a diagonal polarizer. Our photon starts as: $\Ket{\psi} = \cos(45^{\circ})\Ket{\nearrow} + \sin(45^{\circ})\Ket{\nwarrow}.$ Same deal: the photon will pass with a probability of $1/2$, and if it passes it'll be diagonally polarized.

As a last

fine strokes

We've got all the conceptual pieces we need to understand QKD. Here's how we'll represent 1s and 0s:

Basis	0	1
$+$	$\rightarrow$	$\uparrow$
$\times$	$\nearrow$	$\nwarrow$

This means that a horizontally polarized photon is 0 in what's called the "rectilinear" basis. To measure this, we use a vertical polarizer. If the photon doesn't get through, a horizontal polarization is measured. If it gets through, a vertical polarization is measured. If we try to measure a diagonal photon in a rectilinear basis, our results will be 50/50.

Of course, we'll use Alice and Bob to represent the parties in the communication. I don't think anyone else has anything important enough to say anyway.

1. Alice flips a coin to choose a bit $(T=0, H=1)$ and flips it again to choose a basis $(T=+, H=\times)$ to encode it. She records both of these things (secretly) and transmits the photon containing the bit.
2. Bob doesn't know what basis Alice encoded the photon in, so he flips a coin to pick a basis to measure it. He records the basis and polarization he measured.
3. Repeat $n$ times
4. Alice and Bob publicly compare the bases (plural of basis) they used to send/measure the photons. They both discard the bits where they don't match, and they're left with the key they both share.

That's it! Let's take an example:

Alice's random bit	1	1	1	0	1	1	0	0
Alice's random basis	$+$	$+$	$\times$	$+$	$+$	$\times$	$+$	$+$
What Alice sends	$\uparrow$	$\uparrow$	$\nwarrow$	$\rightarrow$	$\uparrow$	$\nwarrow$	$\rightarrow$	$\rightarrow$
Bill's random measuring basis	$+$	$+$	$+$	$+$	$+$	$\times$	$\times$	$\times$
What Bill measures	$\uparrow$	$\uparrow$	$\rightarrow$	$\rightarrow$	$\uparrow$	$\nwarrow$	$\nearrow$	$\nearrow$

They publicly discuss (in a classical channel) which basis they sent/measured the photons in. This is why the classical channel needs to be authenticated: Alice and Bob need to know that the other person is who they say they are. Even if an eavesdropper (Eve) is listening to this discussion, it doesn't provide any information as to what the key is. They throw away any bits where the basis is different, so they're left with 11011.

You might be wondering about the feasibility of throwing away so many bits. Assuming that Alice and Bob both choose the basis randomly with $P=1/2$, then they'll have to throw away half their bits on average. That means to get a 64-bit key, they'll have to send 128 bits.⁴

press e to eavesdrop

What happens if Eve tries to listen to the quantum channel?

Here's where the quantum security comes in. Eve, like Bob, doesn't know what basis Alice sent the photon in. The no-cloning theorem means that she can't clone the photon and store it, so the best she can do is pick a random basis, measure the photon, and send what she measured to Bob. Let's see what happens:

Alice's random bit	1	1	1	0	1	1	0	0
Alice's random basis	$+$	$+$	$\times$	$+$	$+$	$\times$	$+$	$+$
What Alice sends	$\uparrow$	$\uparrow$	$\nwarrow$	$\rightarrow$	$\uparrow$	$\nwarrow$	$\rightarrow$	$\rightarrow$
Eve's random measuring basis	$+$	$+$	$\times$	$\color{red}\times$	$\color{red}\times$	$\times$	$\times$	$\times$
What Eve measures and sends	$\uparrow$	$\uparrow$	$\nwarrow$	$\color{red}\nwarrow$	$\color{red}\nearrow$	$\nwarrow$	$\nearrow$	$\nwarrow$
Bill's random measuring basis	$+$	$+$	$+$	$+$	$+$	$\times$	$\times$	$\times$
What Bill measures	$\uparrow$	$\uparrow$	$\rightarrow$	$\color{red}\uparrow$	$\color{red}\rightarrow$	$\nwarrow$	$\nearrow$	$\nwarrow$

After Alice and Bob discard the bits where they used a different basis, Alice will have 11011 but Bob will have 11101. By choosing a set of $p$ bits to compare (and throw away) beforehand,⁵ they can catch an eavesdropping attempt.

An important nuance is that Eve might choose right sometimes. The first 2 bits don't have any errors, even though Eve tampered with them. What's the probability that Alice and Bob will be able to catch Eve by comparing $p$ bits?

For Alice and Bob to not notice anything, one of two things could happen. We only consider the bits where Alice and Bob have the same Either Eve chooses the right basis $(P=1/2)$, in which case there'll be no error, or Eve could choose the wrong basis $(P=1/2)$ but Bob still measures the right bit $(P=1/2)$. These two cases are mutually exclusive, so for a given bit we get

That means if Alice and Bob compare $p$ bits, they'll catch Eve with

With just $11$ bits to compare, the probability is $96\%$. With $17$, it's $99\%$. With $64$, it's $99.99999899\%$. Pick a benchmark and you can probably hit it without too much trouble:)

a brief discussion of implementation

This isn't a post about implementation, but I'd be amiss not to explain something. We used polarized photons here, but some implementations encode the information as phase encoded states instead; any two pairs of conjugate states work. There are other pieces to algorithm, like "information reconciliation" and "privacy amplification" and "read the wikipedia article". Hey, how'd my notes get in here again?

the briefest of closings

I hope this post did justice to this topic. Quantum physics is, as you might expect, more complicated than I have the ability to explain yet. Be that as it may, I hope I was at least able to give you an appreciation for the big ideas behind why quantum cryptography (and quantum information science) is exciting!

Footnotes

1. By the way, the "observer" doesn't have to be conscious. Polarizers are a good example — they are "observing" the light passing through. ↩

2. This is the hand-wavey bit. Electromagnetic waves (as described by Maxwell's equations) oscillate in two orthogonal directions, with the electric field and magentic field perpendicular to each other. When I say that light is wiggling vertically, it's referring to the direction of osciallation of the electric field. ↩

3. This is the quantum version of $\hat{\imath}$ notation. It uses state vectors instead of unit vectors. I haven't found any convincing reason as to why yet, but it's probably out there if you search. ↩

4. The distribution of the number of bits they can keep is binomial. If they transmit 256 bits, they'll get at least 64 bits almost every time. My graphing calculator just says the probability is 100%, and it has 6 decimal places of precision. ↩

5. How do they choose which bits to compare? They can just publicly decide to compare the first $p$ bits where they used the same basis. Eve doesn't know which bits those will be (since Bob chooses his basis randomly) so she can't strategically evade detection. ↩