SALSA, PICANTE y VERDE: Machine Learning attacks on LWE with small sparse secrets

Learning with Errors (LWE) is a hard math problem with algebraic structure, underpinning many proposed Post-Quantum Cryptosystems (PQC). The only PQC key exchange standardized by NIST is based on module LWE, and current publicly available PQC 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.
This talk presents novel machine learning-based attacks against LWE schemes with sparse binary secrets. Our initial work, SALSA, demonstrated a proof of concept machine learning-based attack on LWE with sparse binary secrets in small dimensions (n<=128) and small Hamming weights (h<5). Our more recent work, PICANTE and VERDE, recovers secrets in much larger dimensions (up to n=512) and with larger Hamming weights (roughly n/10, and up to h=60 for n=350, h=63 for n=512). 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. In VERDE, we extend the attack to apply to sparse ternary and Gaussian secrets. 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.

Speaker Bio:
Kristin Lauter is an American mathematician and cryptographer whose research interest is broadly in application of number theory and algebraic geometry in cryptography. She is particularly known for her work in the area of elliptic curve cryptography. She was a researcher at Microsoft Research in Redmond, Washington, from 1999 - 2021, and the head of the Cryptography Group from 2008 - 2021; her group developed Microsoft SEAL. In April 2021, Lauter joined Facebook AI Research (FAIR) as the West Coast Head of Research Science. She became the President-Elect of the Association for Women in Mathematics in February 2014 and served as President from 2015 - 2017.