Paper 2023/340

SALSA PICANTE: a machine learning attack on LWE with binary secrets

Cathy Li, Meta AI
Jana Sotáková, Meta AI
Emily Wenger, University of Chicago
Mohamed Malhou, Meta AI
Evrard Garcelon, ENSAE - CREST
Francois Charton, Meta AI
Kristin Lauter, Meta AI

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 is based on module~LWE, and current publicly available PQ Homomorphic Encryption (HE) libraries are based on ring LWE. 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, SALSA, demonstrated a machine learning-based attack on LWE with sparse binary secrets in small dimensions ($n \le 128$) and low Hamming weights ($h \le 4$). However, this attack assumes access to millions of eavesdropped LWE samples and fails at higher Hamming weights or dimensions. We present PICANTE, an enhanced machine learning attack on LWE with sparse binary secrets, which recovers secrets in much larger dimensions (up to $n=350$) and with larger Hamming weights (roughly $n/10$, and up to $h=60$ for $n=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 ($4n$) and changes the distribution of the data to improve transformer training. We also improve the secret recovery methods of SALSA and introduce a novel cross-attention recovery mechanism allowing us to read off the secret directly from the trained models. While PICANTE does not threaten NIST's proposed LWE standards, it demonstrates significant improvement over SALSA and could scale further, highlighting the need for future investigation into machine learning attacks on LWE with sparse binary secrets.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. ACM CCS 2023
machine learninglearning with errorslattice-based cryptographycryptanalysis
Contact author(s)
cathyli @ meta com
ja sotakova @ gmail com
ewenger @ uchicago edu
fcharton @ meta com
klauter @ meta com
2023-10-31: last of 3 revisions
2023-03-07: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Cathy Li and Jana Sotáková and Emily Wenger and Mohamed Malhou and Evrard Garcelon and Francois Charton and Kristin Lauter},
      title = {SALSA PICANTE: a machine learning attack on LWE with binary secrets},
      howpublished = {Cryptology ePrint Archive, Paper 2023/340},
      year = {2023},
      doi = {10.1145/3576915.3623076},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.