Cryptology ePrint Archive: Report 2016/139

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

Jung Hee Cheon and 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}.

Category / Keywords: NTRU, GGH Multilinear Maps, Ideal Lattice, Shortest Vector Problem

Date: received 15 Feb 2016, last revised 8 Jun 2016

Contact author: cocomi11 at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20160609:024126 (All versions of this report)

Short URL: ia.cr/2016/139

Discussion forum: Show discussion | Start new discussion