Paper 2026/2527

How Secure are NTRU+ Keys? Analysing the Best Module Attacks

Abstract

A recent analysis of module-BKZ [Ducas–Engleberts–Perthuis, Asiacrypt'25] predicts subexponential speedups for lattice reduction on module lattices over cyclotomic fields whose conductor has small odd prime factors. This threatens NTRU+, the South Korean standard for key encapsulation, and related schemes; however, the short vectors one seeks to find are short in the coefficient geometry, whereas module-BKZ operates in the canonical geometry. We introduce relative canonical and relative coefficient embeddings, realising a module over a cyclotomic field $K$ as a module over any subfield $L$, and characterise when the two agree up to scaling: exactly when the radicals of their respective conductors $c$ and $\ell$ satisfy $\mathrm{rad}(c)/\mathrm{rad}(\ell) \in \{1,2\}$. Furthermore we quantify the distortion incurred in general when passing between embeddings, and hence identify the optimal subfield for module-BKZ and BKZ to use. Estimating the cost of the best attack with simulation-based models [Perthuis–Trenkić, PQCrypto'26], we find that the best module attack saves only 4–10 blocksizes, costing NTRU+ keys at most three bits of security in the Core-SVP model. We further extend the analysis of overstretched NTRU regimes [Ducas–Woerden, Asiacrypt'19] to the module setting, and find the fatigue point is reached sooner than with unstructured counterparts, though NTRU+ parameterisations remain safe.