Welcome to the resource topic for 2023/968
Title:
SALSA VERDE: a machine learning attack on Learning with Errors with sparse small secrets
Authors: Cathy Yuanchen Li, Jana Sotáková, Emily Wenger, Zeyuan Allen-Zhu, Francois Charton, Kristin Lauter
Abstract: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 small secrets, and the HE community has considered standardizing small sparse secrets to improve efficiency and functionality. However, prior work, SALSA and PICANTE, showed that machine learning (ML) attacks can recover sparse binary secrets. Building on these, we propose VERDE, an improved ML attack that can recover sparse binary, ternary, and small 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.
ePrint: https://eprint.iacr.org/2023/968
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .