LWE Attack Benchmarking

[Kristin Lauter]

Dear PQC Forum members,

 

We would like to invite your participation in our LWE Attack Benchmarking initiative.

Please visit our website for access to code and existing benchmarks for 4 attacks:

https://facebookresearch.github.io/LWE-benchmarking/

 

Benchmarks:

Current benchmark results are displayed here:

https://facebookresearch.github.io/LWE-benchmarking/benchmark

representing the work through May 2024 published in this paper:

https://eprint.iacr.org/2024/1229 to appear in IEEE Security and Privacy 2025.

 

Join our LWE Attack Benchmarking Effort

 

Our code can be found at https://github.com/facebookresearch/

 

We hope that by making our code available to the public, others will join us in

establishing experimental benchmarks for LWE attacks.

Our codebase contains 

(1) code to preprocess and generate LWE, RLWE, and MLWE data and

(2) implementations of four different attacks: 

·         transformer-based ML attack, 

·         dual hybrid MiTM attack, 

·         Cruel and Cool (CC) attack

·         USVP attack 

Details on how to set up and run the code are provided in the README.

 

Contributing. We invite contributors to reproduce our results, improve on these methods, and/or implement new LWE attacks. We actively welcome pull requests with new or

improved attacks or code improvements. 

 

Motivation:

Our approach is motivated by the need to study more carefully the effect on security of using small secrets and small error in standardized LWE settings like Kyber and Homomorphic Encryption.  In addition, as sparse secrets have been used in Homomorphic Encryption for efficiency and functionality, it is important to study sparse secrets as well.

 

We also noted several discrepancies between theory and experimental work on lattice reduction which reinforce the commonsense point of view that a multi-pronged approach to

ensuring security is warranted, and one obvious avenue is measuring concrete attack performance.

 

Results:

This work demonstrates the first successful LWE secret recovery on standardized KYBER and HE parameters–not yet general secrets but small, sparse secrets. For example,

• in the KYBER setting n = 256, k = 2, log2 q = 12 we recover binomial secrets with Hamming weight h ≤ 11 in < 36 hours (parallelized compute); 
• for the HE setting n = 1024, log2 q = 29, we recover Hamming weight h = 9 secrets in 13 hours.

 

Bad RNGs in lattice crypto:

We also emphasize the importance of using cryptographically appropriate RNGs for generating the randomness used in lattice-based crypto: we recover secrets with significantly higher Hamming weights from samples generated with an LCG (see Section 6.4 of https://eprint.iacr.org/2024/1229)

 

On behalf of the authors,

Emily Wenger, Eshika Saxena, Mohamed Malhou, Ellie Thieu, Kristin Lauter