An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero

Let f and g be polynomials of a bounded Euclidean norm in the ring Z[X]/ Xⁿ+1 . Given the polynomial [f/g]q∈ Zq[X]/ Xⁿ+1 , the NTRU problem is to find a,b∈ Z[X]/ Xⁿ+1 with a small Euclidean norm such that [a/b]q=[f/g]q . We propose an algorithm to solve the NTRU problem, which runs in 2^O(log ²[STIX]x1D706) time when g , f , and g⁻¹ are within some range. The main technique of our algorithm is the reduction of a problem on a field to one on a subfield. The GGH scheme, the first candidate of an (approximate) multilinear map, was recently found to be insecure by the Hu–Jia attack using low-level encodings of zero, but no polynomial-time attack was known without them. In the GGH scheme without low-level encodings of zero, our algorithm can be directly applied to attack this scheme if we have some top-level encodings of zero and a known pair of plaintext and ciphertext. Using our algorithm, we can construct a level- $0$ encoding of zero and utilize it to attack a security ground of this scheme in the quasi-polynomial time of its security parameter using the parameters suggested by Garg, Gentry and Halevi [‘Candidate multilinear maps from ideal lattices’, Advances in cryptology — EUROCRYPT 2013 (Springer, 2013) 1–17].