1
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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\}$.

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

Your Answer

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

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