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}.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
NTRUGGH Multilinear MapsIdeal LatticeShortest Vector Problem
Contact author(s)
cocomi11 @ snu ac kr
History
2016-06-09: last of 6 revisions
See all versions
Short URL
https://ia.cr/2016/139

CC BY

BibTeX

@misc{cryptoeprint:2016/139,
author = {Jung Hee Cheon and Jinhyuck Jeong and Changmin Lee},
title = {An Algorithm for NTRU Problems and Cryptanalysis of the GGH Multilinear Map without a Low Level Encoding of Zero},
howpublished = {Cryptology ePrint Archive, Paper 2016/139},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/139}},
url = {https://eprint.iacr.org/2016/139}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.