As we see in https://estimate-all-the-lwe-ntru-schemes.github.io/docs/, only dual and primal attacks are the most important attacks against LWE and NTRU schemes. On the other hand, many attacks such as DBDD, Arrora & Ge, MITM and so on exist to deal with lattice hard problems. My question is that out of all these attacks, why are only the two mentioned attacks addressed?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
This is answered in the accompanying paper. I quote from page 4.
In this work, we restrict our attention to a subset of attacks on both families of problems. For LWE, we restrict our attention to the uSVP variant of the primal lattice attack as given in [BG14, ADPS16, AGVW17] and the dual lattice attack as given in [MR09 ,Alb17]. We disregard algebraic [AG11 , ACFP14] and combinatorial [AFFP14, GJS15, KF15, GJMS17] attacks, since those algorithms are not competitive for the parameter sets considered here in the sieving regime$^4$.
${}^4$ BKW-style algorithms do outperform BKZ in the enumeration regime for some medium-sized parameter sets. However, similarly to BKZ in the sieving regime, BKW requires $2^{\Theta(n)}$ memory.
