Is lattice-based cryptography practical?

Question

How viable is lattice-based cryptography in a "practical" setting?

It has been said that lattice-based cryptography would be a "post-quantum" cryptography scheme, but is it feasibly implementable?

Answer 1

Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different types of algorithms, lattice-based algorithms dominate the submissions. These include NTRU and its variants, R-LWE, and FALCON (designed in part by one of our regulars!). Lattice-based cryptography itself is fairly well understood, exploiting lattice problems as a hardness assumption.

Lattice-based cryptography is one of only a few popular designs for post-quantum cryptography. There are others, such as code-based cryptography, multivariate polynomial cryptography, and hash-based signatures. Of those, code-based algorithms are the only class that could realistically compete with lattice-based algorithms, since it is used by the McEliece cryptosystem which itself has been around for quite a while and is well-studied. Multivariate polynomial cryptography is not as popular, and many of the proposed algorithms using it have been broken. Lastly, hash-based cryptography, while quite secure, is only useful for digital signatures, not key exchange. It additionally requires very large signatures. This explains why so many proposed algorithms are lattice-based.

Lattice-based cryptography is also very fast. For example, NTRU performs private key operations even faster than RSA, since the time increases with the cube of the key size for RSA, but quadratically for NTRU. The viability of lattice-based cryptography is undisputed. All we need to do now is iron out the kinks and standardize a particular implementation.

---

Update: A new attack was discovered which seriously weakens LWE and LWR schemes such as Kyber, Saber, and Dilithium, leading Daniel Bernstein to voice his concerns (emphasis mine):

Certainly it's disturbing to see Kyber-512 dropping from (1) supposedly "conservative" to (2) bleeding-edge in bit operations and then to (3) apparently broken in bit operations and bleeding-edge in real cost. The Kyber documentation really should stop using the word "conservative".

It's also deeply concerning that the uncertainties in evaluating costs of lattice attacks, such as the 2^30 uncertainty factor (2^135.5 through 2^165.5) in the round-3 Kyber submission, have been weaponized again and again to suggest that we shouldn't worry about a paper speeding up lattice attacks by a factor 2^5 or 2^10 or 2^15. The cumulative effect of years of such speedups has clearly been far more than 2^30. (The mascot for lattice-based cryptography should be a slow-boiled frog.)

This doesn't mean lattice-based cryptography is useless or inherently insecure, but it does mean it's still an evolving field and we need to wait to better understand it. Its risks are still being analyzed.