{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T18:00:42Z","timestamp":1773424842196,"version":"3.50.1"},"reference-count":21,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"unspecified","delay-in-days":238,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2016]]},"abstract":"Let$\\mathbf{f}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and$\\mathbf{g}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>be polynomials of a bounded Euclidean norm in the ring$\\mathbb{Z}[X]\/\\langle X^{n}+1\\rangle$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Given the polynomial$[\\mathbf{f}\/\\mathbf{g}]_{q}\\in \\mathbb{Z}_{q}[X]\/\\langle X^{n}+1\\rangle$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the NTRU problem is to find$\\mathbf{a},\\mathbf{b}\\in \\mathbb{Z}[X]\/\\langle X^{n}+1\\rangle$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>with a small Euclidean norm such that$[\\mathbf{a}\/\\mathbf{b}]_{q}=[\\mathbf{f}\/\\mathbf{g}]_{q}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We propose an algorithm to solve the NTRU problem, which runs in$2^{O(\\log ^{2}\\unicode[STIX]{x1D706})}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>time when$\\Vert \\mathbf{g}\\Vert ,\\Vert \\mathbf{f}\\Vert$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and$\\Vert \\mathbf{g}^{-1}\\Vert$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>are within some range. The main technique of our algorithm is the reduction of a problem on a field to one on a subfield. The GGH scheme, the first candidate of an (approximate) multilinear map, was recently found to be insecure by the Hu\u2013Jia 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$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>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\u00a0Garg, Gentry and Halevi\u00a0[\u2018Candidate multilinear maps from ideal lattices\u2019,Advances in cryptology \u2014 EUROCRYPT 2013<\/jats:italic>(Springer, 2013) 1\u201317].<\/jats:p>","DOI":"10.1112\/s1461157016000371","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T15:31:14Z","timestamp":1472225474000},"page":"255-266","source":"Crossref","is-referenced-by-count":78,"title":["An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero"],"prefix":"10.1112","volume":"19","author":[{"given":"Jung Hee","family":"Cheon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinhyuck","family":"Jeong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Changmin","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"S1461157016000371_r6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-662-46800-5_1","volume-title":"Advances in cryptology \u2014 EUROCRYPT 2015","author":"Cheon","year":"2015"},{"key":"S1461157016000371_r4","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/324\/05731"},{"key":"S1461157016000371_r14","volume-title":"Advances in cryptology \u2014 EUROCRYPT 2002","author":"Gentry","year":"2002"},{"key":"S1461157016000371_r18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49890-3_21"},{"key":"S1461157016000371_r10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_13"},{"key":"S1461157016000371_r9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_26"},{"key":"S1461157016000371_r21","first-page":"491","volume-title":"Advances in cryptology \u2014 CRYPTO 2016","author":"Miles","year":"2016"},{"key":"S1461157016000371_r17","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054868"},{"key":"S1461157016000371_r12","first-page":"1","volume-title":"Advances in cryptology \u2013 EUROCRYPT 2013","author":"Garg","year":"2013"},{"key":"S1461157016000371_r19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_14"},{"key":"S1461157016000371_r20","doi-asserted-by":"crossref","first-page":"1219","DOI":"10.1145\/2213977.2214086","volume-title":"Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing 2012","author":"L\u00f3pez-Alt","year":"2012"},{"key":"S1461157016000371_r5","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-642-45239-0_4","volume-title":"Cryptography and coding 2013","author":"Bos","year":"2013"},{"key":"S1461157016000371_r1","doi-asserted-by":"crossref","unstructured":"1. D. Aggarwal , D. Dadush , O. Regev and N. Stephens-Davidowitz , \u2018Solving the shortest vector problem in $2^{n}$ time via discrete Gaussian sampling\u2019, Preprint, 2014, arXiv:1412.7994.","DOI":"10.1145\/2746539.2746606"},{"key":"S1461157016000371_r2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53018-4_6"},{"key":"S1461157016000371_r8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_21"},{"key":"S1461157016000371_r15","unstructured":"15. G. Hanrot , X. Pujol and D. Stehl\u00e9 , \u2018Terminating BKZ\u2019, IACR Cryptology ePrint Archive 2011, https:\/\/eprint.iacr.org\/2011\/198."},{"key":"S1461157016000371_r7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49890-3_20"},{"key":"S1461157016000371_r11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_3"},{"key":"S1461157016000371_r13","first-page":"498","volume-title":"Theory of cryptography 2015","author":"Garg","year":"2015"},{"key":"S1461157016000371_r16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36563-X_9"},{"key":"S1461157016000371_r3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48800-3_31"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157016000371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T04:03:40Z","timestamp":1657166620000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157016000371\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":21,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2016]]}},"alternative-id":["S1461157016000371"],"URL":"https:\/\/doi.org\/10.1112\/s1461157016000371","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}