I've found this task in the "Introduction Mathematical Cryptography by Jeffrey Hoffstein":

The guidelines for choosing NTRUEncrypt public parameters (N, p, q, d) in-clude the assumption that gcd(N, q) = 1. Suppose instead that Alice takes q = N , where as always, N is an odd prime.

(a) Make a change of variables x = y + 1 in the ring Z[x]/(xN − 1), and show that the NTRU lattice takes a simpler form.

(b) Can you find an efficient way to break NTRU in the case that q = N that does involve lattice reduction? (This appears to be an open problem.)

I have no idea where to start. I didn't find any valuable information on the net. Can anyone offer me literature that explores this particular problem?(Or maybe the step with the change of variables x = y + 1)

  • 1
    $\begingroup$ What is $(y + 1)^q \bmod q$? $\endgroup$ Jul 2, 2022 at 19:39
  • $\begingroup$ 1+y^q, I guess. Thanks! $\endgroup$
    – SarkoxedaF
    Jul 4, 2022 at 15:50


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.

Browse other questions tagged or ask your own question.