Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

Alberto Alfarano; Eshika Saxena; Emily Wenger; François Charton; Kristin Lauter

cs.CRApr 5, 2026

Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

Authors: Alberto Alfarano, Eshika Saxena, Emily Wenger, François Charton, Kristin Lauter

Organizations: Axiom Math · FAIR at Meta · Duke University

Abstract

The Learning with Errors (LWE) problem is a hard math problem in lattice-based cryptography. In the simplest case of binary secrets, it is the subset sum problem, with error. Effective ML attacks on LWE were demonstrated in the case of binary, ternary, and small secrets, succeeding on fairly sparse secrets. The ML attacks recover secrets with up to 3 active bits in the "cruel region" (Nolte et al., 2024) on samples pre-processed with BKZ. We show that using larger training sets and repeated examples enables recovery of denser secrets. Empirically, we observe a power-law relationship between model-based attempts to recover the secrets, dataset size, and repeated examples. We introduce a stepwise regression technique to recover the "cool bits" of the secret.

Figures & tables

Table 1: Largest Hamming weights recovered compared to C&C: Cool and Cruel attack ( Nolte et al., 2024 ) and SALSA: VERDE/PICANTE ( Li et al., 2023a ; Li et al., 2023b ) .

Hamming	Repetition	Data budget
weight	level	1M	4M	20M	50M
4	1x	–	✓	✓	✓✓
	2x	–	✓	✓	✓✓
	4x	–	✓✓	✓✓	✓✓
	10x	✓	✓✓	✓✓	✓✓
	20x	✓	✓✓	✓✓	✓✓

Table 2: Secret recovery for different Data Budgets (DB), and repetition levels. –: no secret recovered, ✓: recovery in the noiseless case only, ✓✓: recovery in all cases.

Number of secrets recovered. “-” indicates experiments could not be run: compute budget is too large

Cool bit recovery with Linear, Stepwise, and Dual Stepwise Regression, with 2 different data budgets, out of 20 secrets.

Highest Hamming weight/cruel bits

h/k

recovered: binary secret, harder setting.

Highest Hamming weight/cruel bits

h/k

recovered: binary secret, easier setting.

Expected recovery rate for different Hamming weights.

$R$	1	2	5	15	50
$C_{R}$	26.9	35.6	38.1	42.8	51.3
$\alpha_{R}$	0.70	1.31	1.45	1.58	1.95
CI	0.61 - 0.79	1.25 - 1.4	1.38 - 1.51	1.44 - 1.71	1.76 - 2.26

Table 13: Empirical scaling power law fitted parameters. CI (95% Confidence Interval for

\alpha_{R}

) is computed using bootstrapping.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

$n$	$\log_{2}q$	Dataset size	CPU hours	$c$	$\sigma_{cool}$	$\rho$	$\sigma_{e}$
		(millions)	(millions)
256	12	4	0.1	143	$0.30q/\sqrt{12}$	$0.18\%$	$0.88q/\sqrt{12}$
256	20	400	40.4	34	$0.23q/\sqrt{12}$	$1.05\%$	$0.90q/\sqrt{12}$
512	28	60	1.0	224	$0.19q/\sqrt{12}$	$0.12\%$	$0.70q/\sqrt{12}$
512	41	4	0.1	46	$0.15q/\sqrt{12}$	$0.18\%$	$0.80q/\sqrt{12}$

Appendix

Table 14: Reduction statistics . We report dataset size, CPU hours,

c

(size of the cruel region),

\sigma_{cool}

(standard deviation of the cool region),

\rho

(average non-diagonal pairwise absolute value correlation from the covariance matrix of

\mathbf{RA}

\sigma_{\epsilon}

(standard deviation of

\mathbf{R}\epsilon

$h$	CC embedding disabled	CC embedding enabled
28	5/16	8/16
30	0/16	4/16
33	3/16	7/16
34	0/16	5/16
36	0/16	1/16

Appendix

Table 15: Cool and cruel embedding comparison .

$N=256$ $\log_{2}q=20$
Data budget	Repetitions	$\alpha=0,\beta=1$	$\alpha=0.1,\beta=0.1$
50M	15x	60/8	65/8
100M	5x	65/8	65/8
200M	5x	65/8	65/8
400M	2x	65/8	70/8
$N=512$ $\log_{2}q=28$

Appendix

Table 16: Loss comparison .

		Linear regression			Stepwise regression			Dual stepwise regression
Cool bits	Total $h$	1M	2M	4M	1M	2M	4M	1M	2M	4M
8	18	20	20	20	20	20	20	20	20	20
18	41	8	20	20	20	20	20	20	20	20
23	52	0	3	7	0	9	20	13	20	20
28	63	0	0	0	0	0	2	0	3	19

Appendix

Table 17: Cool bits recovery

\bm{n=256},\bm{\log_{2}q=12}

assuming cruel bits have been recovered

		Linear regression				Stepwise regression				Dual stepwise regression
Cool bits	Total $h$	2M	4M	10M	20M	2M	4M	10M	20M	2M	4M	10M	20M
20	23	5	14	20	20	5	20	20	20	13	20	20	20
26	30	2	5	11	13	3	10	19	20	13	17	20	20
32	37	0	2	4	5	0	4	13	20	5	9	20	20
38	44	0	0	0	1	0	0	3	11	1	7	13	20
45	52	0	0	0	0	0	0	0	3	0	2	8	18

Appendix

Table 18: Cool bits recovery

\bm{n=256},\bm{\log_{2}q=20}

assuming cruel bits have been recovered

		Linear regression			Stepwise regression			Dual stepwise regression
Cool bits	Total $h$	1M	2M	4M	1M	2M	4M	1M	2M	4M
10	18	20	20	20	20	20	20	20	20	20
30	53	20	20	20	20	20	20	20	20	20
40	71	15	20	20	20	20	20	20	20	20
50	89	5	8	13	14	17	18	17	20	20

Appendix

Table 19: Cool bits recovery

\bm{n=512},\bm{\log_{2}q=28}

assuming cruel bits have been recovered

		Linear regression			Stepwise regression			Dual stepwise regression
Cool bits	Total $h$	1M	2M	4M	1M	2M	4M	1M	2M	4M
40	44	20	20	20	20	20	20	20	20	20
50	55	20	20	20	20	20	20	20	20	20
60	66	13	15	18	17	20	20	20	20	20
70	77	6	12	17	15	18	19	20	20	20
80	88	0	9	12	10	11	18	19	20	20

Appendix

Table 20: Cool bits recovery

\bm{n=512},\bm{\log_{2}q=41}

assuming cruel bits have been recovered

Highest Hamming weight and cruel bits recovered - ternary secret.

Table 18

Post-Quantum Cryptography

Post-quantum cryptography develops quantum-resistant algorithms and methods for deploying them in secure systems.

See all 15 papers

Discovering Lattice Reduction Strategies via Self-Play
Jun 13, 2026Mohamed Malhou, Kristin Lauter, Ludovic PerretReinforcement Learning RL for Combinatorial Optimization
FAIR, Meta Superintelligence Labs & Sorbonne Université CNRS, LIP6 Paris, France · EPITA, EPITA Research Lab (LRE) Le Kremlin-Bicêtre, France
CREBench: Evaluating Large Language Models in Cryptographic Binary Reverse Engineering
Apr 4, 2026Baicheng Chen, Yu Wang, Ziheng Zhou +4Software Reverse Engineering LLMs for Cybersecurity
Shanghai Qi Zhi Institute · The Chinese University of Hong Kong, Shenzhen · Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China +4
Learning to Detect Language Model Training Data via Active Reconstruction
Feb 22, 2026Junjie Oscar Yin, John X. Morris, Vitaly Shmatikov +2Membership Inference Attacks Privacy Leakage in Language Models
University of Washington · Cornell University · UC Berkeley +1

Jun 13, 2026J/K move · Enter open · S save

Discovering Lattice Reduction Strategies via Self-Play

Mohamed Malhou, Kristin Lauter, Ludovic Perret

FAIR, Meta Superintelligence Labs & Sorbonne Université CNRS, LIP6 Paris, France · EPITA, EPITA Research Lab (LRE) Le Kremlin-Bicêtre, France

Reinforcement Learning RL for Combinatorial Optimization Policy Learning

Open paper AskPDF arXiv

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.

Abstract

Post-Quantum Cryptography

Explore similar work

Discovering Lattice Reduction Strategies via Self-Play

CREBench: Evaluating Large Language Models in Cryptographic Binary Reverse Engineering

Learning to Detect Language Model Training Data via Active Reconstruction