jon-elliott

Hi, I'm a Software Engineer and lifelong learner with a passion for cryptography. I've been with the IAM-Core-Crypto team in Auth0 since 2021, but have been working on applying applied cryptography to systems and applications since 2015


Senior Software Engineer

Jon Elliott

Quantum computers may not be here yet, but we still need to prepare for them.

There’s a joke about Quantum Computing where a Computer Science Professor predicts to a rapt classroom that it’s just 10 years away, and the punchline is that they’ve been saying it for the last 50 years or so. The actual number of years in the future changes from telling to telling, but the point is always that it remains within sight but out of reach. Quantum Computing as a usable tool is definitely still out of reach, but you wouldn’t know it by the amount of discussion there is around it. We’re not going to go into the basics of Quantum Computing as there are plenty of articles already about that. 

Instead, we’re going to focus on how we actively need to prepare for it, whether it will be a reality soon or not. Post-Quantum Cryptography (PQC) refers to cryptographic algorithms that can be run on classical computers, but are believed to be secure enough to withstand a cryptoanalytic attack by a Quantum Computer. Don't get me wrong, I’m not saying that you need to go and ditch your brand-new laptop straight away. When they do reach maturity, Quantum computers probably aren't going to be relevant for every use case out there. The ones we have just now can’t even run that ultimate test of computing power, Doom. [Seriously](https://digitalcommons.denison.edu/cgi/viewcontent.cgi?article=1242&context=synapse).

## How Quantum Computing Impacts Security

However, Quantum Computing is of particular concern when it comes to cryptography, specifically end-to-end encryption. This is where the information is encrypted on the sender's device before transmission and is only decrypted when it reaches the intended receiver's device. This is how we use cryptography every day, in more ways than you can imagine. It’s not just when you log in to your computer to check your bank account; it’s when you message a friend to arrange to meet for lunch, it’s when you tap your card to pay for that lunch, and it’s when you’re reading this article. Take a look at the browser bar, and chances are you will see ‘https’ at the start of the web address rather than just ‘http’. That ‘s’ at the end means that no one online can tamper with what you are reading. The web page is being sent securely to your device via a protocol called TLS, encrypting all communication between your computer and this site.

So why is it such a concern for end-to-end encryption? Well Public Key Cryptography or Asymmetric Cryptography is built around the idea of certain problems being hard to solve, and one of these is what’s called the Integer Factorization Problem. Now, this is a bit counterintuitive but it’s based on the premise that while two numbers are very easy to multiply together, it is surprisingly difficult to divide that result back into its prime factors without first knowing them. The difficulty in calculating the two factors in computing terms equates to Computational Hardness. And Public Key Cryptography is a big part of end-to-end encryption.

> Public Key Cryptography is where a publicly available key is used to encrypt a message and a privately stored key is used to decrypt it. The maths behind it is that this is what is called a one-way function, i.e., very easy to compute in one direction but substantially more difficult to reverse, provided you pick two sufficiently large prime numbers. Examples usually revolve around RSA as it is relatively easy to explain and understand, but the more common Public Key algorithm used is Elliptic Curve, which is built around something called the Discrete Logarithm Problem. At a low level, it’s possible to prove that the Discrete Logarithm Problem and Integer Factorization Problem can be mathematically reduced to the same problem, but for the moment it’s best to think of RSA being based on the Integer Factorization Problem and Elliptic Curves being based on the Discrete Logarithm Problem.

So, how does quantum computing fit into this? Well, one of the earliest quantum algorithms is called [Shor's Algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm) and is designed to, well, efficiently divide a number back into its prime factors.  In real-world terms, Shor’s Algorithm is currently a while away from meeting this goal in any meaningful manner. The largest number reliably factored is 21 (that’s 7 x 3 for anyone needing a hand) back in 2012,  but when the infrastructure exists to support fully developed implementations, then it’s not too hyperbolic to say that it will be a bit of a game changer.

[Grover's Algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm) is a search algorithm that does the same for symmetric encryption but the solution is much simpler, which we’ll go into a little later on.

![Quantum Computing](https://images.ctfassets.net/23aumh6u8s0i/7L8e9elBfIZonTzxZDhPxh/4b95a9a75f7d82da0d43e29dc2ff330f/quantum-sep3.jpg)

One of the driving forces behind developing Post-Quantum Cryptography, or PQC, is the concern that with storage currently being so cheap, it is easy for criminals to stockpile data harvested from security breaches in preparation for when Quantum Computers are available, an approach known as Harvest Now, Decrypt Later, or Retrospective Decryption. Whilst some would argue against preparing for a technology that is a while away from maturity, these attacks are certainly technically feasible. All they involve is the intercepting and (more importantly) storing of a large amount of data that will still have value in 5/10/20 years time. It might not sound plausible that criminals would be that far thinking, however given the longevity of identifiable information, it's easy to see that captured data may still have value, and with storage being very affordable, it doesn’t require too much outlay on the chance that it will. Some predict that Quantum computers will be able to break classical encryption by 2030. Think back to where you were in 2018. Six years isn’t that long, is it? So, ultimately, the concern has changed: it’s not just what is to be kept secret, it’s also how long it needs to stay secret.

## Post-Quantum Cryptography Solutions

No great change is required to the core of asymmetric cryptography in order to make it Quantum secure. It’s still based on the difficulty of solving certain mathematical problems. So, if we want to make an encryption algorithm Quantum secure, we must ensure that the problem it is built around is sufficiently hard. This has a knock-on effect on verifying the security of the algorithms, as cryptography algorithms are validated by cryptographers rather than mechanical means, and the hardness of the problems means that there are fewer cryptographers qualified to do so.

There are six different approaches currently being worked on in Post-Quantum Cryptography:

- Lattice-based cryptography
- Multivariate cryptography
- Hash-based cryptography
- Code-based cryptography
- Isogeny-based cryptography
- Symmetric key Quantum resistance

Out of all of them, symmetric keys are the easiest to harden for Quantum Computing attacks, relatively speaking. In fact, in order to meet the same level of security strength (based on computational hardness) for a Post-Quantum algorithm as for a classical one, the key size can simply be doubled. This is because the computational hardness of symmetric key algorithms is based on the size of the keyspace rather than the difficulty of any problem to solve. So, to meet the same level of security currently offered by AES-256, you will need to use 512-bit keys.

Lattices are a mathematical construct based around matrices, which are arrangements of numbers in rows and columns. One of the more popular algorithms is called [Learning With Errors](https://en.wikipedia.org/wiki/Learning_with_errors), where the Error (a row of values) is added to the result of two matrices, providing the ‘difficulty’ in retrieving the result from the first factor. This can be represented formulaically as `ax+e = b`, where `a` and `b` make up the public key, and `x` and `e` make up the private key.

Hash-based cryptography involves using cryptographically secure hash functions to generate a private and public key for signing and is considered one of the more fully understood approaches. Lattice-based cryptography and Hash-based approaches have proved to be the most fertile ground for asymmetric solutions, leading to them making up the majority of the submissions for standardization by NIST.

## NIST Recommendations

The body that decides which encryption algorithms become standards isn't the NSA or one of the other three-letter agencies you might think of. Instead, it’s the National Institute for Standards in Technology, a subsection of the U.S. Department of Commerce whose job it is to cover both the algorithms and the key strengths recommended for guaranteeing high security. Established in 1901 as the National Bureau of Standards, NIST is responsible for fostering technological innovation and economic competitiveness in the United States. They first became part of the cryptography landscape as part of the first Government project to develop a publicly available cryptographic standard to satisfy a broad range of requirements and use cases, rather than leaving it to the military as had previously been the case.

An open call was made in the early 1970s for people and companies to submit candidate algorithms, and after receiving a submission from IBM called Lucifer, NIST chose that algorithm as the basis for its proposed [Data Encryption Standard (DES)](https://en.wikipedia.org/wiki/Data_Encryption_Standard). Offering only 56 bits of encryption, it wasn’t long before this proved to be wanting in overall security terms, as the hardware needed to crack DES encryption started to become less cost-prohibitive as time went on, and several public competitions were held in the late 90’s with the express goal of breaking DES. It was reconfigured as Triple DES in an attempt to extend its shelf life (literally just running the DES algorithm three times to give 112 bits of security), but it soon became clear that a new standard was required. This was followed up with the replacement, [Advanced Encryption Standard (AES)](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard) in 1997, an implementation of the Rijndael Encryption Algorithm, selected from a list of viable candidates from another public competition.

![Data Encryption Standard](https://images.ctfassets.net/23aumh6u8s0i/1459k5sEGn3nETjOL2CIVP/8d1b15fe4602127fb343c8fe727c3152/quantum-sep2.jpg)

Encryption doesn’t stand still though, so NIST needs to keep updating its standards to meet the evolving security requirements. Since 2016, they have been running rounds of evaluation as part of their PQC Standardization Process, asking cryptographers to devise and vet encryption algorithms that could resist attacks from a Quantum computer. This has been done in the open to allay any concerns of the algorithm being tampered with, such as in the case of [Dual EC DRBG](https://en.wikipedia.org/wiki/Dual_EC_DRBG), a random number generator that was believed to have a backdoor inserted by the NSA.

Nist started with 82 candidate algorithms nominated. 69 of these were chosen to progress, and through four rounds of judging this was whittled down to the four current standardized algorithms in 2022.

### CRYSTALS-Kyber

Renamed by NIST as the Module Lattice-Based Key Encapsulation Mechanism (ML-KEM), this is based on the Learning With Errors (LWE) Lattice problem and is intended to be used for general encryption. It replaces Quantum vulnerable algorithms such as Elliptic Curve Diffie-Hellman (ECDH), i.e., any which use a public/private key pair to share a key that can then be used for symmetric encryption.

There are three parameter sets defined by the standard:

- Kyber-512, offering security equivalent to AES-128
- Kyber-768, offering security equivalent to AES-192
- Kyber-1024, offering security equivalent to AES-256

### CRYSTALS-Dilithium

Renamed by NIST as Module Lattice-based Digital Signature Algorithm (ML-DSA), this is a digital signature intended to offer a Quantum-secure replacement for ECDSA and RSA, i.e., any use case which involves using a public/private key pair to authenticate data.

There are three parameter sets defined by the standard:

- ML-DSA-44, offering security equivalent to SHA3-256
- ML-DSA-65, offering security equivalent to AES-192
- ML-DSA-87, offering security equivalent to AES-256

### SPHINCS+

Renamed by NIST as Stateless Hash-based Digital Signature Algorithm (SLH-DSA). Unlike all the other algorithms, this is the only non-Lattice-based solution and is instead a Hash-based approach.

There are twelve parameter sets defined by the standard. These are based on using either SHA2 or SHAKE as the hash algorithm and 128, 192, or 256 bits of security, eg SLH-DSA-SHA2-128s uses the SHA2 hash algorithm and offers security equivalent to AES-128.

### FALCON

This is a Lattice-based solution but is still to receive a draft standard. This is taking longer due to the difficulty of implementing it, but it is due later this year (2024).

Three additional algorithms are still under consideration: BIKE, Classic McEliece, and HQC, all code-based cryptography. The popular SIKE (Supersingular Isogeny Diffie–Hellman Key Exchange) was originally in this list but was found to be classically broken by a group of Belgian researchers, who were able to recover a key within 62 minutes running on an [Intel Xeon computer](https://eprint.iacr.org/2022/975.pdf). NIST unsurprisingly decided not to standardize SIKE. This was built around the Supersingular Isogenies Problem, which seems to have been enough to dissuade further development around this particular problem.

## Conclusion

Hopefully, you’re all a little clearer by now on why this is important and also why it has taken a long time to get here. Taking the joke from the start of this post as a warning, the U.S. is aiming to transition its cryptographic systems to Quantum-resistant algorithms by 2035, and recently, both Apple iMessage and Signal have upgraded their protocols to incorporate the CRYSTALS-Kyber algorithm and become Quantum-resistant. So, while this is a complex area and there are too few people around who understand it, the progress made is promising, and the joke is slowly becoming a reality.

### References

- [NIST: PQC Standardization Overview](https://csrc.nist.gov/projects/post-quantum-cryptography)
- [NIST: PQC Standardization Call for Proposals](https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf)
- [Wikipedia: Hidden Subgroup Problem](https://en.wikipedia.org/wiki/Hidden_subgroup_problem)
- [CACM: NIST Post-Quantum Cryptography Candidate Cracked](https://cacm-preview.acm.org/news/nist-post-quantum-cryptography-candidate-cracked/)

Post-Quantum Cryptography: Preparing for the Future of Security

arthur-bellore

I’m a tech content creator. I enjoy breaking up seemingly complicated topics into easy-to-understand pieces for people to read. When I’m not in front of a computer, you’ll usually find me reading books.

Cybersec Writer

Arthur Bellore

Quantum computers are not simply very fast regular computers

## A Definition Of Quantum Computers

At the pace, technology has been growing over the last decades, our ability to make faster and smaller processors is slowing down. However, why do we have to make computers faster in the first place?

It doesn’t matter how fast the “classical” computers of today become; their architecture isn’t well-suited to solve certain kinds of problems, like drug research, training artificial intelligence, and breaking encryption algorithms.

Quantum computers aren’t the “faster horses” that Ford alluded to when he created the Model T, but rather an entirely different type of computer that changes the paradigms of how computers work, much like the car changed the transportation paradigm at the time.

They are another tool to aid researchers, scientists, and computer programmers in developing solutions that can radically alter how we interact with technology.

Quantum computers date way back to the 70s and 80s when quantum physicists were theorizing on how they could harness the quantum mechanics properties of particles and create a machine that could make use of them.

Feynman, a pioneer in the field, published a paper in 1982 titled [Simulating Physics with Computers](https://www.cs.princeton.edu/courses/archive/fall05/frs119/papers/feynman82/feynman82.html), where he said that to simulate quantum systems, we would need to build quantum computers.

And while quantum computers have been talked about for decades (you can take a look at the [timeline](https://en.wikipedia.org/wiki/Timeline_of_quantum_computing_and_communication)), the first quantum computer was only ever built in 2009. The reason for such a delay is that they are extremely fickle and very sensitive to interference from the external world.

But now they are becoming increasingly mature, so we’re going to talk about how they work, what problems researchers are facing today, and their future.

<include src="TweetQuote" quoteText="Are quantum computers the next big jump in technology advancement like classical computers were in the 1960s, and if they are, what does it mean for security?" />

## How Does Quantum Computing Work

As we’ve alluded to, the era of Silicon is coming to an end. We just don’t know when it’s gonna happen.
(There has been some promising research suggesting that maybe using Graphene instead of Silicon to build microchips could allow the trend to continue, but it’s not yet clear how viable it is. It’s entirely possible that the curve could flatten in the next 10 years.)

> The main issue preventing more growth with Silicon are fundamental problems of thermodynamics and quantum mechanics.

With the miniaturization of the transistor, it reaches a point where they’re so close to each other that the heat generated is so intense that the chip would melt. And on a sub-atomic level, the atoms are so close to each other that electron behavior becomes unpredictable. We simply don’t know where electrons are anymore: they could be inside the chip, outside of the chip... we just can’t know.

Now, even if Graphene-based chips, which have a much higher thermal and electrical conductivity than Silicon (meaning it can handle more heat and use less power), can continue the growth trend that started with Silicon, there will still be problems that will be impossible for classical computers to solve because of the way they operate.

Quantum computers promise to address the atomic limitations by exploring sub-atomic physical properties that weren’t even known to man 100 years ago and use insane amounts of parallelism to make computations.

![Superposition](https://images.ctfassets.net/23aumh6u8s0i/7L8e9elBfIZonTzxZDhPxh/4b95a9a75f7d82da0d43e29dc2ff330f/quantum-sep3.jpg)

## Superposition

Classical computers perform operations using bits, which can be either 0 or 1. A quantum computer performs operations using qubits, or quantum bits, and they can be both 0 and 1 at the same time. They only collapse when we measure them.

The idea that one thing can be at two places at the same time or be two things at the same is a complicated idea to wrap your head around. There is no equivalent in the “real” world to describe this behavior, so scientists had to come up with a new term to describe it: superposition.

One way physicists try to interpret this is by saying that it’s as if the qubit exists in multiple parallel universes. The best explanation I’ve seen was from MIT professor Allan Adams: his full lecture is available for free on [MIT OCW](https://www.youtube.com/watch?v=lZ3bPUKo5zc), so if you have an hour to spare, check that out. If not, the simplified version of multiple parallel universes will suffice for this article.

So, the idea is that if a qubit can be both 0 and 1 at the same time, as long as we don’t measure it, it could be doing many parallel computations at the same time.

With that in mind, we can use quantum gates to manipulate qubits. It accepts as inputs qubits in superposition, entangles them, manipulates probabilities according to what the program instructed it to do, and spits other qubits superposition as its output, which is then collapsed so we can measure the desired result.

**Qubits** assume a random discrete value when they collapse, and they could assume the form of the wrong answer. However, it’s possible to create quantum algorithms that would make bad answers cancel out and nudge the correct answer, so it’s more likely to appear as the result when the qubits are measured.

A **quantum computer** takes advantage of superposition by having qubits in superposition perform many different calculations at the same time, and only then making a measurement at the end of the computation where we retrieve the results that we are looking for.

![Entanglement](https://images.ctfassets.net/23aumh6u8s0i/1459k5sEGn3nETjOL2CIVP/8d1b15fe4602127fb343c8fe727c3152/quantum-sep2.jpg)

## Entanglement

If we only had to make individual qubits work, we’d already have reached a point where quantum computers could be commercially viable.

But what is desirable about quantum computing is the ability to make many computations in parallel, so the fact that we have to make them all work simultaneously is what makes this a hard problem.

When a group of quantum particles is generated in a way such that the state of each particle of the group can’t be described independently of the state of the others is what researchers call entanglement.

Entanglement is the other quantum propriety that makes quantum computers work. Changing the state of one entangled qubit will instantly change the state of the other qubit in a predictable manner.

This is what allows the power of quantum computers to grow much faster than classical computers: entangling additional qubits to a quantum computer produces an exponential increase in computing power.

<table style="width:100%">
 <tr style="background-color:#679790">
 <td> N </td>
 <td> Bits (2N)</td>
 <td> Qubits (22N)</td>
 <td> Relative to classical computer</td>
 </tr>
 <tr>
 <td>1</td>
 <td>2</td>
 <td>22</td>
 <td>4</td>
 </tr>
 <tr>
 <td>2</td>
 <td>4</td>
 <td>24</td>
 <td>16</td>
 </tr>
 <tr>
 <td>3</td>
 <td>8</td>
 <td>28</td>
 <td>256</td>
 </tr>
 <tr>
 <td>4</td>
 <td>16</td>
 <td>216</td>
 <td>65,536</td>
 </tr>
 <tr>
 <td>5</td>
 <td>32</td>
 <td>232</td>
 <td>4,294,967,296</td>
 </tr>
 <tr>
 <td>6</td>
 <td>64</td>
 <td>264</td>
 <td>18,446,744,073,709,551,616</td>
 </tr>
 <tr>
 <td>7</td>
 <td>128</td>
 <td>2128</td>
 <td>3.4028236692093846e+38</td>
 </tr>
 <tr>
 <td>8</td>
 <td>256</td>
 <td>2256</td>
 <td>1.1579208923731619e+77</td>
 </tr>
 <tr>
 <td>9</td>
 <td>512</td>
 <td>2512</td>
 <td>1.3407807929942597e+154</td>
 </tr>
 <tr>
 <td>10</td>
 <td>1024</td>
 <td>21024</td>
 <td>1.7976931348623159e+308</td>
 </tr>
</table>
 

![Applications](https://images.ctfassets.net/23aumh6u8s0i/3mnbZM85K33qOjz2RwHqe7/343ccd38e074e1a182d3181772423bee/quantum-sep5.jpg)

## Applications Of Quantum Computing

Harnessing the power of quantum mechanics will open a lot of new doors for problems that could be drastically sped up with increased parallelization.

Take drug research, for instance. The analysis of molecules for drug research and material science is a challenge today because calculating all of the quantum proprieties is very computationally expensive.

“It turns out it’s absolutely impossible to represent one simple little caffeine molecule in a classical computer,” says Bob Sutor, Vice President at IBM, in an [interview with CNBC](https://www.youtube.com/watch?v=u1XXjWr5frE), “because the amount of information you would need to represent it, the number of zeros and ones you would need is around 1048. The number of atoms on Earth is about 10 to 100 times that number. That’s never going to happen.”

The increased parallelization of quantum computers can help research solve this and other types of problems, including problems related to security, such as encryption.

![Encryption](https://images.ctfassets.net/23aumh6u8s0i/48pYjAzJ9yV0PE5UpR6Tgn/473da1cfc0630cbbd23629a38b37800b/quantum-sep4.jpg)

## Applications In Encryption

How quantum computing will affect encryption algorithms depends on the type of encryption.
For example, let’s consider public encryption and RSA for a moment.

> The security of RSA is based on the fact that finding a factor of a very, very big number is pretty much impossible.

The method we know for breaking encryption today is guessing which numbers could be the factors and see if it decrypts the data. If it isn’t, we try again, much like [guessing the correct password](https://auth0.com/blog/defending-against-password-cracking-understanding-the-math/) by hashing several different possible passwords. But there are so many numbers to try that it would take millions of years to find using classical computers.

While we don’t know for sure if there’s an algorithm to expedite this process using classical computers, we know that there’s one algorithm for quantum computers that would take exponentially less time: [Shor’s algorithm](https://en.wikipedia.org/wiki/Shor’s_algorithm).

Shor’s algorithm is a quantum algorithm for finding factors of a number. Say you want to find factors for number N. The algorithm starts with a guess of what number could be a factor, but then it keeps optimizing the guess until it eventually guesses a number that does share a factor with N.

Now, you could run Shor’s algorithm on a classical computer, but it would be extremely slow. It’s the optimizing part of the algorithm that makes use of the quantum properties to factor numbers in a fraction of the time (in the order of weeks, days, and even hours).

For symmetric encryption, the story is a little bit different. In 1996, Lov Grover devised what is now known as [Grover’s algorithm](https://en.wikipedia.org/wiki/Grover’s_algorithm). It’s a searching quantum algorithm that finds a desirable output in just N1/2 operations, where N is the sample size.

This means that a brute-force attack using Grover’s algorithm on a quantum computer could reduce the number of operations to brute-force a 128-bit AES key from 2128 operations in the worst-case scenario to 264 operations, which is well within range.

However, symmetric encryption is very resistant to quantum computers because, basically, all Grover’s algorithm is doing is halving the key size, so we can just double the keyspace. Using Grover’s algorithm on AES-256 would require 2128 operations, which is outside of range even for quantum computers in the conceivable future.

## The Future Of Quantum Computing

In October 2019, Google published a paper suggesting it had achieved “quantum supremacy,” that is, that their quantum computer could perform a task in minutes that would take a classical supercomputer 10,000 years.

But IBM disputed their findings, saying that an ideal simulation of the same task could be performed in 2.5 days and with greater fidelity on a classical supercomputer.

> They [claimed](https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/) the original meaning of the term “_was to describe the point where quantum computers can do things that classical computers can’t, this threshold has not been met._”

Adding qubits and keeping them in a superposition state is the biggest engineering challenge for researchers, as any minor external disturbance can knock a qubit out of the delicate state of superposition. As a result, quantum computers have to be kept isolated from all forms of electrical interference and operate at temperatures to absolute zero – about 100 times colder than outer space.

The most qubits we have available today are around 50, and that’s incredibly powerful, especially if you consider the power grows exponentially with each additional qubit. But they also have really high error rates because of those problems with interference.

Shor and Grover’s algorithms need a quantum computer with millions of qubits to work. Will this computer exist? Not for at least a couple of decades, some experts say.

Even if we add more qubits faster than Moore’s Law pace, it still will take over 10 or 15 years to reach the point where we could realistically attempt to break encryption algorithms used today.

Hopefully, by the time quantum computers have matured, mathematicians and cryptographers will have created a quantum-resistant version of encryption algorithms.

And while quantum computers will not substitute classical computers – researchers and large businesses that need to solve complex problems will probably do so by accessing them remotely – they’re far from science fiction at this point.	

“For those who are just getting started, they like to make noise about Sputnik and things like this. But let me give you some numbers,” says Sutor, “IBM has had quantum computers on the cloud since May of 2016. We’re not in any sort of Sputnik era. We’re not landing on the moon. But for those of you who like space history, I think we’re probably well into Mercury or Gemini.”

"quantum"