Cryptography is an old subject. Any time two parties wish to communicate in secret, cryptography is useful. For example, when Julius Caesar had to communicate information of military significance, cryptography, albeit a simple one, was used, leading to the algorithm by the name “Caesar’s cipher”. This algorithm simply shifts every letter in the original message by three (A becomes D, B becomes E, and so forth), and is obviously very easy to break. Modern cryptographic algorithms are much more complicated, but the essence of it has not changed much. Cryptography widely used in communication technologies today comes down to devising ways to encrypt a message so that only the intended recipient can decrypt it back to the plain text.
Suppose we wished to make Caesar’s cipher stronger. Instead of shifting every letter by three, we may devise a look-up table that switches every letter with another letter as given by the table. Such a table may look like the one below, in which you can look up any letter in the first row, and the corresponding letter in the second row is its encryption.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | Z | Y | Z |
| G | Q | L | K | V | B | O | X | W | T | M | U | H | Y | D | P | Z | R | N | F | A | C | E | J | S | I |
According to this table, to encrypt a message, I would switch all the A’s to G’s, B’s to Q’s, and so on. Decrypting is just as easy as long as you have access to this table. You look up the letter in the second row, and switch to the corresponding letter in the first row. The G’s become A’s, Q’s become B’s, and so on.
By this rule, “Meet me at the park” would become “HVVFHVGFFXVPGRM”. Here, I took out the spaces to hide some contextual information, because a three letter word in English is most likely to be the word “the” and I don’t want to give out such information.
Now, I simply need to share this table with the intended recipient of all my secrets, and as long as nobody else gains access to our secret table, I can communicate by sending encrypted messages, and the information will be safe, right?
Wrong. This is still a weak cipher. Let’s consider why. It is a major improvement on the Caesar cipher in which an adversary could simply shift the letters back by three to reveal the secret. However, the English language, like any human-spoken language on Earth, has distinct statistical characteristics that make a cryptographic algorithm like this one prone to attacks.
The most common letter used in the English language is the letter e. If I’m using the above table to communicate a message of significant length, it is not long before an attacker who observes the encrypted message will notice that the letter “V” likely is a substitute for “E”, because it seems to appear much more often than any letter. In English, T, A, O, then I are the next common letters after E, in that order, so the attacker may figure those out too by simple use of statistics. Eventually, all of the letters will be broken using a combination of statistics and inference from context.
So can we do better?
Before we discuss more cryptographic algorithms, let’s lay the necessary foundations.
Bits
At the heart of modern communication is the usage of bits to convey information. The word “bit” was coined by a statistician named John Tukey, who also coined the term “software”. A bit stands for “binary digit”, and each bit can hold a value of 0 or 1. Thinking of information as a collection of bits is particularly useful for designing computers, because computers store information in memory which consists of transistors. Each transistor can be in one of two states at any time. We denote one of the states as 0, and the other as 1.
All information can be represented by bits using some standardized process. For example, text can be converted into bits by lookup in each character of the text in the ASCII table, which assigns a number to each character. Those numbers can then be converted to 0s and 1s using binary math.
XOR Operation
The XOR Operation is commonly used as the building block of cryptographic algorithms. XOR stands for “exclusive or”. The operation takes two bits as inputs, and outputs 0 if the two input bits are the same. If not, the operation outputs 1.
So the possible input/output combinations of an XOR operation are as follows, where ⊕ denotes the XOR operation sandwiched by the two input bits:
0⊕0 = 0
0⊕1 = 1
1⊕0 = 1
1⊕1 = 0
The magic of the XOR operation, and why it is so useful for cryptography, is in its reversible nature. If you XOR a bit (call it the “original bit”) with a random bit (call it the “key” bit), you get a certain result (call it the “encrypted bit”).
Now, XORing the encrypted bit with the key bit turns the encrypted bit back into the original bit.
Here’s an example. Assume the following:
Original bit = 0
Key bit = 1
Encrypted bit is calculated as the original bit XORed with the key bit:
0⊕1 = 1 = encrypted bit.
Now, XORing the encrypted bit with the same key bit gets you back the original bit. This process works like a decryption, because you are decrypting the encrypted information to get back the original information.
1⊕1 = 0 = the original bit!
This works no matter the value of the original and key bits. I suggest that you try a few examples yourself to verify this fact.
One-Time Pad
Now that you understand how the XOR operation works, we are ready to introduce the “one-time pad”, a provably secure encryption algorithm which cannot be attacked on the basis of statistics.
To illustrate with a simple example, let’s assume that Alice and Bob already share a secret key. The topic of key-sharing will be covered later, so for now, let’s just assume that they’ve already gone through the key-sharing process and they both know that the key is “1001 1100”, while nobody else knows it.
Now, let’s say that Alice is trying to send a short message “1011 0101” to Bob in secret. To do this, Alice would XOR each bit of the plaintext with the bit from the key in the same position. This is called a “bitwise” XOR, and results in the following.
(1011 0101)⊕(1001 1100) = 0010 1001
Now, Alice can send this encrypted text (0010 1001) to Bob and it is completely safe from attack. An eavesdropper (let’s call her Eve) who gains access to this encrypted text in transit will have no way of knowing what the message is. It simply appears to be a random collection of 1’s and 0’s, and no statistical information is revealed that may help Eve break the encryption to turn it back to the original message.
Once Bob receives the encrypted text, he can recover the plain text by taking the encrypted text and applying the bitwise XOR operation with the secret key:
(0010 1001)⊕(1001 1100) = 1011 0101 = the original message!
The problem with the one-time pad is that the key can only be used once. Any key that is repeatedly used is proved to give out some information about the original text. Another concern is that the key must be the same length as the message itself, and if you had the ability to share a long key in secret, why not just share the message itself?
To overcome these problems, cryptographic algorithms have been devised to safely exchange a key (of limited length however), and to encrypt and decrypt a message using such a key. Although not provably secure theoretically, these algorithms still make it difficult for a third-party like Eve to figure out the original text, and only known attacks are brute force attacks that try every single permutation of possible keys. So far, these algorithms have stood the test of time to potential attacks, and are used in communication technologies everywhere today. This post will not delve into specific details of these algorithms, but an interested reader should read about Diffie-Hellman protocol for key exchange, and AES (Advanced Encryption Standard) as an example of encryption/decryption algorithm that works with a key of limited size (128, 192, or 256 bits), to get a taste for how some algorithms work under the hood.
These algorithms are in the realm of classic cryptography (as opposed to quantum cryptography). Classic cryptography algorithms depend on difficult math problems that even the fastest computers in existence cannot solve easily or quickly, such as the prime factoring problem. As long as computers don’t get too fast to solve these problems in a reasonable amount of time or to perform a brute force attack quickly, we can continue using these algorithms in cryptography.
A concern to classic cryptography is the observation that historically, computers have gotten faster over time. This means that classical cryptography may become useless in the future. Any algorithm that depends on computers being slow may become obsolete one day. Quantum cryptography, on the other hand, does not depend on math problems. Instead, they depend on the laws of nature. This is a paradigm shift from cryptography of the past, and has been of great interest in the recent decades as an alternative to overcome the limitations of classic cryptography. In the next sections, we will introduce the relevant laws of quantum physics that aid in cryptography, then quantum cryptography itself.
Qubits
We discussed bits in information theory previously, and it turns out that nature has its version of bits. We call them “quantum bits” or “qubits” for short, and we use this term generally to mean any quantum state that can be one of two values. Spin of an electron is one example, but for quantum cryptography, the orientation of the vibration of a photon will provide us with the qubits we need.
Quantum Nature of Photons
If you have a pair of polarized sunglasses, you have in your hands a device to measure the quantum nature of photons. Light consists of particles called photons, and each photon has an intrinsic orientation that can be filtered based on the orientation by the polarizer.
Sunglasses filter certain photons, but if we let photons through a calcite crystal, we will see that a random photon will pass through and emerge having one of two orientations with a 50/50 chance. If we orient the calcite crystal a certain way, we can force the photons to emerge with either a vertical or horizontal polarization.
Illustration: if a photon goes through a crystal in the following orientation,
then emerges with one of two orientations:
Once polarized, these same photons, if they were to pass through the crystal again, will retain the orientation as long as the orientation of the crystal is not changed.
A really interesting thing happens when I tilt the crystal by 45-degrees. Now, a photon is forced to be in one of two states, either 45-degrees up, or 45-degrees down as illustrated below. Surprisingly, regardless of the previous state (vertical or horizontal), the two new states are equally likely. There is no classical analogue to this nature of orientation and probability, so quantum mechanics is sometimes hard to wrap our heads around.
Illustration: A previously polarized (vertical or horizontal) photon goes through the diagonally-oriented crystal as below:
And emerges with one of these two states:
Another key feature of the photon’s orientation that makes it particularly useful for quantum cryptography is that polarizing the photon with this tilted crystal makes it “forget” the original orientation. Let’s call the original orientation the A basis, and the tilted orientation the B basis. If I measure the photon to be vertical in the A basis, it will stay vertical in the A basis as long as I don’t measure it in any other basis. But if I measure the spin in the B basis, then the original orientation in the A basis is forgotten, and measuring in the A basis again could result in a 50/50 chance of vertical or horizontal, since B now acts like the original basis, and A is now the new basis.
Quantum Key Distribution
With the above crash course in quantum physics out of the way, let’s see how we can take advantage of the quantum nature of photons to implement key distribution using photons. This process is called Quantum Key DIstribution, or QKD.
The goal is for Alice and Bob to share a string of bits that Eve doesn’t know. Alice can prepare a bunch of photons, and randomly select the A or B basis to send each photon. Suppose the below table represents the bases and the results that Alice observed. Here, we’ll denote the orientations with 0 and 1 instead of vertical and horizontal to be consistent with the notation of bits in cryptography.
| Alice Basis | A | B | B | A | B | B | A | A | A | B |
| Orientation | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
These photons are sent to Bob using an optical fiber. Bob also randomly chooses the basis with which to measure (A or B). He measures the following orientations:
| Bob Basis | A | A | B | A | A | B | A | B | B | A |
| Orientation | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
Notice that every photon which Alice and Bob chose to measure in the same basis resulted in the same value. This makes sense, since that is consistent with how photons behave. However, every photon that was measured in different bases has a 50/50 chance of flipping.
Now, Alice publicly shares the bases with which she measured each photon. Alice and Bob can keep the bits that were measured in the same basis as their secret key.
Here’s the end result:
| Alice Basis | A | B | B | A | B | B | A | A | A | B |
| Orientation | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| Bob Basis | A | A | B | A | A | B | A | B | B | A |
| Orientation | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| Same basis? (Y/N) | Y | N | Y | Y | N | Y | Y | N | N | N |
| Key | 0 | 0 | 0 | 0 | 1 |
So their secret key is “00001” in this example.
The example above only used 10 bits, and they ended up with a 5-bit long key since the other 5 were measured in the wrong basis. In actual applications, they would use a much longer sequence of bits to arrive at a sufficiently long key that can be used as a one-time pad.
Detecting Eve
Now, Alice and Bob must ensure that there was no eavesdropper present. Suppose their secret key is 256 qubits long. They could randomly select a few bits to compare, but the act of comparing requires them to give some of their secret bits away through an insecure channel, and they would have to discard those bits. A better way is to choose some random combination of bits, and share the sum of those bits, modulo 2. For example, Alice might say, “the sum of my 22, 54, 195, 200, 210th bits, modulo 2, is equal to 1.” And Bob can confirm whether his sum is the same. If their remainders don’t match, that tells them that someone had tried to measure the photon along the way, and because of the nature of quantum physics, the act of measuring has a probability to change the value had they measured in the wrong basis.
If the sums do match, that is still no guarantee that there was no Eve, since Eve may have gotten lucky by choosing the correct basis, or choosing the wrong basis but Bob ended up re-correcting the orientation when he made his measurement by sheer chance. Or maybe a bunch of bits were different, but the remainder just happened to be the same as that will happen 50% of the time just by random chance. So to be confident, Alice can now choose another combination of random bits and compare the sum with Bob. They can repeatedly do this until they are statistically confident that there was no Eve in the middle.
Future of Quantum Cryptography
The physics is there. Quantum cryptography, by the inherent nature of quantum physics, has the advantage over classical cryptography which relies on mathematics and the slowness of current computers and their ability to perform brute-force attacks. What’s preventing quantum cryptography from widespread use is the engineering challenge that comes with engineering a quantum network of intercontinental optical-fiber of long lengths and multiple nodes. One multi-node quantum network was built with a DARPA grant in the Boston metro area and was operational for 3 years starting in 2003, but it hasn’t been adopted much in the private sector where classic cryptography still works just fine, and still is much less expensive to implement. More recently, there is an ongoing effort in China to implement satellite-to-ground quantum channels. Only time will tell, but it may just be a matter of time before all cryptography will shift to quantum cryptography in the near future.
