Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

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.

Future quantum computers are expected to break current online encryption algorithm. Researchers are developing new post-quantum schemes that aim to remain secure in the quantum era. Many of these schemes are based on a mathematical problem called Learning With Errors. We show that a machine learning model, trained on far larger datasets than previous attempts, and combined with a new method for recovering the secret key one bit at a time, can crack versions of the problem that earlier AI attacks could not solve. Our attack does not break any encryption currently in use, but it pushes the practical limit of what AI can achieve against this family of problems. Findings like these help cryptographers choose safer parameters and design defenses before next-generation encryption is widely adopted.