Introduction to Quantum Cryptography


In 1943, Admiral Isoroku Yamamoto, the greatest military commander of the Japanese navy, went to visit one of the front line bases to boost morale. The plan of his visit was communicated through an encoded message through the Japanese Naval Cipher JN-25D, a code that was believed to be unbreakable at the time. US naval intelligence intercepted and decrypted the message, and by the time Yamamoto’s plane approached the base, allied P-38 Lightning aircrafts appeared. Codebreakers took down one of the greatest Japanese commanders, the architect behind Pearl Harbor.

There has always been an endless battle between code-makers and code-breakers, developed by some of the brightest minds in history. The holy grail of cryptography has been to develop an encryption method that is absolutely secure, cannot be copied and unlimited computation power. This goal was partially achieved in 1973, when Gilbert Vernam developed the One-Time-Pad (OTP) encryption. The OTP is an encryption algorithm where the text is encoded with a secret key, which has the same length as the original message. The OTP has been proven to have absolute security by Claude Shannon [Shannon, C. E., ―Communication theory of secrecy systems‖, Bell Syst. Tech. J., 28, pp.656-715, 1949.], since the random key is only used once. And here lies the drawbacks, once the key is used up, then you need another one. Also, in classical physics, sending a key over an insecure channel leaves you vulnerable for eavesdroppers to copy it. If Alice and Bob send a key to each other through such an insecure channel, then they cannot prove if Eve has made a copy of it or not.

[Source: A brief introduction of quantum cryptography for engineers Bing Qi, Li Qian, Hoi-Kwong Lo]

Classical Cryptography vs Quantum Cryptography

Classical cryptography relies mainly on mathematical algorithms, where the algorithms are based on the fact that it is easy to multiply very large prime numbers, but extremely hard to perform prime factorization to find the primes. These primes are the key to the encryption and decryption of a transmission, which means to eavesdrop on a transmission, you need to find the prime factorization of the key. The prime factors are over a hundred digits long!

The security of classical cryptography is in general based on unproven mathematical assumptions that there is no efficient way to find the prime factors of a large integer. This assumption has not been proven by mathematicians, even though there have been tremendous efforts to prove it. Quantum cryptography, on the other hand, is when information is transmitted on an atomic level through photons, and the security of quantum cryptography is based on the laws of quantum mechanics [https://arxiv.org/ftp/arxiv/papers/1002/1002.1237.pdf].

A problem with classical cryptography is that even though a lot of today’s encryption are considered secure, they can be copied and cracked by quantum computers in the future. We’re not going to get too far into the details of a quantum computer, but here’s a short explanation.

 Quantum Computing

Classical computers encodes data that can only be 0 or 1, while a quantum computer can encode data as a superposition of multiple states. If we think of four classical bits, they can be in one of 2^4, or 16, different combinations at a time:

0001 – 0010 – 0011 – and so on.

Four quantum bits, or qubits, in superposition can be in all those 16 combinations at the same time. This scales exponentially, where 20 qubits can store about a million values in parallel (2^20 = 1048576). This is because a bit of data could be represented by a single atom that is in one of two states, |0> and |1>. The two states could represent two energy levels of an atom, meaning |0> is the ground state, and |1> is the excited state. One single qubit could be the superposition of two states:

|Ψ> = α|0> + β|1>

Where α and β are the probability of the superposition collapsing to either |0> or |1> when you measure it.

These qubits are connected through something called entanglement. Entanglement is a close connection that makes each of the qubits react to a change in the other qubits state instantaneously, no matter how far they are a part.

Quantum Entanglement – Source

This means that when you measure just one entangled qubit, you can directly deduce the properties of it’s connected qubits too. We’re not going to go further into quantum computing, but there are lots of good video lectures online.

The implication of a quantum computer is that modern algorithms that would take so much computing power, it could even take longer than the lifetime of the universe to break them (some algorithms, not all). The same algorithm on a quantum computer, however, would drastically reduce this time, and rendered practically useless. Quantum algorithms would need about the square root of the time that a classical algorithm would need to compute. This is a very simplified explanation, but still gives you the right feel for what is at stake here.

Back to Cryptography

The only secure way around the problem with insecure proof of the algorithms in classical cryptography is through the OTP (One-Time-Pad), which was brought up in the introduction and has a few drawbacks. Especially the case of only being able to be used once is a huge limitation for the OTP. A need for a repeatable secure encryption method is needed. Quantum cryptography solves this key distribution problem by exploiting the properties of a quantum particle.

A single photon can represent a qubit. To find out the value of a qubit, one needs to measure the property of the photon, such as the polarization of it. Now this is where it gets tricky, when you measure the properties of a photon, the photon may alter its property (To the advanced reader: this is a simplification for the scope of this post). This makes it much harder for anyone trying to eavesdrop on the transmission, since both sender and receiver can detect the changes caused by the measurement. If Eve tries to measure or copy the key, Alice and Bob will have obtained different values for the qubits when they compare them and can discard the qubit. More on this later.

Qubit

So in regards to cryptography, what’s the difference between a bit and a qubit? Well, if we think in terms of classical cryptography, all information is reduced to 1’s and 0’s (bits) for sending and receiving, while qubits behave a bit different when you send and receive.

In classical cryptography, the value of the key is always the same, no matter how you read it, which is not the case for quantum cryptography. There the value of the bit depends on how you measure the qubit value. In order to get the right value, you also need to measure the qubit in the correct way. We know, this seems a bit abstract, but it will become clearer soon. If we measure a qubit in a wrong way, the information we get could be destroyed or get a random bit value.

To send a qubit, we send a photon through a polarizer, as you can see in the image below, to get the desired polarization. If we use horizontal polarizer, we will send a horizontal polarized photon.

And if we try to detect with the wrong polarizer, i.e. a horizontal polarized photon with a vertical beamsplitter:

We will get the wrong answer every time. If we try to detect a photon oriented at +45°, we will detect the photon 50% of the time.

A more detailed example of this last case is coming up soon.

To conclude, Bob will detect the photon using a beamsplitter that can detect the basis, which is the two different quantum states (horizontal and vertical, or 0’s and 1’s)

The beamsplitter only separates between orthogonal polarizations, meaning two polarizations that are perpendicular to each other (horizontal and vertical). This means that the polarizations can only be oriented (+45° or -45°) to a different angle (in reference to the coordinate system), if both parties, Alice and Bob, use pre-defined reference coordinate system. Meaning, they both agree beforehand to orient their beamsplitters.

Let’s look at this again through some examples. First, we want to generate a photon with a given polarization (a qubit) like horizontal:

Source

Then we want to detect it using a correct beamsplitter that both Alice and Bob knows about:

When the horizontal polarized photon passes through a horizontally-vertically oriented beamsplitter, it will be detected going through the exit of the horizontal split. If you we try to detect the incoming photon through a wrong beamsplitter, the measurement of the polarized photon will change polarization, and will exit the beamsplitter at 50% probability of the two exits of the beamsplitter.

This is a great advantage with quantum cryptography, since copying a qubit may give you a random value and damaging the information stored in the qubit, so that the polarized photon that Alice sends to Bob is not the same. To summarize in a simple way: to read a qubit can only be right when you pick the right beamsplitter, and cannot be copied by Eve without detection, because if Eve picks the wrong beamsplitter – meaning an “X” instead of a “+” – Eve will have a 50/50 chance to get the right value. For proof, please refer to “W. K. Wootters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299:802, 1982». Therefore, qubits can be used to distribute a key from sender to recipient without the possibility for the eavesdropper to obtain a copy without being discovered.

Let’s take a step back and look a bit closer behind the technology of such a quantum communication, before we delve further into the cryptography. In the setup for quantum cryptography, you need three main things:

  • Single photon sources
  • Single photon detectors
  • A quantum channel for transmission.

Of course, you need more devices, but the rest are more standard components within electronics and telecommunications.

Single Photon Sources and Detectors

The single photons that Alice emits towards Bob are typically generated from a semiconductor laser, where the laser pulses are attenuated in such a way that you have no more than one photon per pulse. This is one of the main disadvantages with quantum cryptography, since it’s actually quite hard to generate less than two photons per pulse. If Alice happens to emit two or more photons, Eve could copy one of the photons and let the rest pass to Bob, this decreases the secret key rate.  Also, there are more problems with single photon sources, which you can find here.

A typical detector would be a semiconductor detector. It works by absorbing a single photon in the detector, which excites neighboring electrons in the lattice, which again causes an avalanche of electrons to be excited. This avalanche is detected by the detector. A drawback of this method, though, is that a similar avalanche could also occur without a photon, through a case such as thermal excitation.

So how do we send the keys from Alice to Bob? We need a Quantum key distribution channel, or simply a quantum channel. An example of this would be optical fibers. Here the drawbacks are the transmission loss of sending a photon over a long distance, which means there are limitations for how far we can send it. One of the longest transmissions of land-to-land have been over 404 km through an optical fiber.

Let’s look aside from the extreme problem of 400km, because you do have loss in shorter distances as well, where a significant portion of photons sent from Alice to Bob won’t be registered by Bob. This loss-problem is often rectified by a post-selection process, where Bob publicly announces which photons he registered, so that Alice only keeps the same data.

BB84 Protocol

We have now looked at the basic physics behind quantum cryptography, along with the advantages and drawbacks, so now we’ll focus more on the protocol that ensures safe encryption.

The quantum key distribution protocol, BB84, was named after Charles Bennett and Gilles Brassard, who came with a lot of the principles behind quantum cryptography in 1984. When Alice emits a polarized photon to Bob, Bob does not know which polarizer Alice has used, so he has to randomly pick which one of the two beamsplitters, as seen in the picture below. The two bases are so that Bob can split between horizontal and vertical photons, for -45° or +45° polarizations

What this means is that when Alice sends, say a horizontal or vertical polarized photon, Bob does not know which beamsplitter to use, and has to guess. He can choose between the “+” and “X” beamsplitters in the image above, which results in Bob only picking the right beamsplitter half of the time. If Bob did in fact pick the “+” beamsplitter to detect a horizontal or vertical polarized photon, then Bob will detect a 0 or 1. On the other hand, if Bob chooses the “X” beamsplitter, then the polarized photon will bet detected as a -45° (“\”) or +45°(“/”) 50% of the time each. “\” and “/” correspond to 0 and 1, in the same way as horizontal and vertical correspond to 0 and 1. This sets a requirement that that Bob needs to use polarizing beamsplitters that are compatible with Alice, to read the right polarization.

After Bob receives enough photons, he will then end up with a key of bits called the raw bits. Then Alice and Bob will publicly announce over an insecure connection, such as the internet, the sequence of beamsplitters that they used to measure the qubit values. It’s important to understand that they only reveal the sequence of the of the beamsplitters, meaning the order used of “+” for horizontal and vertical, and  “X” for “\” and “/”. They do not reveal the value (0’s and 1’s) corresponding to the beamsplitters, but just the sequence they both used beamsplitters. They then discard the qubits where they did not use the same beamsplitter, and keep the ones where they used the same beamsplitter. Since Bob randomly picks a beamsplitter for every photon, he will pick the wrong beamsplitter half of the time, so they end up discarding half of the qubits, and the new random sequence of bits will be half as long. It is called the sifted key.

In the new sifted key, Alice and Bob takes a fraction of their key (meaning the 0’s and 1’s values) and compare them on a public channel to see if they have the same value. If the fraction of the key is the same for both, then they have a secure quantum key. Take a look at the image below for further explanation:

But what happens if is trying to intercept? If Eve has tried to eavesdrop on the transmission, then Eve will have picked the correct beamsplitter half of the times, since it’s a 50/50 chance to pick the right one. So when Eve is copying the information, half of the information might be changed when sent to Bob. This is because Eve might use the “+” beamsplitter on an incoming photon and get the right value (0 or 1), yet half of the time she will use the wrong beamsplitter, “X”, where it’s a 50/50 chance to get the right value (0 or 1).

Correct vs incorrect guess of beamsplitter. – Source

To summarize:

  • Alice and Bob Reveal the sequence order of their beamsplitters
  • Discard the values where they have used different beamsplitters.
  • The new key is half as long – the sifted key.
  • Conduct a test with the sifted key by taking a fraction of they key (the 0’s and 1’s) and compare it on a public channel.
  • If they have the same fraction of key, they know no one has eavesdropped or the signal has been perturbed. Their entire sifted key is than considered safe to use for encryption and decryption.
  • If there is a discrepancy between Alice and Bob’s fraction of the sifted key, someone may have been eavesdropping (or poor signal). They sifted key is than not considered safe.

A simplification of this process is illustrated in the video below.

When Alice and Bob only measures a fraction of the errors in the key, this is known as the quantum bit error, and the BB84 protocol can then provide information if the key is provable secure, or if it has failed.

How Far Have We Come?

But who actually uses this? Well, earlier we said that one of the longest transmissions of photons for quantum communication for land-to-land was over 400km through fiber optics. The Chinese Academy of Sciences in Beijing and the Austrian Academy of Sciences had an experiment of intercontinental quantum communications, with the goal of establishing a secure video conference between them. First packets of photons were sent from 1200km from ground to satellite, the Chinese Micius satellite, as the satellite passed over China, and worked as a relay to send the packets to Europe. Then Austria and China could communicate securely through fiber optics between them, an impressive distance of 7600km. This is laying the ground for a future quantum internet.

This post has been heavily influenced by https://arxiv.org/pdf/1108.1718.pdf, https://arxiv.org/ftp/arxiv/papers/1002/1002.1237.pdf and http://alumni.soe.ucsc.edu/~yanli/res/quantum_cryptography_intro.pdf.