3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Hint: $X^N-1 = (X^{N/2}+1)(X^{N/2}-1)$. Use this to solve for the key modulo each factor. $\endgroup$
    – Chris Peikert
    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$
    – Chris Peikert
    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$
    – Chris Peikert
    Jul 12, 2016 at 16:08

0

Reset to default

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.