LWE Attack Benchmarking Project

Kristin Lauter and her colleagues at Facebook research recently announced a project to benchmark attacks against LWE.

The announcement was on the post-quanum crypto mailing list.

They state: “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.”

I’m most interested in the applications to FHE, for which they state their strongest result: “for the HE setting n = 1024, log2 q = 29, we recover Hamming weight h = 9 secrets in 13 hours.”

I don’t know of any places where FHE uses sparse secrets. For stuff I’m familiar with, the hamming weight is usually n/2 = 512 or larger. But it’s an interesting project to keep track of!

Another interesting note is that one of the attacks is a transformer-based attack. This goes back to a paper by the same authors called SALSA, though the best performing attack is one called the Cruel and Cool attack.

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