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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$– LeafarCommented 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.Commented Jan 17, 2017 at 16:53