9
$\begingroup$

Today a new paper appeared on ePrint, "Improved Provable Reduction of NTRU and Hypercubic Lattices". It claims that:

this is the first provable result showing that breaking NTRU lattices can be reduced to finding shortest lattice vectors in halved dimension, thereby providing a positive response to a conjecture of Gama, Howgrave-Graham and Nguyen at Eurocrypt 2006.

I'm wondering what are the consequences of this new attack. Does it mean that NTRU now needs parameters twice as big as those currently proposed to remain secure? Or is it only proving that a previously conjectured bound works? Also, how does this affect variants such as Streamlined NTRU Prime?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

Dan Bernstein (one of the authors of Streamlined NTRU prime) has the following initial comment.

My initial assessment of https://eprint.iacr.org/2024/601 is that

  1. the "halved dimension" is actually what people normally call the "dimension" for NTRU
  2. Section 4 is understating what the usual attacks accomplish
  3. all 2024/601 exponents are above the usual exponents

Here, "exponent" means the exponent $c$ in the attack cost $2^{cn}$, so this third point is saying the attacks of 2024/601 are less effective than current attacks. It is possible that these current attacks are heuristic (and 2024/601 is fully provable), e.g. that 2024/601 may have merit even without advancing the state of the art of practical cryptanalysis of NTRU, but I'm the wrong person to comment on that.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Indeed, the article tries to be clear in its achievement, however, if they believe broken it, the title would be Farewell NTRU. $\endgroup$
    – kelalaka
    Commented Apr 22 at 23:24
  • 1
    $\begingroup$ @mark could you improve the phrasing of the attacks [...] are worse ? The term worse seems ambiguous to me depending on whether you are attacking or defending, and while I think I can guess from the context which one is meant here, I am not certain. $\endgroup$
    – Torque
    Commented Apr 23 at 8:05
3
$\begingroup$

This is a paper about provable lattice reduction, not about new attacks. It is about getting the theory catch up with practice and heuristic. The paper does not claim otherwise.

Improve this answer
$\endgroup$

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.