In the NTRU cryptosystem, it is suggested to take $N$ prime. I want to understand why.

In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (as exercise) to suppose that $N$ is even, to consider the natural map $$\mathbb{Z}[X]/\langle X^N-1 \rangle \longrightarrow \mathbb{Z}[X]/\langle X^{N/2}-1 \rangle,$$ and prove that one can recover the private key by solving a lattice problem in dimension $N$, rather than in dimension $2N$.

Can someone explain how can we do this, please? Thanks in advance.

  • $\begingroup$ Hint: $X^N-1 = (X^{N/2}+1)(X^{N/2}-1)$. Use this to solve for the key modulo each factor. $\endgroup$ Jul 11, 2016 at 4:51
  • $\begingroup$ I have already tried it, I reduce the public key $h$ modulo $X^{N/2}-1$ and consider the associated lattice now of dimension $N$. Similarly, reduce $h$ modulo $X^{N/2}+1$ and do the same thing. Assume that I can find the private key for these two smaller lattices. I don't understand how can I recover the original private key... $\endgroup$
    – Leafar
    Jul 11, 2016 at 10:38
  • $\begingroup$ Use the Chinese Remainder Theorem to combine the two solutions. $\endgroup$ Jul 11, 2016 at 11:51
  • $\begingroup$ Right, thanks, how can I generalize for arbitrary composite $N$. For example, take $N=15$. What is the appropriate decomposition of the polynomial $X^{15}-1$? $\endgroup$
    – Leafar
    Jul 12, 2016 at 16:06
  • $\begingroup$ See the beginning of en.m.wikipedia.org/wiki/Cyclotomic_polynomial $\endgroup$ Jul 12, 2016 at 16:08


Your Answer

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