Paper 2026/1041

CoNAN: A Structure-Aware Framework for Lattice Cryptanalysis

Abstract

The security of structured lattice-based schemes is typically evaluated through the estimated cost of the best known lattice attacks, which in turn guides practical parameter selection. However, existing lattice security estimators typically evaluate different algebraic structures in a largely uniform manner, without fully accounting for the additional structure introduced by the underlying algebra. In this work, we show that such structure can, in certain instances, be exploited through algebra-induced homomorphisms to derive lower-dimensional lattice representations, thereby enabling more efficient attacks and yielding more realistic and in some cases significantly lower security estimates. To this end, we introduce CoNAN, a framework for incorporating algebraic structure into the security estimation of lattice-based constructions. We develop our main analysis in the context of NTRU-like constructions and further show that the framework naturally extends to several structured LWE-based schemes. Our framework reproduces known algebraic attacks against lattice-based constructions such as NTRU Composite~(EUROCRYPT 2001), BQTRU~(PQCrypto 2024), and multivariate LWE~(ANTS 2020). Furthermore, it highlights specific schemes, such as LWE over noncommutative group rings and semidirect products (DCC 2022, DCC 2026), where the underlying algebraic structure degrades concrete security by at least 60 bits relative to standard lattice estimator predictions. Beyond cryptanalysis, our work provides practical guidance for the secure design of future lattice-based schemes, particularly those instantiated over structured or noncommutative algebras.