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, culminating in a fully structured construction defined over the group ring of the dihedral group. Our proposal may be viewed as a follow-up to the early noncommutative construction of Hoffstein and Silverman. We further provide a complete reference implementation of the structured construction under two proposed parameter sets, Plausible and Paranoid, demonstrating both the efficiency and compactness of our scheme in comparison with NTRU-HPS and the state-of-the-art non-commutative NTRU variant.

Note: As an initial step toward evaluating the hardness of the ANTRU assumption, we have formulated it as a problem in the NSUCRYPTO 2025 Olympiad https://nsucrypto.nsu.ru/olymp/2025/.