SALSA VERDE: a machine learning attack on LWE with sparse small secrets

Learning with Errors (LWE) is a hard math problem used in post-quantum cryptography. Homomorphic Encryption (HE) schemes rely on the hardness of the LWE problem for their security, and two LWE-based cryptosystems were recently standardized by NIST for digital signatures and key exchange (KEM). Thus, it is critical to continue assessing the security of LWE and specific parameter choices. For example, HE uses secrets with small entries, and the HE community has considered standardizing small sparse secrets to improve efficiency and functionality. However, prior work, SALSA and PICANTE, showed that ML attacks can recover sparse binary secrets. Building on these, we propose VERDE, an improved ML attack that can recover sparse binary, ternary, and narrow Gaussian secrets. Using improved preprocessing and secret recovery techniques, VERDE can attack LWE with larger dimensions (n = 512) and smaller moduli (log 2 q = 12 for n = 256), using less time and power. We propose novel architectures for scaling. Finally, we develop a theory that explains the success of ML LWE attacks. Public-key cryptosystems are the main solution for secure communication over the Internet. Public keys can be used to encode messages or verify digital signatures to or from a user with the corresponding private key. Security relies on the fact that recovering the private key from the public data requires solving a computationally hard math problem. Most currently deployed public-key systems are based on RSA [47] , which relies on the hardness of factoring large numbers into products of primes. Unfortunately, large-scale quantum computers will enable implementation of Shor's algorithm [52] , which can factor integers in quantum polynomial time and break such systems. As a result, new hard problems are sought to serve as the basis of post-quantum public key cryptography (PQC). The US National Institute of Standards and Technology (NIST) ran a 5 year competition to define future PQC standards [2], and standardized 4 PQC systems in July 2022 [17] . Two of these rely on special cases of the same hard (and Shor-free) problem: Learning with Errors (LWE). The Learning With Errors problem (LWE) assumes that it is hard to recover a secret vector s, given many LWE samples (a, b). In a LWE sample, each a is a random vector of n integers modulo q (n is the dimension and q is the modulus), and b is a noisy modular inner product of a and the secret key s-that is, b = a • s + e mod q, with the error e drawn from a Gaussian distribution of * Co-senior authors 37th Conference on Neural Information Processing Systems (NeurIPS 2023).