Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the general benefits of Lattice-based cryptography, such as:

  • Post quantum Security
  • Security from worst case scenario
  • Efficiency

What could the outlook of shifting from RSA \ ECC-based cryptography to the Lattice one (say NTRU) be?

Would that be feasible?

Are there any drawbacks?

share|improve this question
You can already use NTRU in TLS with WolfSSL. R-LWE is also available. While the NTRU protocol outperforms the R-LWE protocol both in terms of performance and key sizes, one major advantage of using R-LWE is that it provides security proofs via reductions to hard standard problems in ideal lattices, whereas NTRU is not known to be provably secure in the sense that no such reduction is known; as well, there are no known patents covering R-LWE. – Janus Troelsen Jan 31 at 21:19

Feasible? Sure, there are lattice algorithms that are competitive in performance with RSA.

However, there are drawbacks, like:

  • They've been studied less than RSA or ECC, especially the individual algorithms.
  • The most well studied system, NTRU, is patented.
  • No generic proof that I know of that there isn't a quantum algorithm to solve them.

The first one is why I doubt TLS will quickly move to lattices at least unless there's significant evidence that a quantum computer capable of breaking current crypto is practical. The third means that even then another public key system might be better, if such can be found.

share|improve this answer
So I guess we just need to get crypto-analysts to focus on that and, given that - as far as I know - there has been no particular shift in the academic world after the NSA-related revelations, I guess that just a prize on cracking NTRU (or other Lattice algos) could work. Would you agree? – XCore Jul 31 '14 at 13:01
It doesn't make sense to wait until there's significant evidence that a quantum computer capable of breaking current crypto is practical. Why? Because the first people who will likely get one are NSA. They have a yearly budget of $11.7B and they don't share their research or what goes on inside that place. Nobody except NSA will know when one is operational. In fact it's likely already operating right now. Refer to the Utah data center. A move to post quantum crypto for all protocols is necessary now. Not when it becomes available to the general public. By then it's too late. – NDF1 Jul 31 '14 at 21:19
Secondly, the drawback that they've been studied less than RSA or ECC is true, but how can you quantify what is a safe time period to wait in order for them to be considered "well studied"? 10 years? 20 years? 30 research papers? Perhaps what we need is a more open competition like AES or SHA3 where the better algorithms will get some proper cryptanalysis. However lets not let the NIST run it, but an international organisation of reputable cryptographers. Otherwise NSA will just co-opt the standard again. – NDF1 Jul 31 '14 at 21:38
I think you might add the fact that NTRU is patented to the list of reasons. It doesn't have anything to do with cryptography, but it is a very strong reason for a lot of people to bend over backwards searching for alternatives. – Henrick Hellström Aug 1 '14 at 8:23
@XCore I work mostly with independent software vendors. For them, GPL is as prohibitive as patents. – Henrick Hellström Aug 1 '14 at 10:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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