3
$\begingroup$

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.

$\endgroup$
  • 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$ – TMM Feb 1 '17 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$ – 111 Feb 1 '17 at 17:54
4
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.