Understanding choice of $\alpha$ in the estimator.

Create issue
Issue #21 resolved
Rick created an issue

Hi, I quite did not understand how you have chosen alpha in your examples(https://bitbucket.org/malb/lwe-estimator). The paper says sigma=alphaq/(sqrt(2Pi)) i.e alpha=sigmasqrt(2Pi)/q. It is fine with your example of TESLA. But in the case of NewHope where the \sigma=8, you have taken \alpha-8/q i.e \alpha=\sigma^2/q. I quite did not understand the reason. Can you please elaborate?

Comments (4)

  1. Martin Albrecht repo owner

    σ is not the standard deviation but the Gaussian noise parameter, i.e. the standard deviation is α⋅q/\sqrt{2π}. New hope has a standard deviation of ≈ \sqrt{16/2}, so you're right, it should be 7.1 not 8

  2. Rick reporter

    Hi Martin, Thank you for your response. One more small question, In the security estimation of NewHope, the tool returns lowest rop=2^355 but the BKZ block size is 1113. Now the NewHope paper estimates security as 2^{.2075*block_size} \approx 2^{230}. I am not sure what should I take as the bit security? Nevertheless, both of the approach actually reports more security of NewHope than the original paper.

  3. Martin Albrecht repo owner

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

    1. The estimate you quote is the paranoid estimate which differs in the leading constant in the exponent from BKZ.sieve
    2. New Hope conservatively assumes one SVP call suffices (we uses 8n which is less conservative)
    3. 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

    You can run

    sage: _  = estimate_lwe(n, alpha, q, reduction_cost_model=lambda beta, d, B: 2^(.2075*beta))
    

    which takes care of 1. and 2.

  4. Log in to comment