Discovering Lattice Reduction Strategies via Self-Play
For cryptographers and computational number theorists, this work provides a novel method to improve lattice reduction, a fundamental tool in cryptography, though it is currently limited to small training dimensions.
The authors used deep reinforcement learning to discover lattice reduction strategies that outperform LLL, achieving better basis quality with fewer operations on small lattices and generalizing zero-shot to higher dimensions up to n=32.
The Lenstra-Lenstra-Lovász (LLL) algorithm is a seminal contribution to computer science used for lattice basis reduction, yet its polynomial-time outputs produce bases that are far from optimal as the dimension grows. We show that deep reinforcement learning can discover strictly superior, generalizable reduction strategies by interacting with the primitive action space of LLL. We formulate lattice reduction as a single-player Markov Decision Process (MDP) and train a deep residual network using an AlphaZero-style self-play pipeline augmented with adaptive-horizon MCTS (Monte Carlo Tree Search), which couples multi-step network predictions with an entropy-gated expansion mechanism. The resulting policy, DeltaStar, is trained exclusively on small $8$-dimensional $q$-ary lattices and requires fewer primitive row operations than LLL. Crucially, it generalizes zero-shot to unseen moduli and higher dimensions up to $n=32$ without retraining.