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
1  
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
1  
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
2  
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
2  
@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
1  
R-LWE is not patented and provably reduces to hard standard problems in ideal lattices. – Janus Troelsen Jan 31 at 21:22

The outlook for implementing Lattice into TLS will involve using both pre (RSA/ECC) and post (Lattice and others) Quantum asymetric cryptography in series. Lets call this DUAL for simplicity hereafter.

You then get the mathematical rigour of preQ RSA/ECC AND the highly probable security against Shor's algorithm from postQ Lattice. Having both does increase the time to start a secure channel, but that shouldn't be a problem, the rest of the session uses symmetric (AES and others).

Opportunity to embrace unpatented less-mature lattice algorithms

With this in mind, the maturity of the postQ algorithm becomes much less risky and therefore one could embrace an open postQ algorithm (R-LWE) avoiding patent issues.

Without DUAL, you are open to post-quantum decryption. With DUAL you are only "potentially" open to post-quantum decryption. (Because if they break the postQ part you don't have postQ protection anymore, but at least you still have mature preQ protection for classical threats).

Here are some links to much more detail, that I have written before and shouldn't be necessary for this answer:

share|improve this answer
    
Your statements here are too strong. It currently reads as an advertisements for your blog and ideas. You point to an article, probably by yourself, where you propose this idea (which isn't that outlandish or unique) of using crypto in series without actually proposing a scheme. DUAL seems to be just a single thought that has been given a name. Please rewrite your answer to explicitly answer the questions: "Would that be feasible? Are there any drawbacks?" You may of course throw your DUAL idea in the mix but please don't just make it only about your idea. – Maarten Bodewes Mar 13 at 12:05
    
@MaartenBodewes This is certainly not an ad. I'm not selling my ideas, blog or products. They are completely relevant to the answer. If there was already a related answer, then perhaps I would agree with you, but in the absence of such, these ideas need to be captured. I've been thinking in this area for over 5 years. If a researcher from a University linked to their own article, would it be a problem? There are few good people in this industry, lets work together. I called it DUAL as a handle, not marketing - a bit like dictionaryofobscuresorrows.com, you need a handle. – Todd Mar 14 at 2:47
    
I also think answers should be declarative, not questioning. I would assume most would test the answer relative to others and their own judgement. If there are others with the same idea(s) I would be more than happy to reference them - I'm sure others have a lot more credibility than me. But until then, if my thinking isn't that outlandish (aka. likely correct) I'm hoping others can suggest such additional references. How do we get Lattice based cryptography into TLS? Combining both (pre / post quantum cryptography). – Todd Mar 14 at 2:56

Your Answer

 
discard

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.