Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

Alberto Alfarano, Eshika Saxena, Emily Wenger, Francois Charton, Kristin E. Lauter
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:1865-1879, 2026.

Abstract

ML attacks on Learning with Errors (LWE) with binary or small secrets only succeed on LWE settings with very simple secrets. For example, they can recover secrets with up to three non-zero bits when models are trained on not-reduced LWE data, and three non-zero bits in the ”cruel region” [9] when BKZ pre-processing is applied. We show that larger training sets and the use of repeated examples in the training data allow the recovery of denser secrets. We empirically 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. Overall, these techniques allow for the recovery of denser binary secrets: up to Hamming weight $70$ (and $8$ cruel bits) for dimension $256$ $\log_2 q=20$ and $75$ (and $7$ cruel bits) for dimension $512$ $\log_2 q=41$ (vs $33$ and $63$ Hamming weight and $3$ cruel bits in previous works). We also demonstrate our methods’ effectiveness on denser ternary secrets, showing a substantial improvement over prior work.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-alfarano26a, title = {Improving {ML} Attacks on {LWE} with Data Repetition and Stepwise Regression}, author = {Alfarano, Alberto and Saxena, Eshika and Wenger, Emily and Charton, Francois and Lauter, Kristin E.}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {1865--1879}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/alfarano26a/alfarano26a.pdf}, url = {https://proceedings.mlr.press/v306/alfarano26a.html}, abstract = {ML attacks on Learning with Errors (LWE) with binary or small secrets only succeed on LWE settings with very simple secrets. For example, they can recover secrets with up to three non-zero bits when models are trained on not-reduced LWE data, and three non-zero bits in the ”cruel region” [9] when BKZ pre-processing is applied. We show that larger training sets and the use of repeated examples in the training data allow the recovery of denser secrets. We empirically 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. Overall, these techniques allow for the recovery of denser binary secrets: up to Hamming weight $70$ (and $8$ cruel bits) for dimension $256$ $\log_2 q=20$ and $75$ (and $7$ cruel bits) for dimension $512$ $\log_2 q=41$ (vs $33$ and $63$ Hamming weight and $3$ cruel bits in previous works). We also demonstrate our methods’ effectiveness on denser ternary secrets, showing a substantial improvement over prior work.} }
Endnote
%0 Conference Paper %T Improving ML Attacks on LWE with Data Repetition and Stepwise Regression %A Alberto Alfarano %A Eshika Saxena %A Emily Wenger %A Francois Charton %A Kristin E. Lauter %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-alfarano26a %I PMLR %P 1865--1879 %U https://proceedings.mlr.press/v306/alfarano26a.html %V 306 %X ML attacks on Learning with Errors (LWE) with binary or small secrets only succeed on LWE settings with very simple secrets. For example, they can recover secrets with up to three non-zero bits when models are trained on not-reduced LWE data, and three non-zero bits in the ”cruel region” [9] when BKZ pre-processing is applied. We show that larger training sets and the use of repeated examples in the training data allow the recovery of denser secrets. We empirically 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. Overall, these techniques allow for the recovery of denser binary secrets: up to Hamming weight $70$ (and $8$ cruel bits) for dimension $256$ $\log_2 q=20$ and $75$ (and $7$ cruel bits) for dimension $512$ $\log_2 q=41$ (vs $33$ and $63$ Hamming weight and $3$ cruel bits in previous works). We also demonstrate our methods’ effectiveness on denser ternary secrets, showing a substantial improvement over prior work.
APA
Alfarano, A., Saxena, E., Wenger, E., Charton, F. & Lauter, K.E.. (2026). Improving ML Attacks on LWE with Data Repetition and Stepwise Regression. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:1865-1879 Available from https://proceedings.mlr.press/v306/alfarano26a.html.

Related Material