Bob's Blog

Quantum Computing and Quantum-Safe Cryptography

I recently explained how asymmetric encryption is absolutely vital for protecting information and your identity. I mentioned that we have had two major forms for some time. RSA was publicly described in 1977, and Elliptic Curve Cryptography or ECC was first suggested in 1985.

I mentioned that both base their security on the difficult of solving a trapdoor problem, a math problem that is much harder to solve in one direction than the other.

Toward the end of that earlier post, I briefly mentioned the need for what are variously called quantum-safe or quantum-resistant or post-quantum algorithms. Because we believe that a large enough general-purpose quantum computer could quickly solve the trapdoor problems used by RSA and ECC, we need new asymmetric ciphers based on totally different mathematics.

The U.S. National Institute of Standards and Technology or NIST has been leading a major project to develop post-quantum cryptography.

We Need New Trapdoor Functions

The trapdoor problems used so far have been the factoring problem and the discrete logarithm problem. They must be replaced.

The security of RSA is based on the difficulty of the factoring problem. Greatly simplified, a private key consists of two large prime numbers, each on the order of 600 to 1200 digits long. The public key is the product of the two primes.

The security of classic Diffie-Hellman is based on the difficulty of the discrete logarithm problem, solving:
ga mod p = c
for a, given g, p, and c.

The security of elliptic-curve cryptography also depends on the difficulty of the discrete logarithm problem.

In 1981, Richard Feynman suggested using computing systems based on quantum mechanics to simulate and study quantum systems. It wasn't clear how one might build such a system, but it was a promising idea.
Richard Feynman, "Simulating Physics with Computers"

In 1994, Peter Shor published an algorithm for using a quantum computer to rapidly find the prime factors of an integer. Within a year he had also published related algorithms to rapidly solve the discrete logarithm problem.
Peter Shor, "Algorithms for quantum computation: Discrete logarithms and factoring" Peter Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"

Shor's algorithms were understood to require a quantum computer with an adequate number of adequately stable qubits or quantum computational units. No one knew how to build such a thing, or even if it definitely could be built. But if it could be built, we knew what the algorithms could do.

So far there have only been proofs of concept, like the 2001 IBM project that used a 7-qubit computer to factor 15 into its prime components 5 and 3. By 2012, teams were factoring 21 into primes 7 and 3. In 2019 they tried but failed to factor 35 into 7 and 5.

A study in 2023 showed that Shor's algorithm cannot be used in general until quantum error correction can be worked out. "Mostly stable" or "stable enough" just isn't good enough against certain classes of primes.
Jin-Yi Cai, "Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise"

We know that Shor's algorithm works.

And, we know how to build a functional (if too unstable) qubit which can do the needed computation.

It's an engineering problem at this point, how to improve and enlarge the physical solution. The theory is understood, it's a matter of making it practical.

In 2023, Oded Regev published a significant speed-up of Shor's algorithm.
Quanta Magazine overview Oded Regev, "An Efficient Quantum Factoring Algorithm"

New Trapdoor Functions

There are three classes of trapdoor functions for which some specific problems are believed to be quantum safe:

Lattice-based — Based on finding the nearest point in a high-dimensional lattice. These have been used to develop both KEM or key encapsulation mechanism schemes including CRYSTALS-Kyber, FrodoKEM, and others; and signing algorithms including CRYSTALS-Dilithium. These have been selected by NIST.

Code-based — Based on error-correcting codes, including the McEliece algorithm and variants. The European Commission's Post-Quantum Cryptography Study Group has recommended the McEliece public-key encryption algorithm.

Hash-based — Based on using hash functions, NIST selected SPHINCS+ as an algorithm for hash-based digital signatuves.

Other schemes were initially thought to be promising, but at least some of the algorithms based on the concepts have been broken. Multivariate cryptography uses the solution of nonlinear equations in many variables; one scheme was broken in February 2022. Isogeny-based cryptography finds a mapping between two elliptic curves. The Supersingular Isogeny Diffie-Hellman or SIDH key exchange protocol was an initial selection in NIST's competition, but it was broken in July 2022. The initial break required about 62 minutes on a single 2.60 GHz CPU core of a laptop, definitely a classical or non-quantum attack.

Work is Underway

In August 2023, NIST published draft standards for algorithms derived from CRYSTALS-Kyber, CRYSTALS-Dilithium, and SPHINCS+. Those cover module-lattice-based key encapsulation mechanisms, module-lattice-based digital signatures, and stateless hash-based digital signatures.

The Open Quantum Safe project provides shared libraries implementing a variety of proposed post-quantum algorithms. I have experimented with these, and have managed to get the Nginx web server to support Kyber and Frodo based KEMs. However, there really aren't yet any browser clients that are generally useful with this!

Hopefully we will soon reach the point where both web servers and web browsers will routinely support a range of post-quantum or quantum-safe KEMs.