The Importance of Quantum Cryptography: Explained and Explored

cueW...JgCK

29 Jan 2024

A beginner’s guide to building Quantum Computers, breaking encryption, and stopping quantum hackers

Introduction

I went to London recently and saw a replica of IBM’s Quantum System One.
Replica of IBM’s Quantum System One, from a recent trip to London
Since then I keep seeing Quantum Computing and Post-Quantum Cryptography — PQC — mentioned online and in the news.
There seems to be an air of mystery around it, maybe because (almost) no one has their own quantum computer. Because of this, it almost seems like a sci-fi thing or something we don’t need to be concerned with. But that’s not true, so I thought I’d write a blog post.
This post is quite in-depth: it sets out to explain what PQC is and why it’s important. If you’re baffled by the concept of a quantum computer, then don’t worry — I’ll get to that.
A quick heads up: I’m by no means an expert in cryptography or quantum computing. If you spot any errors or omissions then let me know.
What people think of when they hear “Post Quantum Cryptography”
First, lets clarify some terms with simple definitions:

Classical Computer: A type of computer that uses classical bits for processing information.
Cryptography: The techniques for secure communication in the presence of third parties.

This is how the Internet and all digital communication works. You’re reading this blog post over HTTPS thanks to cryptography.
It’s important to realise that the cryptography in use today is designed and configured to prevent attacks not just from current computers but also against future computers. Moore’s law roughly equates to encryption being twice as easy to break every 18 months. Put another way, it gets about 100 times faster to break encryption every 10 years. That means if it takes a hacker a whole month to break in to your encrypted hard disk today, if they found it in 10 years time then it would take them about 7 hours.
This is the reason why it’s crucial for cryptography to anticipate and stay ahead of future advancements in computing technology.
Now let’s introduce the “quantum” stuff…
Let’s get this out the way first: quantum does not mean fast.

Quantum Computer: A new type of computer that uses quantum bits (qubits) for processing information, which allows it to perform certain types of calculations much faster than classical computers.
Post Quantum Cryptography (PQC): Cryptography methods that are designed to be secure against both classical computers and potential future quantum computers.
Quantum Cryptography: Cryptography methods that require a quantum computer to work. Don’t worry about these for now.

As cryptography is designed to prevent attacks from future computers, it doesn’t matter whether or not there are any quantum computers available today. The risk is that in a few years, quantum computers will be available that break traditional cryptography.

Classical Computers vs Quantum Computers

How Classical Computers Work: Bits

The computer you’re currently using to read this post operates on the principle of bits. These bits, which are either 1’s or 0’s, true or false, are stored in your computer’s RAM and disk. Your CPU, the brain of your computer, performs billions of logic calculations every second. For instance, the logical operation NOT false results in true, and true AND false results in false.
The 1’s, 0’s and logic gates that make up a classical computer
Classical computers have been around for a while and now we’ve got to the point where the average smartphone can store around a trillion bits. That’s 1,000,000,000,000 bits! You can even power up a phone years later and still access those trillion bits.

How Quantum Computers Work: Qubits

Quantum computers aren’t like classical computers. They use the principles of quantum mechanics to process information. Things aren’t either true or false in the quantum world. Quantum bits, known as qubits can be true, false, or in a state where it can be either. This is known as superposition: where the qubit can be true or false until it’s measured.
Quantum mechanics has another concept that qubits make use of called entanglement. Entanglement is when 2 the state of one object depends on the state of another, no matter how far they are separated. Also if 1 qubit is changed then so is its entangled partner.
These concepts mean that quantum computers can do calculations based on the probability of a qubit’s state, before it’s measured.

But what are qubits really? Can we make one?

You will need:

aluminium
silicon
an insulator
a microwave. Make sure it has very precise power and timing controls.
a fridge. Ideally cooled with liquid helium.
a Faraday cage
sticky tape and glue (optional)

1’s and 0’s are fairly intuitive to understand if you’ve ever used a light switch. These bits are little more than the presence or absence of a charge: either as a voltage going through a circuit in a CPU or as a floating charge in something like an SSD.
Qubits probably still sound a bit mystical because of the counterintuitive properties of quantum mechanics. But in reality the physical system that hosts qubits aren’t that special. There’s a few different ways to hold a qubit, using various different particles. The most common being superconducting qubits, which is generally what you see if you Google for pictures of a quantum computer. But there’s also a few other types (that I don’t really understand), like quantum dots, topological qubits and photonic qubits.
To make superconducting qubits more tangible, let’s see how they’re made. Note: this is vastly simplified!
First, we’re going to make a Josephson junction, which is a superconductor sandwich that can continually carry a current without a voltage drop. All we need is a substrate, then we can use photolithography to make a circuit pattern and put some a superconducting material like aluminium on it, followed by an insulator, then some more superconducting material. This is circuit is going to be 10’s of micrometers in size, so nowhere near as small as the nanometer scale classical circuits in modern CPUs.
By NBS — NIST paper A Practical Josephson Voltage Standard at One Volt, Figure 1, Public Domain, https://commons.wikimedia.org/w/index.php?curid=319467
To make sure it’s stable we need to keep the Josephson junction in a fridge and also a Faraday cage, making sure it doesn’t get over 0.01K and there’s no electromagnetic radiation at all. Then we need to work out how to read and write to the qubit. We’ll use microwave pulses and then we’ll wire up some electronics so we can detect individual photons. This bit is a bit of trial and error, with lots of calibration needed as we have to match the qubit’s energy levels. Think of it like James Bond trying to perfectly match a villain’s car on a high speed chase. If we get the microwave pulses, distances and the electromagnetic couplings just right then we can entangle the qubits and make our very own controlled NOT gate! This is a 2 qubit gate that’s like a quantum version of an XOR gate and gives us the building block to make other quantum gates.
If you’ve followed along and made your own entangled qubits then send in a photo!
Don’t forget to keep your entangled qubits cool with liquid helium!

How Quantum Computers Solve Problems Quickly

But what do quantum computers do with these weird qubits?
Let’s say we have an unsorted database of 1,000,000 items and we want to find one item. A classical computer would have to go through each one and check it — potentially a million operations. A 4 core CPU might check 4 at once. This is an O(n) operation, where the time to find out the answer scales linearly with the size of the database. Computers these days are getting more and more CPU and cores so they can do more at once.
A quantum computer on the other hand can take advantage of the superposition of the qubits and check many states with fewer operations. A quantum computer with just 20 qubits can hold a superposition of 2²⁰ states at once. That’s more than enough to cover all 1,000,000 items in our database. Rather than searching one by one, quantum computers can then use Grover’s algorithm so they only need to search the square root of the number of items: 1000 in our case. This means searching for something is O(√n) instead of O(n).
This is the crux of why quantum computers are often perceived as “fast”. It’s not that they execute operations at a faster rate than classical computers. Rather, their speed advantage comes from their ability to leverage quantum algorithms, like Grover’s, which can solve certain problems using fewer operations than their classical counterparts. A quantum computer may take much longer to complete a step in calculation but still get the answer much quicker than a classical computer.
In essence, quantum computers don’t need more CPU cores to do more at once, they just need more qubits. To double the speed of a classical computer you might have to double the number of CPUs. But to be able to handle twice as many superpositions in a quantum computer, you only need to add 1 more qubit.
I’ll go into some of the practicalities of this later.

How Encryption Works on Classical Computers

Cryptography, at its core, involves computations that are straightforward to perform but challenging to reverse. This principle is the foundation of many encryption methods. A simple analogy is mixing paint: you can easily mix 2 paint colours together but once you’ve done it it’s much harder for someone to work out which 2 specific paints you used.
RSA encryption is like mixing paint and not knowing what colours it was made from
RSA, one of the most common encryption types today, is a perfect example of this. It operates on the principle of prime factorisation. It’s relatively easy to multiply two prime numbers together, but it’s computationally difficult to determine the two prime numbers that make up a given number. This asymmetry is what makes RSA secure.

Delving into RSA

Using the example from Wikipedia, 61 times 53 is easy to work out with a bit of paper and a pen in just a minute, assuming you know your times tables. But if I asked you to work out what 2 prime numbers 3233 could be divided into, you’d have to check each one, taking hours or even days.
From the 2 prime numbers 61 and 53 and their product 3233, you can use the RSA algorithm to derive public and private keys like 17 and 413 (read the Wikipedia page for how this is done). Anyone with the public key 17 and the product 3233 can then quickly encrypt any data. Decrypting is also quick if you know the private key. If you don’t then you have to work out the prime factors of 3233.
RSA is just 1 of lots of encryption algorithms, many of which depend on prime factorisation being a time consuming calculation to perform. The general rule is that as computers get faster, bigger prime numbers are needed to ensure the factorisation process remains sufficiently slow.
As of 2023, RSA keys are typically 4096 bits long. To put this in perspective, if you were to write this number in base 10 (the number system we use in everyday life), it would have over 1000 digits. Imagine an A4 piece of paper filled halfway with the public key and the other half with the private key, all written in a standard font size. The complexity of RSA lies in the fact that even if you have this A4 paper with the product of two large prime numbers, it would take computers in the foreseeable future an impractical amount of time to figure out which two prime numbers were used.
This is with classical computers though. Is it practical to use quantum computers to break encryption like RSA?

Practicalities and Current State of Quantum Computing

Quantum computers are all about the qubits. The number of qubits required depends on the complexity of the task at hand. For instance, a mere 20 qubits can swiftly search a database of 1,000,000 items. However, the way some algorithms work (we’ll get to them later) to crack a 4096-bit RSA encryption, we would need a quantum computer with a capacity ranging from 10,000 to 100,000 qubits.

Where are we now?

If you skim over Timeline of quantum computing and communication, you’ll see that the first real quantum computers were made around the 1980’s and 1990’s, starting off with just 2 qubits. In the 2000’s there were reports of quantum computers with 10’s of qubits and now in 2023 there’s a few with a few hundred or so qubits. (Not including D-Wave’s processors that use Quantum annealing, which is a different type of quantum computer).

It’s not easy

But why does the phone in my pocket have a trillion bits, while the tech giants are struggling to make quantum computers with 1000 qubits? The answer comes down to how unreliable qubits are.
Qubits are super-sensitive to the environment: imagine trying to get an old style spinning hard disk to work reliably whilst in a washing machine running with bricks in it. That’s a bit like the challenges of running a quantum computer whilst there’s various atoms and electromagnetic interference all around. Quantum computers need to keep qubits around long enough to perform useful operations on them before they decohere and then carefully read them without disturbing them.
Quantum computers are often cooled to close to absolute zero, so there’s less thermal energy to mess things up. Many rely on superconductors to ensure there’s almost zero resistance and have massive copper pipes. There’s also clever engineering in place to reduce vibrations or any other environmental change. Until the engineering to reduce this decoherence has advanced substantially, you won’t get a quantum computer in your smartphone. Unless you want liquid helium in your pocket that is. This is also why quantum computers, like IBM’s System One, look so cool and unusual and add to the mystery of scifi TV shows.

Error correction

Anyway, this decoherence of the qubits leads to errors that need to be corrected.
Errors aren’t normally a big problem with classical computers: you just add in some extra bits and use an error correction algorithm. For example the Reed–Solomon error correction is used all over the place: it’s the reason that a slight scratch on a DVD won’t cause issues and why a small bit of dirt on a QR code won’t stop it being readable.
However, error correction in quantum computers is a much more complex task and fundamentally doesn’t work in the same way. One issue is that every time a qubit is added, it can potentially interact with all the other qubits, leading to a higher probability of errors. There’s also the no-cloning theorem, which means that you can’t “backup” a qubit.

Future?

There’s many other challenges with building reliable quantum computers too but the finickiness of qubits is the main reason we haven’t reached quantum supremacy yet: the point where a quantum computer can do something better than a physical computer.
There’s so much ongoing research with quantum computing as new techniques are created and the number of stable qubits gradually increases. This feels slow at the moment but one or two significant breakthroughs could suddenly unlock and accelerate a whole lot of further innovation.
As the value of quantum computers gets proven with quantum supremacy, we can expect significantly more investment into it and the pace of technology to increase further.

Applications

Because they can deal with so many states at once, quantum computers are very well suited to certain types of work. A powerful enough quantum computer could simulate individual molecules and revolutionize areas of chemistry and biology and specific fields like weather and climate forecasting. Many types of optimisation problems are much easier with a quantum computer using quantum annealing, leading to efficiencies in many industries. Machine Learning and AI is likely to get a big boost too, with quantum versions of support vector machines for pattern matching and the potential for quantum neural networks to make it quick to train AI.
So lots might happen when we get a quantum computer with enough reliable qubits. But let’s see what happens to traditional encryption when we have a suitable quantum computer…

Breaking Classical Cryptography with Quantum Computers

OK, so we have a load of data that’s been encrypted using RSA (or something else like ECDHE). This relies on it being difficult to find the 2 prime numbers, known as “prime factorisation”. Let’s pretend we have access to a quantum computer with enough qubits to break it. Now what? Do we just get it to try all the prime numbers really quickly?
Unfortunately it’s not that simple. Remember: quantum computers aren’t just “fast computers”, they’re computers that make use of certain quantum mechanics properties like superposition and entanglement. We can’t just give them a traditional algorithm and expect them to blast through it in no time at all.

Shor’s Algorithm

What we need is a specific algorithm that’s designed to be ran on a quantum computer. I already mentioned Grover’s algorithm, which gives a pretty impressive quadratic speed up to database searching. But for doing prime factorisation we’re going to make use of Shor’s algorithm that gives an exponential speedup than the best known classical algorithms.
Shor’s algorithm is a bit complicated to go into here but in essence if you can turn a problem into an “order finding” problem then you’re in luck. Order finding means working out how many times you have to multiply a number by itself to make it divisible by a number with a remainder of 1. For example you have to keep multiplying 4 by itself 3 times (4x4x4=64) to get an answer that when you divide it by 7 you get remainder 1, so the order of “4 modulo 7” is 3.
Once you’ve converted a problem into order finding, you can use something called Quantum Phase Estimation to massively parallelise the problem, taking advantage of a quantum computer’s superposition. To be honest the Quantum Phase Estimation part of things is where I start to get a bit lost.
RSA uses prime factorisation but this isn’t the only kind of problem that can be turned into an order finding problem for Shor’s algorithm to speed up. For example Diffie-Hellman Key Exchange uses something called the discrete logarithm problem, relying on the fact that it’s hard to work out x in an equation like 123ˣ = 456. Shor’s algorithm works for this too. In fact most cryptography in use today is vulnerable to Shor’s algorithm.
Uh oh.

Practicality

Shor developed his algorithm in 1994 but it wasn’t until 7 years later in 2001 that it was demonstrated to work. IBM used a quantum computer with a grand total of 7 qubits to run Shor’s algorithm. Here’s what the researchers managed to work out with their amazing quantum computer:

The prime factors of 15 are 3 and 5.

Wow!
Since then a few other two digit numbers have been factorised. 21 has been factored into 3 and 7!
This all sounds like maths that children can do in their heads. Factoring 2 digit numbers isn’t challenging at all. And remember, RSA is often used with 1000 digit numbers.
However this was a working proof of concept. The use of Shor’s algorithm was clear tangible evidence that quantum computers could one day overtake classical computers and pose a significant threat to cryptography. Think of this like creating a sports car with incredible power in the engine but because you haven’t figured out the gearbox yet, it can only go 5 miles an hour.
As of 2023 there don’t seem to be any prime factorisations of 3 digit numbers that have been done with Shor’s algorithm. We certainly haven’t reached quantum supremacy yet as we need 10’s of thousands of qubits to defeat RSA. But all signs are showing it’s a matter of “when”, not “if”.
So if quantum computers are going to break traditional cryptography some day, what can we do about it?

What is Post-Quantum Cryptography?

If you’ve been reading along carefully, by this point we:

know cryptography like RSA is effective against brute force attacks by classical computers
know quantum computers with enough qubits can make breaking RSA exponentially faster
know current quantum computers don’t give a practical advantage
expect quantum computers in the future to outpace classical computers

So once quantum computers with thousands of qubits are commonplace then does that mean all encryption is broken?
Firstly, Shor’s algorithm generally only applies to asymmetric encryption, which is used for things like HTTPS. Symmetric encryption like AES, where you use the same secret to encrypt and decrypt, is expected to be pretty safe even from quantum computers. This is because Grover’s algorithm only provides a quadratic speedup, which can’t keep up with doubling the key length.
Secondly, now that cryptographers are taking quantum computing and algorithms like Shor’s into account, a whole new field of cryptography has merged: Post Quantum Cryptography or PQC. This is algorithms that have been specially designed to be resistant against quantum attacks.
So, to ensure that we can continue to keep information safe in the future, we need to make sure we’ve got PQC algorithms in place wherever we’re using asymmetric encryption.

Post-quantum Cryptographic Algorithms

So far there’s 4 main types of PQC algorithms that have been created: lattice-based, code-based, multivariate polynomial and hash-based. The field is rapidly expanding and there’s lots of research in this area. The details of some of these algorithms are beyond my understanding but the general idea is that there is confidence that they can’t be reduced to a problem that can be solved with any known quantum algorithm. In simpler terms, you can’t solve them faster by adding more qubits, you have to add more processing power.

Homomorphic encryption

Before we go on, a slight side track about these algorithms…
Some of these algorithms also give rise to a fairly new concept called homomorphic encryption. Normally when you encrypt something, the encrypted message can’t be analysed — it’s just gibberish. With homomorphic encryption, certain processing can be done on the encrypted message. This is incredibly cool. Depending on how the plaintext was encrypted, it can be possible to do things like search through the data, do privacy-preserving data analysis or secure voting, all without needing to decrypt the data.

Lattice-based cryptography

Let’s have a quick look at lattice-based cryptography, which seems to be one of the most common and actually isn’t too complicated.
A lattice is like a repeating grid, like you see on graph paper. But instead of being in 2 dimensions or even 3, lattices used in cryptography have hundreds of dimensions. Lattice-based cryptography generally relies on variations of the Shortest Vector Problem (SVP).
Multi-dimensional lattice
If you try reading up about the Shortest Vector Problem then you’ll come across loads of complicated maths.
But just like RSA is like mixing and un-mixing paint, let’s let’s see if we can simplify it a bit…

Chess analogy

Let’s reduce our lattice to 2 dimensions and visualise it as an infinite chess board. We have a knight in the centre. How the knight moves is the “vector”. Normal knights can move 2 squares in one direction and 1 in the other. We can represent as the vectors (1, 2) and (2, 1) for moving ↗ and negate them for ↙️. Knights can also move with the vectors (-1, 2) and (-2, 1), which allows them to go ↖️ and ↘️.
For our lattice-based cryptography, we’ll have a special knight that can move either (1, 4), (7, 5) or (-2, 3). We'll call these 3 moves "hop", "skip" and "jump", respectively, just for fun.
Our special knight can hop (1, 4), skip (7, 5) or jump (-2, 3)
Now, the challenge is to find the combination of knight moves that will get the knight as close as possible to the starting point but not exactly on it. As you can imagine, this requires trying lots of different combinations. It turns out that with these three moves, our knight can get to one square below the starting point: (0, -1). It does this with 1 skip, 2 jumps and then hopping backwards 3 times. Fortunately our lattice is infinite, so the knight doesn’t fall off the board.
That’s the basis of lattice-based cryptography. Though our cryptographic knight can move in hundreds of ways (vectors) and our chess board also has hundreds of dimensions.
3D chess in the future. Still not enough dimensions.
In practice, lattice-based cryptographic algorithms add additional layers of complexity. To generate a public key, I’d have to introduce a controlled amount of randomness into the description of the knight’s possible moves. This adds a layer of obfuscation that’s deliberate and calculable. During encryption, the knight would be given a mathematically precise nudge on the board.
If you’d like more maths, I’d highly recommend reading Enough Polynomials and Linear algebra to implement Kyber as it’s not too complicated.
OK, we’ve now got the maths to save us from hackers with quantum computers. What’s next?

Current and Future Outlook

PQC recommendations

When a new cryptographic algorithm comes along then it isn’t immediately adopted. First it needs rigorous testing. Over time new algorithms gain adoption, spurred on by industry recommendations from the likes of NIST in the US or NCSC in the UK.
In July 2022, NIST announced that the PQC CRYSTALS-Kyber encryption had won its competition to be used for general encryption. Since then Kyber, a lattice-based PQC algorithm, has grown significantly in its adoption. In August 2023, NIST announced it would standardise Kyber in FIPS 203, along with some other PQC encryption for digital signatures.
FIPS 203 is a 49-page draft PDF. Don’t let the pages of linear algebra scare you though — it’s little more than explaining the rules and constraints of our multi-dimensional knight problem. In fact, if you know C then the source code to generate keys and encrypt messages in Kyber isn’t too complicated.

Risks

Encryption like Kyber is quantum-resistant, rather than definitively quantum-proof. There’s no known ways to break Kyber at the moment but until it can be proved impossible, there’s always a chance that a new algorithm like Shor’s will make Kyber vulnerable.
It’s also early days for PQC: they haven’t been battle-tested yet and there could be undiscovered exploitable weaknesses in the algorithms. This is what happened to SIKE in 2022. SIKE was a promising PQC key-exchange algorithm based on ECC but the way the keys are exchanged meant some of the metadata (auxiliary points) gave away information used to generate the elliptic curves.

PCQ in use in 2023

As of November 2023, there’s growing use of PQC, specifically Kyber-based encryption. Here’s a few applications that jump out:

The Open Quantum Safe project (started in 2016) has developed a libocs, a C library with PQC encryption, used by many other projects.
The Signal Protocol can use PQXDH, which is based on Kyber. Signal Protocol is used by WhatsApp and Google’s RCS too.
Microsoft are working on getting PQC into OpenSSL, one of the most widely used encryption libraries (code). Watch out: that page still mentions SIKE, which is known to be insecure.
The Chrome browser supports X25519Kyber768

Cloudflare gets a special mention here, having developed the Circl encryption library in 2019. Cloudflare use a hybrid standard key-exchange and PQC key-exchange system, X25519+Kyber. This provides resistance against quantum computers but keeps the battle-tested encryption in place, just in case a weakness is discovered in the novel encryption. Cloudflare also have a PQC fork of Google’s BoringSSL.
Cloudflare regularly have excellent articles about their adoption of PQC. These are all worth a read:

Future

It’s already used on your phone, your web browser supports it and more and more web servers are starting to use it. We can expect PQC almost everywhere within a few years as the risks of quantum supremacy increase and the new encryption gets more battle-tested. Perhaps a few years later we can expect security standards to recommend or even require PQC.

Beyond Post-Quantum Cryptography

But is that it with quantum computers? What else might happen when tbey become commonplace?
If or when that’s the case, we can go one step beyond PQC.
Instead of just using cryptography that can’t be broken with quantum computers, we can start using quantum cryptography. This is in cryptography that requires a quantum computer to encrypt and decrypt data. This means they’re impossible to break using classical computers.
Not just yet though. For now, let’s just start upgrading to PQC.