Let the modified NTRU be $h=f/g$ such that $f$ is not necessarily a short polynomial, is the NTRU problem still hard in this case?


1 Answer 1


Finding an answer is not hard, but answers will not be unique. Given $h$, pick your favourite short polynomial $g$ then compute $f=gh$ using multiplication mod $X^n-1$. As $f$ is unconstrained the resulting answer is a legitimate solution.

  • $\begingroup$ Thanks dear professor $\endgroup$
    – Don Freecs
    Feb 10 at 14:09
  • $\begingroup$ I don't know if I need to open another question or keep discussing here, another question how about distinguishing from uniform? $\endgroup$
    – Don Freecs
    Feb 10 at 18:17
  • 1
    $\begingroup$ @DonFreecs I think the answers will be pretty uniform as well; fixing invertible $g$ and letting $h$ run over all possible values will give all values of $f$ and vice-versa. $\endgroup$
    – Daniel S
    Feb 11 at 12:05

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.

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