In this paper, Coppersmith and Shamir used lattice reduction to attack NTRU. At the very end of the paper, they note that developing non-commutative variants of NTRU would be wise, in light of their attack, and indeed numerous such variants have been developed (e.g. here, here, and here). Moreover, the authors of such papers often claim that the non-commutativity of their constructions prevents Coppersmith's attack. But where in the original paper does the argument rely on commutativity? I have been unable to pinpoint the step in their argument which requires it.

  • 1
    $\begingroup$ You a right to be skeptical about those non-commutative variants: they do not prevent lattice attacks. $\endgroup$
    – LeoDucas
    Apr 20, 2021 at 6:36


Your Answer

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