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?


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.

  • $\begingroup$ Could you elaborate a little bit on what you mean by "iron out the kinks" and standardize a particular implementation? Thank you! $\endgroup$ – William Hird Aug 19 '18 at 3:00
  • 3
    $\begingroup$ @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. $\endgroup$ – forest Aug 19 '18 at 3:03
  • $\begingroup$ 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? $\endgroup$ – William Hird Aug 20 '18 at 9:20
  • 1
    $\begingroup$ 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.” $\endgroup$ – Frédéric Grosshans Aug 20 '18 at 16:25
  • 3
    $\begingroup$ I don't think SVP is a trapdoor function. It should be the hardness assumption. $\endgroup$ – Shan Chen Sep 26 '18 at 19:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.