4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Janus Troelsen
    Commented Jan 31, 2016 at 21:19

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ 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. $\endgroup$
    – NDF1
    Commented Jul 31, 2014 at 21:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – NDF1
    Commented Jul 31, 2014 at 21:38
  • 2
    $\begingroup$ 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. $\endgroup$
    – Henrick Hellström
    Commented Aug 1, 2014 at 8:23
  • 2
    $\begingroup$ @XCore I work mostly with independent software vendors. For them, GPL is as prohibitive as patents. $\endgroup$
    – Henrick Hellström
    Commented Aug 1, 2014 at 10:48
  • 1
    $\begingroup$ R-LWE is not patented and provably reduces to hard standard problems in ideal lattices. $\endgroup$
    – Janus Troelsen
    Commented Jan 31, 2016 at 21:22
0
$\begingroup$

In short:

Yes it's feasible with no significant drawbacks.

There would be slightly more work to do in establishing a channel, but after keys have been exchanged it's the same old symmetric encryption (ChaCha20 or AES).

Longer:

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:

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 13, 2016 at 12:05
  • $\begingroup$ @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. $\endgroup$
    – Kind Contributor
    Commented Mar 14, 2016 at 2:47
  • $\begingroup$ 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). $\endgroup$
    – Kind Contributor
    Commented Mar 14, 2016 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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