3
$\begingroup$

I recently found this paper eprint which estimates security of LWE instantiations using an improved Dual attack. However, I got confused looking at their example in this site. For example, in the case of NewHope their example gives states that minimum operation (rop) using dual attack is $2^{371}$, whereas the minimum $\beta$ is $1168$. So following the NewHope paper the securty of NewHope should be $2^{.2075*1168}\ =\ 2^{242}$. Which indeed increases the security of the NewHope. I am wondering which should I take as the bit security?

Another question is definition of $\alpha$, in their paper they define $\alpha=\sigma*\sqrt{2\cdot \pi}/q$ whereas in the example they have taken $\alpha=\sigma^2/q$ (NewHope parameter).

|improve this question|||||
$\endgroup$
  • $\begingroup$ The results seem to have changed. A commit was made this morning that has changed the rop to $355.5$, down from the $371$ you mentioned. Also, $\beta = 1113$ now. (Still larger than the 962 from the NewHope paper.) $\endgroup$ – user47922 Jun 7 '17 at 17:26
  • 1
    $\begingroup$ Actually, the more I look over there, someone (maybe you) asked Martin Albrecht directly (if this is you, smart move!) If that answer is satisfactory, would you mind posting what you learned here and accepting your own answer? (it's encouraged here!) If not, will you highlight what you're still trying to learn? $\endgroup$ – user47922 Jun 7 '17 at 17:31
  • 1
    $\begingroup$ @galvatron Sorry, I did not see your message. Yes, it was me. I will update the answer. $\endgroup$ – Rick Jun 8 '17 at 7:44
4
$\begingroup$

I asked the question to the author directly. To answer the first question, authors of NewHope estimate their security very conservatively, whereas the estimator takes many other things into account. Specifically, here is the answer I got from the author.

Hi, Id' suggest to use their claimed security. To explain the differences:

  • The estimate you quote is the paranoid estimate which differs in the leading constant in the exponent from BKZ.sieve

  • New Hope conservatively assumes one SVP call suffices (we uses 8n which is less conservative)

  • New Hope uses a different technique to amplify success of the dual attack. For the parameter sets considered here, their estimate means amplification is essentially free, whereas the estimator assumes amplification has a considerable costs.

For the second part, the clculation of $\alpha$ was wrong. It should be $\sigma\cdot\sqrt{2\cdot\pi}/q$

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Awesome! Looks like your question was solved. Would you click the "accept" check mark so that others can benefit from your research? : ) $\endgroup$ – user47922 Jun 10 '17 at 0:58

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.