# Is lattice-based cryptography practical?

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?

• Is there anything further you'd like me to add to my answer?
– forest
Jul 30, 2019 at 7:43
• No great answer. Sorry for not selecting as answering my question. Jul 31, 2019 at 20:13
• No problem! I was just wondering if I was missing anything. :)
– forest
Jul 31, 2019 at 20:15

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.

• Could you elaborate a little bit on what you mean by "iron out the kinks" and standardize a particular implementation? Thank you! Aug 19, 2018 at 3:00
• @WilliamHird It just means that the different algorithms will be tested, people will try to break them and will debate their merits and drawbacks. The creators will argue why their algorithm should be chosen, etc. This is all part of the NIST standardization process, a "contest" to see which algorithm should be made the official standard.
– forest
Aug 19, 2018 at 3:03
• My understanding is that NTRU was invented by mathematicians at Brown University, which also has some of the most brilliant computer scientists on the planet. Why didn't Brown do the "whole package", the math, the algorithmic implementation, the protocols, ect. ? Why would you need a contest when you have all those geniuses in one place working on cryptography? Aug 20, 2018 at 9:20
• The answer to tha last question is known as Schneier’s law: “Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject the algorithm to years of analysis by the best cryptographers around.” Aug 20, 2018 at 16:25
• @FrédéricGrosshans: OK, makes sense, the team peer review concept, just don't let anyone from the NSA be part of the team unless you like back doors in your software. :-) Aug 20, 2018 at 17:46