Paper 2023/968
SALSA VERDE: a machine learning attack on Learning with Errors with sparse small secrets
, FAIR, MetaAbstract
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.
Note: 18 pages
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. Minor revision. NeurIPS 2023
- Keywords
- machine learninglearning with errors
- Contact author(s)
-
cathyli @ meta com
ewenger @ meta com
zeyuanallenzhu @ meta com
fcharton @ meta com
klauter @ meta com - History
- 2023-10-27: revised
- 2023-06-20: received
- See all versions
- Short URL
- https://ia.cr/2023/968
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/968,
author = {Cathy Yuanchen Li and Emily Wenger and Zeyuan Allen-Zhu and Francois Charton and Kristin Lauter},
title = {SALSA VERDE: a machine learning attack on Learning with Errors with sparse small secrets},
howpublished = {Cryptology ePrint Archive, Paper 2023/968},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/968}},
url = {https://eprint.iacr.org/2023/968}
}
