Paper 2016/139

An Algorithm for NTRU Problems and Cryptanalysis of the GGH Multilinear Map without a Low Level Encoding of Zero

Jung Hee Cheon, Jinhyuck Jeong, and Changmin Lee

Abstract

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\in \Z_q[X]/< X^n+1>, the NTRU problem is to find a, b\in \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 2^{O(\log^{2} \lambda)} time when ||g||, ||f||, and || g^{-1}|| are within some range. The main technique of our algorithm is the reduction of a problem on a field to one in a subfield. Recently, the GGH scheme, the first candidate of a (approximate) multilinear map, was 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 {GGH13}.