Paper 2025/1988

Almost NTRU: Revisiting Noncommutativity Against Lattice Attacks

Abstract

NTRU is one of the most extensively studied lattice-based cryptographic schemes and is widely regarded as a strong candidate for post-quantum security. The most effective attacks on NTRU are lattice-based or lattice-related, which naturally guide the choice of parameters to achieve the desired security levels. In 1997, Hoffstein and Silverman proposed a variant of NTRU based on a noncommutative algebraic structure, claiming that it would mitigate lattice attacks. However, their scheme was later shown to be vulnerable to an algebraic attack by Coppersmith. Although several subsequent attempts have been made in the literature to develop noncommutative variants of NTRU, most of these designs have either been shown to be vulnerable to algebraic attacks or have failed to directly address lattice-based attacks. In this work, we revisit the problem of constructing a noncommutative analog of NTRU that offers stronger resistance against direct lattice attacks. Firstly, we conceptualize the problem by introducing an almost unstructured variant, and then refine this idea towards a more compact instantiation by introducing a semi-structured variant. Our proposal may be viewed as a follow-up to the early noncommutative construction of Hoffstein and Silverman. We further discuss the requirements towards having a fully structured construction in this paradigm.

Note: Updated: the fully structured variant has been removed as it was vulnerable to a lattice attack. We leave the design of a fully structured ANTRU instantiation as future work.