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 HuJia attack using lowlevel encodings of zero, but no polynomialtime attack was known without them. In the GGH scheme without lowlevel encodings of zero, our algorithm can be directly applied to attack this scheme if we have some toplevel encodings of zero and a known pair of plaintext and ciphertext. Using our algorithm, we can construct a level0 encoding of zero and utilize it to attack a security ground of this scheme in the quasipolynomial time of its security parameter using the parameters suggested by {GGH13}.
Metadata
 Available format(s)
 Publication info
 Preprint. Minor revision.
 Keywords
 NTRUGGH Multilinear MapsIdeal LatticeShortest Vector Problem
 Contact author(s)
 cocomi11 @ snu ac kr
 History
 20160609: last of 6 revisions
 20160216: received
 See all versions
 Short URL
 https://ia.cr/2016/139
 License

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