SalsaPicante: A Machine Learning Attack on LWE with Binary Secrets

Learning With Errors (LWE) is a hard math problem underpinning many proposed post-quantum cryptographic (PQC) systems. The only PQC Key Exchange Mechanism (KEM) standardized by NIST [13] is based on module LWE, and current publicly available PQ Homomorphic Encryption (HE) libraries are based on ring LWE [2]. The security of LWE-based PQ cryptosystems is critical, but certain implementation choices could weaken them. One such choice is sparse binary secrets, desirable for PQ HE schemes for efficiency reasons. Prior work S [51] demonstrated a machine learningbased attack on LWE with sparse binary secrets in small dimensions ( ≤ 128) and low Hamming weights (ℎ ≤ 4). However, this attack assumes access to millions of eavesdropped LWE samples and fails at higher Hamming weights or dimensions. We present P , an enhanced machine learning attack on LWE with sparse binary secrets, which recovers secrets in much larger dimensions (up to = 350) and with larger Hamming weights (roughly /10, and up to ℎ = 60 for = 350). We achieve this dramatic improvement via a novel preprocessing step, which allows us to generate training data from a linear number of eavesdropped LWE samples (4 ) and changes the distribution of the data to improve transformer training. We also improve the secret recovery methods of S and introduce a novel cross-attention recovery mechanism allowing us to read off the secret directly from the trained models. While P does not threaten NIST's proposed * Co-first authors.