SalsaPicante: A Machine Learning Attack on LWE with Binary Secrets
Open Access
- 15 November 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 2606-2620
Abstract
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 [2], 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[51] demonstrated a machine learning-based attack on LWE with sparse binary secrets in small dimensions (n ≤ = 128) and low Hamming weights (h ≤ = 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.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- On the concrete hardness of Learning with ErrorsJournal of Mathematical Cryptology, 2015
- Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation2014
- BKZ 2.0: Better Lattice Security Estimates2011
- Faster exponential time algorithms for the shortest vector problem2010
- On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem2009
- Quantum Computation and Lattice ProblemsSIAM Journal on Computing, 2004
- Lattice basis reduction: Improved practical algorithms and solving subset sum problemsMathematical Programming, 1994
- Minkowski's Convex Body Theorem and Integer ProgrammingMathematics of Operations Research, 1987
- A hierarchy of polynomial time lattice basis reduction algorithmsTheoretical Computer Science, 1987
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982