In the LWE problem there are two methods in order to choose secure parameters. The Lindner-Peikert and Micciancio-Regev method. The first method is an attack to BDD : find closest vector knowing the distance is bounded. The second method uses a distinguisher of SIS problem in order to attack the Decision-LWE. If someone applies one of the previous methods will finally find some values for the parameters of LWE. In this paper(table 1,p.15) this has be done for the case of Ring LWE. My question is, if someone knows a similar referance for the case of LWE that suggests specific values for the security parameters.
2
-
1$\begingroup$ There's still a lot of work being done on attacks on LWE and choosing parameters. If you want to make up-to-date choices, you may want to check more recent papers. (The most recent I can find on the Cryptology ePrint Archive for instance is this paper accepted for the upcoming Eurocrypt 2017 conference.) $\endgroup$– TMMFeb 1, 2017 at 14:43
-
$\begingroup$ @TMM thanks for the reference. Indeed, there is a description and a code in sage that it provides (secure) specific values for the LWE-parameters. You can add it as an answer, since my question was asking for reference. $\endgroup$– 111Feb 1, 2017 at 17:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
As mentioned in the comments, there is still a lot of active research being done in the area of algorithms for solving Learning With Errors, as clearly it's an important topic for estimating the security of LWE-based cryptography. Therefore it's probably already not a good idea to rely on papers from more than 5 years ago if you want your parameter choices to be accurate today.
For instance, at Crypto 2015 there were two important papers (here and here) on improving the complexity of BKW for solving LWE, leading to new parameter suggestions deemed "secure" at the time. Other methods for solving LWE such as those based on lattice basis reduction methods like LLL and BKZ (2.0), are directly influenced by the state-of-the-art complexity for SVP algorithms. There is still a lot of work going on in this direction as well, and the SVP challenge website gives you a reasonable idea of what is currently achievable in academic practice.
There are also attempts being made to develop more efficient quantum algorithms for solving LWE (as lattice-based cryptography is often claimed to be secure against quantum attacks), and just a few months ago there was some commotion because someone claimed to have found an efficient quantum algorithm for LWE. That turned out to be incorrect, but for choosing parameters you have to ask yourself whether you want to (slightly) increase your parameters to be quantum-secure, or go for smaller parameters and be only classically secure.
Then finally, even if you had full knowledge of the state-of-the-art methods for solving LWE, choosing parameters can still be done in various ways, ranging from aggressive/optimized to conservative/secure. Do you choose parameters such that the current best attack would take $2^{80}$ time? So that any small improvement to the algorithm might make the best attack take only $2^{60}$ time? Or do you choose parameters such that the current best attacks take at least $2^{120}$ time so that even if there are some improvements, you won't have to adjust your parameters in the near future?
In any case, there are several people/papers which attempted to choose concrete parameters following a certain approach, or criticize others for wrong parameter choices. Some more reading material in this direction from the last two years is below - many papers can be found by just searching the Cryptology ePrint Archive for the term "LWE".
- https://eprint.iacr.org/2017/047 - Considers attacks against small-secret LWE, breaking parameter choices previously deemed secure.
- https://eprint.iacr.org/2016/1126 - Discusses attacks and ways to choose parameters for their LWE-based encryption scheme.
- https://eprint.iacr.org/2016/659 - On choosing parameters for classical-LWE-based key exchange (as opposed to the ring-LWE variant New Hope mentioned below).
- https://eprint.iacr.org/2016/380 - Experimental results on running BDD attacks on LWE.
- https://eprint.iacr.org/2015/1222 - Asymptotic analysis of different approaches for LWE.
- https://eprint.iacr.org/2015/1092 - Ring-LWE-based key exchange with conservative parameter estimates. Won the internet defense prize and was being tested by Google.
