**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

[ Cryptology ePrint archive ]