In ECC we have: if we know $G$ and $P=kG$, it is very difficult to find $k$. I wonder whether or not in NTRUEncrypt: if we know $h$ and $P=rh$, it is difficult to find $r$?

  • 1
    $\begingroup$ Aren't inverses in a field trivial since the order is known? $a^{-1} = a^{q-1}$, which you can compute in $\log(q)$ time $\endgroup$
    – bmm6o
    Jan 7 at 17:27
  • 1
    $\begingroup$ @bmm6o: you are right in a field of known order. I think the extended GCD allows to perform that in a field of unknown order. But as far as I understand (which is, not much), NTRUEncrypt does not operate in a field. If I'm right, that makes the title of the question wrong. Also: is the question to find $r$, or to find an $r$, or the/an $r$ with coefficient all in the set $\{-1,0,1\}$ (which I think is what breaks NTRUEncrypt)? $\endgroup$
    – fgrieu
    Jan 7 at 17:45
  • 1
    $\begingroup$ Since you know the maths angle please edit the question stating the mathematical question precisely for everyone's benefit. NTRU is not exactly the best known cryptosystem out there. $\endgroup$
    – kodlu
    Jan 7 at 20:03
  • 2
    $\begingroup$ NTRUEncrypt works modulo a polynomial over GF(q) (typically $x^n\pm1$). As @fgrieu said, polynomial GCD allows to invert elements easily. There can be non-invertible elements though, but it's rather rare (but non-negligible). There is definitely no hardness here. $\endgroup$
    – Fractalice
    Jan 7 at 20:04

Your Answer

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

Browse other questions tagged or ask your own question.