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

作者：Cheon Jung Hee^*; Jeong Jinhyuck; Lee Changmin

来源：LMS Journal of Computation and Mathematics, 2016, 19(A): 255-266.

DOI：10.1112/S1461157016000371

Let f and g be polynomials of a bounded Euclidean norm in the ring {Z}[X]/< X-n+1 >. Given the polynomial [f/g](q) is an element of Z(q) [X]/< X-n + 1 >, the NTRU problem is to find a,b is an element of Z[X]/< X-n + 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 2O(log2 lambda) time when parallel to g parallel to, parallel to f parallel to, and parallel to g(-1)parallel to 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 HuJia 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].

• 出版日期2016-1