Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper enhances machine learning attacks against the Learning with Errors (LWE) problem by increasing training dataset sizes and repeating examples to recover denser secrets than previously possible. They empirically demonstrate a power-law relationship between dataset size, repeated examples, and the success rate of recovering secrets. A novel stepwise regression technique is introduced to efficiently recover the "cool bits" of the secret, further improving attack performance.
ML can now crack significantly denser LWE secrets thanks to larger training sets, repeated examples, and a clever stepwise regression technique.
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.