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
LWEbased 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
BlumKalaiWasserman (BKW) algorithm.
Our webtool implements the following three attacks:

The SISbased 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 (BlumKalaiWasserman)
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
No comments:
Post a Comment