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.
How RSA WorksThe 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.
How Diffie-Hellman Works
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.
Wouter Castryck & Thomas Decru, "An efficient key recovery attack on SIDH"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.
Nginx, OpenSSL, and Quantum-Safe CryptographyThe 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.
Next:
What Does "FIPS" Mean?
People often casually speak of "FIPS compliance", but that could mean multiple things. If it matters — and why else speak of it — we must be careful.
Latest:
Routing Through Starlink
By the mid 2020s, Internet connections in remote areas frequently used Starlink, the satellite system owned by the pro-fascist eugenicist Elon Musk. Let's see how Starlink works.
Previous:
How Does Asymmetric Cryptography Work?
Asymmetric cryptography is a vital tool, but how does it work? We have two major solutions now, with more on the way. Learn how asymmetric ciphers protect information.
What's the Point of Asymmetric Encryption?
Asymmetric encryption is often described as useful for "small messages", but that's misleading. They're absolutely vital in cryptographic protocols such as key agreement and authentication.
Learn How to Write a Shell Script to Analyze Logs
Write a shell script to analyze logs and generate a report. We'll start by reporting the web server's 20 most popular pages.
How to Start Writing Scripts
Someone asked me, "How can I learn scripting?" It's easy to get started! Bash or Python or whatever!