# Explain: An NTRU key for a lattice of dimension $d$ has size only $O(d\log{d})$

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?

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\}$.
• So it is correct to say that both keys are at most $O(d\log(d))$? – Leafar Jan 15 '17 at 23:19
• 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)$. – Vadim L. Jan 17 '17 at 16:53