Security estimation of LWE using “On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL”

Question

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

Answer 1

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$