1
$\begingroup$

I am reading literature related to NTRU cryptosystem. I have readen many questions in the current Cryptography stackexchange site, But, I still search for some answers:

  1. What makes so difficult to calculate the needed vector in NTRU's CVP and SVP problems? Can you give me an example?
  2. Why they use vectors and not numbers, as occurs in RSA for example?
  3. What is so special with vectors anyway?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The rings in which we work in the NTRU cryptosystem is $\mathbb{Z}[x]/(x^n-1)$ (one can work in this ring modulo an integer too). Hence the objects here are polynomials of the form $a_0+a_1x+\cdots+a_{n-1}x^{n-1}$ where the $a_i$'s are integers. Hence one can also represent any such object as a vector of cofficients $(a_0,a_1,\cdots,a_{n-1})$. When we manipulate vectors we omit the indeterminate $x$ which simplifies writing. It is known that we can associate to each NTRU cryptosystem an NTRU lattice falls in $\mathbb{Z}^{2n}$ this justifies why we use vectors. Concerning the security, it is believed that finding the private key is equivalent to finding a short vector in our lattice, this is hard especially when the dimension is very large. For more details about these questions you can follow the book 'An Introduction to Mathematical Cryptography', of Silverman and Pipher and Hoffstein' (section 7.10)

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ It is worth mentioning that your comment "one can work in this ring modulo an integer too" is generally important. I don't know if anyone has written a variant of this for NTRU, but LWE without modular reduction is easy. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented May 8 at 20:31
  • $\begingroup$ So, the idea is that a lattice is full of vectors, and the attacker should check all of them in order to find the smallest one? Am I right? $\endgroup$
    – someone
    Commented May 16 at 20:02
  • 1
    $\begingroup$ @someone a short vector is not unique in a lattice, for example the standard lattice $\mathbb{Z}^2$ has four short vectors namely $(\pm 1,0), (0,\pm 1)$ here the dimension is small ($n=2$) but when the dimension is very large the situation is quite different, it is hard to find in a reasonable time a short vector in a lattice. $\endgroup$
    – Muhammad rahmani
    Commented May 29 at 19:16

Your Answer

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

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