Lattice-Based Cryptosystems and Quantum Cryptanalysis
Bruce Schneier · Communications of the ACM · 2024
Lattice-Based Cryptosystems and Quantum CryptanalysisQuantum computers are probably coming, though we don't know when-and when they arrive, they will, most likely, be able to break our standard public-key cryptography algorithms.In anticipation of this possibility, cryptographers have been working on quantum-resistant public-key algorithms.The National Institute for Standards and Technology (NIST) has been hosting a competition a since 2017, and there already are several proposed standards.b Most of these are based on lattice problems.The mathematics of lattice cryptography revolve around combining sets of vectors-that's the lattice-in a multi-dimensional space.These lattices are filled with multi-dimensional periodicities.The hard problem c that's used in cryptography is to find the shortest periodicity in a large, random-looking lattice.This can be turned into d a public-key cryptosystem in a variety of different ways.Research has been ongoing since 1996, and there has been some really great work since then-including many practical public-key algorithms.On April 10, Yilei Chen from Tsinghua University in Beijing posted a paper describing a new quantum attack on that shortest-path lattice problem.It's a very dense mathematical paper-63 pages long-and my guess is that only a few cryptographers are able to understand all of its details.(I was not one of them.)But the conclusion was pretty devastating, breaking essentially all of the lattice-based fully homomorphic encryption schemes and coming significantly closer to attacks against the recently proposed (and NIST-approved) lattice key-exchange and signature schemes.However, there was a small but critical mistake in the paper, on the bottom of page 37.It was independently discovered by Hongxun Wu from Berkeley and Thomas Vidick from the Weizmann Institute in Israel eight days later.The attack algorithm in its current form doesn't work.This was discussed last week at the Cryptographers' Panel e at the RSA Conference.Adi Shamir, the "S" in RSA and a 2002 recipient of ACM's A.M. Turing award, described the result as psychologically significant because it shows that there is still a lot to be discovered about quantum