If you’re a normal person — that is, a person who doesn’t obsessively follow the latest cryptography news — you probably didn’t spend a lot of time on last week’s bombshell cryptography news. A new paper authored by Yilei Chen, “Quantum Algorithms for Lattice Problems“, has roiled the cryptography research community. The result is now being evaluated by experts in lattices and quantum algorithm design (and to be clear, I am not one!) but if it holds up, it’s going to be quite a bad day/week/month/year for the applied cryptography community.
Rather than elaborate at length, here’s quick four-bullet-point TL;DR.
(1) Cryptographers like to build modern public-key encryption schemes on top of mathematical problems that are believed to be “hard”. In practice, typically means that we know of no efficient algorithm that solves the problem. While many problems have been considered (and sometimes discarded), most schemes in use today are based on three problems: factoring (the RSA cryptosystem), discrete logarithm (Diffie-Hellman, DSA) and elliptic curve discrete logarithm problem (EC-Diffie-Hellman and ECDSA etc.)
(2) While these problems are thus far viewed as “hard”, this only applies to classical computers. Researchers have devised quantum algorithms that solve all of these problems efficiently (i.e., in polynomial time) — provided someone figures out how to build a quantum computer powerful enough to run them. Fortunately such a computer has not yet been built!
(3) Even though quantum computers are not yet powerful enough to break any real cryptography, the mere threat of future quantum attacks has inspired industry, government and academia to join forces Gandalf-style in order to address the problem right now. This isn’t just future-proofing: even if quantum computers take decades to build, future quantum computers could break messages we encrypt today! One conspicuous outcome is NIST’s Post-Quantum Cryptography (PQC) competition: this was an open competition designed to standardize “post-quantum” cryptographic schemes. Critically, these schemes are based on different mathematical problems — most notably, problems that don’t seem to admit efficient quantum solutions.
(4) Within this new set of schemes, several popular schemes are based on problems related to mathematical objects called lattices. Schemes based on lattice problems include Kyber and Dilithium. Lattice problems are also the basis of several efficient fully-homomorphic encryption (FHE) schemes.
This background sets us up for the big new result.
Chen’s new paper claims a new quantum algorithm that solves the “shortest independent vector problem” (SIVP, as well as GapSVP) in lattices with specific parameters. If it holds up, the result could (with numerous important caveats) allow future quantum computers to break schemes that rely on lattices with these parameters. The good news here is that the parameters are very specific: Chen’s algorithm does not immediately apply to the recently-standardized NIST algorithms such as Kyber or Dilithium. But there is a saying in our field that attacks only get better. If Chen’s result can be improved upon, then quantum algorithms could render obsolete an entire generation of “post-quantum” lattice-based schemes, forcing cryptographers and industry back to the drawing board.
And so: a great technical result. Also, possibly a mild disaster.
As previously mentioned: I am neither an expert in lattice-based cryptography nor quantum computing. The folks who are those things are quite busy trying to validate the writeup. For those searching for the latest developments, here’s a nice writeup by Nigel Smart that doesn’t address the validity of the quantum algorithm, but does talk about the possible implications for FHE and PQC schemes (TL;DR: bad for some FHE schemes, but really depends on the concrete details of the algorithm’s running time.) And here’s another brief note on a “bug” that was found in the paper, that seems to have been quickly addressed by the author.
Up until this week I had intended to write another long wonky about complexity theory, lattices, and what it all meant for applied cryptography. But unfortunately I’m going to hold onto that one for the moment.
Article Link: A quick post on Chen’s algorithm – A Few Thoughts on Cryptographic Engineering