1
$\begingroup$

I am looking at the primal attack against schemes in the second round of the NIST Post-Quantum Standardization Project. The cost of primal attack usually comes from an estimate described in NewHope which says that the error vector $e$ can be found if
$$\sqrt{\beta}\sigma\leq \delta^{2\beta-d-1}\text{Vol}(\Lambda)^{1/d}\quad\quad (1)$$

My concern is with the term $\sigma$ which is the standard deviation of the distribution from which vector $e$ is sampled. If the scheme is based on Learning with Errors problem (like FrodoKEM...), then the authors always specify this value. When the scheme is based on Learning with Rounding problem then I found in the specification document of Round5 formula how to calculate the deviation error $\sigma$. However, for the NTRU-based schemes (NTRU, NTRUprime) I could not find any formula for $\sigma$ and therefore I am not able to use the (1) estimation for primal attack (though in the specification document of NTRU and NTRUprime the cost of primal attack is evaluated).

Do you know how to estimate the cost of primal attack for the NTRU-based schemes? I.e. how to compute $\sigma$ for these schemes?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.