# Let’s talk about Post-Quantum Encryption

## Why all the fervor over a technology that’s still 8-10 years away?

We’ve discussed Quantum computing and the potential threat it poses to our current cryptosystems before, but after our COO spent a week out at the DigiCert roundtable discussing the future of PKI and encryption last week, we figured it would be a good time to double back and cover it again.

As we wrote about last month, DigiCert is partnering with ISARA on creating post-quantum IoT certificates that will be able to withstand the coming quantum computing revolution. But that revolution is still 8-10 years away. So why is there such a concerted effort to start creating post-quantum or quantum-proof encryption now?

Let’s hash it out…

## The threat of quantum computing

RSA or Rivest-Shamir-Adleman is the most widely used public key cryptosystem, so we’ll use it as our example when we discuss why quantum computing poses a threat. RSA is based on the factorization of prime numbers. But without knowing what those numbers are, and they are kept a secret, the best a computer can do is guess. Computationally, this isn’t necessarily difficult, it’s just the sheer number of possibilities that creates the problem.

Modern computers operate in binary on units called bits. The bit is either a 1 or 0. Quantum computing is different, practically requiring a degree in physics to truly comprehend, but it starts with the units, called Quantum Bits or Qubits. Qubits can be in superposition, meaning they be both a 0 and a 1 simultaneously. How this works is based on quantum physics and there’s an example with a coin in a box that is deeply unsatisfying, so let’s just leave at the idea they can be in superposition.

Now let’s talk about why quantum computing represents a threat to our current cryptosystem, this is excerpted from our own Jay Thakkar’s discussion of quantum-side of quantum computing:

Our normal computers can try only one combination at a time because it’s using bits. Quantum computer, on the other hand, works on qubits. Therefore, a quantum computer operating on a single qubit can try cracking it using two values at a time. Similarly, a Quantum Computer with two qubits can be in four positions. We can say that a Qunatum Computer with n qubits can try 2

^{n}combinations simultaneously. Bristlecone, which has 72 qubits, can try 2^{72}(4, 722, 366, 482, 869, 645, 213, 696) values.

So, while a 2048-bit RSA key is currently adequate owing to the fact that it would theoretically take a modern computer 6.4 quadrillion years to crack it, guessing one combination at a time. But the aforementioned Bristlecone, which is currently the world’s fastest quantum computer at 72 qubits, could crack a 2,048-bit RSA key in no time.

And that obviously represents a major problem, specifically for RSA, but for other cryptosystems as well. And RSA isn’t well-suited to combat this. The transition from 1024-bit keys to 2048-bit ones increased CPU usage between 4-7 times based on server type, etc. Going up to 3072-bit or 4096-bit key lengths would put even greater burden on the servers handling PKI functions, and the improvement to the security of those keys is not consummate. As the keys get bigger, the resources needed increase more and more while the gains being made are less and less.

This performance issue is partially why you’re already seeing a push towards more elliptic curve-based cryptosystems, though even those aren’t going to be quantum proof. Also, it’s worth noting that symmetric cryptosystems and hashing functions aren’t considered as at-risk as public key cryptosystems.

## What is Post-Quantum or Quantum-Proof encryption?

Right now, public key cryptosystems are based on one of three kinds of mathematical problem:

- Prime Factorization
- Discrete Logarithm
- Elliptic Curve

We’ve already covered Prime Factorization as much as we need to. We’ve got a great guide on ECC. And it’s probably not worth going too far into the weeds on logarithms because it’s only going to get us distracted. All of these would be vulnerable to quantum computing, which will probably be feasible in 8-10 years.

Again, this is less likely to affect hash functions and symmetric cryptosystem, where it’s believed that simply increasing key size should make systems like AES sufficiently quantum-resistant.

But Public Key cryptosystems are going to need an overhaul, and there’s work being done in several areas:

- Lattice-based cryptography
- Multivariate cryptography
- Hash-based cryptography
- Code-based cryptography
- Supersingular Elliptic Curve cryptography

DigiCert has partnered with ISARA on creating post-quantum certificates for Internet of Things (IoT) devices. ISARA is currently working on several post-quantum standards, two of which it has submitted to the National Institute for Standards in Technology (NIST). One is lattice-based (Qtesla), the other code-based (QC-MDPR KEM).

The idea is this: DigiCert and ISARA will create digital certificates that are underpinned by two public key cryptosystems, a current one like RSA and then a post-quantum one like Qtesla or QC-MDPR KEM.

While short-lived digital certificates like you see with SSL/TLS or digital signing can wait a little bit longer before being made quantum-resistant, the need is far more pressing with IoT devices. Many of these devices will need to be used for years, some could have lifespans lasting decades. As more and more devices that will still be in use in 8-10 years – when all of this quantum computing technology is estimated to become viable – come online, the need to ensure they won’t be vulnerable to quantum computing only grows.

There’s still a lot we need to figure out about how SSL/TLS and encryption in general will evolve in the face of the oncoming quantum revolution, endeavors like the DigiCert/ISARA one help gives us an idea of what it might look like.

*As always, leave any comments or questions below…*

The statement that the 72 qubit Bristlecone can break RSA encryption in no time is not correct. It will take something like 40-100 million qubits to implement Shor’s algorithm to factor a large number and break RSA. This is because quantum qubits need a massive amount of error correction to perform reliably. We are still 10 or more years away from seeing a quantum computer that large. However, it is still wise for end users to start their planning now for use of post-quantum cryptography because it will take many years to implement a conversion of our global digital infrastructure to use these new encryption algorithms.

Doug Finke

Managing Editor

Quantum Computing Report

https://quantumcomputingreport.com