3
$\begingroup$

A new paper (https://eprint.iacr.org/2015/552.pdf) says:

This makes it possible to asymptotically and heuristically break the NTRU cryptosystem in subexponential time (without contradicting its security assumption).

Does this mean NTRU is less secure now? By how much?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ The attack in this paper is not as efficient as existing lattice-based attacks on practical parameters, so it does not affect the concrete parameters for NTRU (see the bottom of page 2). However, it is an asymptotic improvement over previous attacks, so it may lead to concretely lower security in the future. Note also that the attack requires nearly an exponential amount of space, which can make it hard to run in reality. $\endgroup$ – Chris Peikert Jun 24 '15 at 19:17
3
$\begingroup$

No, this result (as it stands) is of no practical use against NTRU as typically used. To quote the paper:

Note that there is a large value hidden in the o(1) term, so that our algorithm does not yield practical attacks for recommended NTRU parameters.

In addition, while it is subexponential, it's just barely so; they estimate the time as $2^{ (\ln 2/2+o(1))n/ \log \log n}$; even if we ignore the $o(1)$ term, this grows just slightly slower than an exponential function.

On the other hand, it may be that this attack might be useful against the use of NTRU as a somewhat homeomorphic cipher (which requires the error terms to be much smaller). In addition, perhaps this result can be sharpened to be strong enough to be useful against NTRU. So, while this isn't fatal to NTRU, the book isn't closed either.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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