JAMES ELCOCK
[This article is the second in a series on Quantum Technologies. For an discussion of the origins of quantum theory and its applications to physics, consider reading You Cannot Understand Quantum Physics - Should You?. For a more in-depth look at the principles of Quantum Key Distribution, after reading this article, see James' next one, Quantum Key Distribution]
The basics
Privacy is a key part of the internet and modern communication. Who wants every little detail about themselves exposed and open to the world? To ensure privacy, communication over the internet is encrypted. Encryption is the process of hiding the contents of a message by applying an operation to the text. An example could be to swap every letter of the message with the letter next in the alphabet (this is called a Caesar wheel):
\(encryption is cool → fodszqujpo jt dppm\)
And then to read the message, the intended recipient uses a key (that they will have received through a secure channel) that will enable them to decrypt the message. In the example above this would be the number of places shifted in the alphabet (i.e. 1).
The problem with using a basic encryption method such as a Caesar wheel is that the message above could easily be brute-forced. This is because there are only 25 possible shifts for each character to move. This means somebody could try each possible shift until they find the message. As lots of communication could include sensitive information such as trade secrets or nuclear codes, a stronger encryption method is needed.
Modern communication occurs over the internet. This means that the message would be represented as numbers using Unicode (A is represented by 65, B is 66, etc.). As the message is represented by numbers, certain operations (involving modular arithmetc) can be performed on the message such that there is no way for an eavesdropper to know what operations were done. Examples of algorithms employing this techinque include AES, Triple DES and Blowfish. These algorithms are so secure and impossible to crack that it would take one of the world’s most powerful supercomputers (like "Tianhe-2"), millions of years to crack just a single message.
Again, the intended recipient needs the correct key to be able to decrypt the message. It can be given to them using a variety of key exchange algorithms (e.g., Diffie-Hellman, RSA, ECC, etc.). These algorithms are equally secure and it would take Tianhe-2 6.4 quadrillion years to crack a 2048 bit RSA key. However, if this was able to be cracked then the eavesdropper wouldn’t just have access to a single message. In fact they could read every message received by the intended recipient. Unfortunately there is a technology that means that these key-exchange mechanisms could be cracked.
Quantum computers
Classical computers such as the one on which you are viewing this article are based on, and obey, classical laws of physics. This is in contrast to quantum computers, which obey quantum laws of physics that are truer than the classical ones on a fundamental level. This allows for quantum computers to have an advantage.
[Figure 1: Diagram depicting the intersection between different fields of computing and physics, and how this relates to Quantum]
The key difference between classical and quantum computers is that quantum computers use
qubits instead of bits. While bits can only be either 0 or 1, Qubits are bits that can take a value of both 1 and 0 simultaneously, because of the way in which they represent the bits using the quantum state of particles. This means that if you have 2 qubits, they can take 4 possible values and so when the number of qubits increases to 30, they can represent over a billion different values simultaneously.
Quantum computers then take advantage of this by performing calculations over the qubits which are representing many different values, effectively computing the answer for all possible states of the problem at once. Then using complex physics, we can ensure that only the correct answer is always returned.
This is possible due to quantum superposition which is where quantum particles can be in multiple states at the same time. A well-known example of this is Schrödinger’s cat, which is said to be in a superposition of dead and alive at the same time.
In addition to superposition, qubits can benefit from entanglement, allowing the same calculation to be performed over all of the entangled qubits.
To show how quantum computers work let's take an example. In the image below we are trying to find the length of the shortest path from the red to the green dot. In classical computers, each of the possible paths is generated and then the shortest path is selected (there are ways to optimise this but it isn’t relevant here - see Dynamic Programming if interested) whereas quantum computers, using qubits, can check all the possible paths and using complex physics complete all calculations simultaneously to produce only the best path length. This is significantly faster as it is only doing one calculation but all the needed calculations are taking place simultaneously in that one calculation.
Back to cryptography
The new computing power provided by quantum computers would mean, if developed to a sufficient extent, that all modern ciphers would become breakable and would need to be replaced by "quantum-safe" encryption standards. This would require a major upheaval of the internet and could cause mass disruption to trade. Luckily, we are in the position where quantum computers are still rather weak and vulnerable to interference and so we have time make the required standard switch.
One option for a quantum-safe cipher could be to use quantum properties to help encrypt messages, and as these properties are completely random this would be provably secure. Encryption like this would mostly focus on distributing keys to both recipients as this is currently the weakest link in the chain. Here a process called sifting takes place. Single photons are sent along a fibre optic (modern broadband) cable. Each photon will have a randomly selected polarisation orientation (a property of light, represented by the arrows below) and they are sent through randomly chosen orientations of filters which are selected by the recipient. The recipient will then record the selection of filters used. After many photons have been exchanged the receiver reveals the sequence of filter orientations, without disclosing the actual results of his measurements. This information would be exchanged over a classical channel such as the internet. The emitter uses it to compare the orientation of the photons they have sent and in which cases the orientations were compatible with the chosen filters. The incompatible orientations are discarded.
Next, the key needs to be distilled (i.e., cleaned) as it is full of errors due to imperfections or the environment. First, all errors are corrected using classical error correction (e.g. checksums) and then the key is compressed to make it more secure. This is because an eavesdropper could have some information on the key, but by compressing it we prevent that information from being useful. A privacy amplification algorithm is then applied to the key. At this point the two users have a secure key with which they can communicate, using traditional methods.
Conclusion
There are many nuances to the particular topic and so I would recommend that you do more research yourself. I would specifically recommend the white paper in my bibliography, as it gives a good insight into quantum key distribution and quantum cryptography.
Bibliography
ID Quantique SA. (2020). Understanding Quantum Cryptography White Paper. Retrieved 1 October 2021, from https://marketing.idquantique.com/acton/attachment/11868/f-020d/1/-/-/-/-/Understanding%20Quantum%20Cryptography_White%20Paper.pdf
Singh, S., 2000. The Code Book. London: Fourth Estate.