Hardness of the LWE problem

One of the goals of the HEAT project is to better understand the hardness of the computational problems that underly SHE. One of those problems, the Learning with Errors problem, has been investigated repeatedly, but until now, there was no consistent way to specify security parameters. In order to resolve this and increase interest in LWE-based cryptosystems, we built an efficient online security estimation tool, available to anyone and straightforward to use.

The LWE problem has three parameters: a dimension n, a Gaussian width parameter s and a modulus q. In order to implement the complexity of attacks against LWE as a function of these parameters, we combined results from the literature of the last couple of years, with a main focus on the Bounded Distance Decoding attack and the Blum-Kalai-Wasserman (BKW) algorithm. 

Our webtool implements the following three attacks:

- The SIS-based attack is an attack against the LWE decision problem, as described by Micciancio and Regev. Given a pair (A,t), one searches a vector v orthogonal to the rows of A (mod q) and checks whether the inner product <v,t> is small. 

- The Bounded distance decoding (BDD) attack is a combination of lattice basis reduction and the nearest planes algorithm of Lindner and Peikert. It attempts to solve the LWE search problem by searching a lattice point close to t.

- The BKW (Blum-Kalai-Wasserman) algorithm approaches the LWE search problem as a noisy linear system and uses a blocked version of Gaussian elimination with back substitution. This method was recently optimised by Duc, Tramèr and Vaudenay. 

Designers of cryptosystems are no longer restricted to parameters proposed in papers, but can use this tool to query the security estimates of any set of LWE parameters. Finally, in order to further simplify the process of choosing LWE parameters, we also implemented the search for a suitable modulus q. A user can input parameters n and s and a security level sec to obtain the approximate value of log_2(q) that results in sec bits of security.

 

Lauren De Meyer