Some time ago I read an explanation of the key generation process of NTRUEncrypt, where it was stated that a polynomial $f$ should have "small" coefficients. It defined the number $df$, which configured the space of this polynomial to have coefficients in the set $\{-1,0,1\}$ such that $df$ is the number of 1s and $(df-1)$ is the number of -1s.

However, checking the submitted code in the third round of NIST competition, the sampling of $f$ seems to return coefficients in the set $\{0,1,2\}$. Is it because they are equivalent representations for the coefficients, being this one the best for making computations?

Also, the sampling function for $f$ needs a seed as a parameter called "uniformbytes". Based on the comments, I filled it with uniform random bytes from 0 to 255, but the number of 1s and -1s (suposing 2s are -1s) are really different from the $df$ and $(df-1)$ thing I read in the other work. Looking at how this sampling function is called in other parts of the code, I see that the seed is generated using some AES functions, which seemed pretty weird to me.

What is the correct way of sampling $f$, and what is that $df$ parameter that seems to be missing in the submitted code?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.