The associated NTRU lattice is of dimension $d=2N$. The public and private key sizes are both of length $O(N)=O(d/2)=O(d)$.

So where does the $d\log(d)$ appear?

Thanks in advance.


1 Answer 1


An NTRU public key is a polynomial of degree $d-1$ whose coefficients are elements in $\mathbb{Z}_q$. So the number of bits you need to represent it is $d\log{q}$. If q is of the same order as d, then this gives you $d\log{d}$. The private key, on the other hand, can be represented with $O(d)$ bits since the coefficients are all in the set $\{-1,0,1\}$.

  • $\begingroup$ So it is correct to say that both keys are at most $O(d\log(d))$? $\endgroup$
    – Leafar
    Jan 15, 2017 at 23:19
  • $\begingroup$ Sure, you can say that the private key is also $O(d\log{d})$, but you can be tighter and say that it's $O(d)$. $\endgroup$
    – Vadim L.
    Jan 17, 2017 at 16:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.