Paper 2022/1343

Refined Strategy for Solving LWE in Two-step Mode

Abstract

Learning with Errors (LWE) and its variants underlie many lattice-based cryptosystems, making accurate concrete attack-cost estimates important for parameter selection. Practical primal attacks combine lattice-basis reduction with a final shortest-vector search, and their performance depends strongly on how these components are scheduled. We formalize the two-step strategy space considered in this work and propose PSSearch, a pruning-based method that selects a minimum estimated cost strategy under a specified reduction simulator and cost model. We instantiate the framework with a Pump-and-Jump BKZ (PnJBKZ) simulator supporting jump parameters \(J>1\), practical dimension-for-free settings, and LLL effects, together with a refined estimator for the dimension of the final SVP call. We integrate these components into a practical solver in G6K-GPU-Tensor and compare the PSSearch-selected strategies with its default heuristic strategy under comparable settings. On six TU Darmstadt LWE Challenge instances, the selected strategies achieve speedups of \(7.2\times\)--\(23.4\times\). Under the stated primal-attack and classical gate-count assumptions, the optimized two-step primal estimates for selected ML-KEM and ML-DSA parameter sets are \(3.4\)–\(4.6\) bits below the corresponding previous estimates; relative to the prescribed two-step baseline \(\mathsf{S}_0\), PSSearch provides an additional \(1.2\)–\(1.3\)-bit reduction. Along the tested relation \(\log_2 q=0.198n^{0.832}\), the empirically fitted advantage satisfies \(\Delta(\log_2T)=0.01887n-0.98\), where \(T\) denotes the estimated attack cost. These figures concern the primal-attack branch; the overall attack-cost estimate is determined by the minimum cost among all applicable attack families.