Paper 2024/1229
Benchmarking Attacks on Learning with Errors
Abstract
Lattice cryptography schemes based on the learning with errors (LWE) hardness assumption have been standardized by NIST for use as post-quantum cryptosystems, and by HomomorphicEncryption.org for encrypted compute on sensitive data. Thus, understanding their concrete security is critical. Most work on LWE security focuses on theoretical estimates of attack performance, which is important but may overlook attack nuances arising in real-world implementations. The sole existing concrete benchmarking effort, the Darmstadt Lattice Challenge, does not include benchmarks relevant to the standardized LWE parameter choices - such as small secret and small error distributions, and Ring-LWE (RLWE) and Module-LWE (MLWE) variants. To improve our understanding of concrete LWE security, we provide the first benchmarks for LWE secret recovery on standardized parameters, for small and low-weight (sparse) secrets. We evaluate four LWE attacks in these settings to serve as a baseline: the Search-LWE attacks uSVP, SALSA, and Cool & Cruel, and the Decision-LWE attack: Dual Hybrid Meet-in-the-Middle (MitM). We extend the SALSA and Cool & Cruel attacks in significant ways, and implement and scale up MitM attacks for the first time. For example, we recover hamming weight
Note: Accepted at Oakland S&P 2025
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Learning with ErrorsCryptanalysisBenchmarkingMachine Learning
- Contact author(s)
-
emily wenger @ duke edu
eshika @ meta com
mmalhou @ meta com
thieu @ wisc edu
klauter @ meta com - History
- 2024-10-10: last of 2 revisions
- 2024-08-01: received
- See all versions
- Short URL
- https://ia.cr/2024/1229
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1229, author = {Emily Wenger and Eshika Saxena and Mohamed Malhou and Ellie Thieu and Kristin Lauter}, title = {Benchmarking Attacks on Learning with Errors}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1229}, year = {2024}, url = {https://eprint.iacr.org/2024/1229} }