{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T05:01:43Z","timestamp":1764997303774,"version":"3.46.0"},"reference-count":23,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Overstretched NTRU is a variant of NTRU with a large modulus. Recent lattice subfield and subring attacks have broken suggested parameters for several schemes. There are a number of conflicting claims in the literature over which attack has the best performance. These claims are typically based on experiments more than analysis. In this paper, we argue that comparisons should focus on the lattice dimension used in the attack. We give evidence, both analytically and experimentally, that the subring attack finds shorter vectors and thus is expected to succeed with a smaller dimension lattice than the subfield attack for the same problem parameters, and also to succeed with a smaller modulus when the lattice dimension is fixed.<\/jats:p>","DOI":"10.1515\/jmc-2015-0055","type":"journal-article","created":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T13:48:20Z","timestamp":1592228900000},"page":"110-119","source":"Crossref","is-referenced-by-count":3,"title":["Characterizing overstretched NTRU attacks"],"prefix":"10.1515","volume":"14","author":[{"given":"Gabrielle","family":"De Micheli","sequence":"first","affiliation":[{"name":"University of Pennsylvania , Pennsylvania , United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Heninger","sequence":"additional","affiliation":[{"name":"University of Pennsylvania , Pennsylvania , United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barak","family":"Shani","sequence":"additional","affiliation":[{"name":"University of Pennsylvania , Pennsylvania , United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"key":"2025120600161810667_j_jmc-2015-0055_ref_001_w2aab3b7e2182b1b6b1ab2b1b1Aa","doi-asserted-by":"crossref","unstructured":"M. Albrecht, S. Bai, and L. Ducas. A Subfield Lattice Attack on Overstretched NTRU Assumptions. CRYPTO 2016.","DOI":"10.1007\/978-3-662-53018-4_6"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_002_w2aab3b7e2182b1b6b1ab2b1b2Aa","doi-asserted-by":"crossref","unstructured":"W.D. Banks and I.E. Shparlinski. Distribution of Inverses in Polynomial Rings. Indagationes Mathematicae, 12(3), 2001.","DOI":"10.1016\/S0019-3577(01)80012-4"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_003_w2aab3b7e2182b1b6b1ab2b1b3Aa","doi-asserted-by":"crossref","unstructured":"D. Boneh and R. Venkatesan. Hardness of Computing the Most Significant Bits of Secret Keys in Diffie\u2013Hellman and Related Schemes. CRYPTO 1996.","DOI":"10.1007\/3-540-68697-5_11"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_004_w2aab3b7e2182b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"J. H. Cheon, J. Jeong, and C. Lee. An Algorithm for NTRU Problems and Cryptanalysis of the GGH Multilinear Map without a Low-Level Encoding of Zero. LMS Journal of Computation and Mathematics, 19(A): 2016.","DOI":"10.1112\/S1461157016000371"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_005_w2aab3b7e2182b1b6b1ab2b1b5Aa","unstructured":"D. Coppersmith and A. Shamir. Lattice Attacks on NTRU. Eurocrypt \u201997."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_006_w2aab3b7e2182b1b6b1ab2b1b6Aa","unstructured":"G. De Micheli, N. Heninger, and B. Shani. Characterizing overstretched NTRU attacks. ePrint 2018\/630"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_007_w2aab3b7e2182b1b6b1ab2b1b7Aa","unstructured":"M. Drmota and R. Tichy. Discrepancies and Applications."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_008_w2aab3b7e2182b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"D. H. Duong, M. Yasuda, and T. Takagi. Choosing Parameters for the Subfield Lattice Attack Against Overstretched NTRU. Information Security 2017.","DOI":"10.1007\/978-3-319-69659-1_5"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_009_w2aab3b7e2182b1b6b1ab2b1b9Aa","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, and S. Halevi. Candidate Multilinear Maps from Ideal Lattices. EUROCRYPT 2013.","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_010_w2aab3b7e2182b1b6b1ab2b1c10Aa","doi-asserted-by":"crossref","unstructured":"J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. NTRUSign: Digital Signatures Using the NTRU Lattice. CT-RSA 2003.","DOI":"10.1007\/3-540-36563-X_9"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_011_w2aab3b7e2182b1b6b1ab2b1c11Aa","doi-asserted-by":"crossref","unstructured":"J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: A Ring-based Public Key Cryptosystem. Algorithmic Number Theory 1998.","DOI":"10.1007\/BFb0054868"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_012_w2aab3b7e2182b1b6b1ab2b1c12Aa","doi-asserted-by":"crossref","unstructured":"P. Kirchner and P.-A. Fouque. Revisiting Lattice Attacks on Overstretched NTRU Parameters. EUROCRYPT 2017.","DOI":"10.1007\/978-3-319-56620-7_1"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_013_w2aab3b7e2182b1b6b1ab2b1c13Aa","unstructured":"R. Kuipers and H. Niederreiter. Uniform Distribution of Sequences."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_014_w2aab3b7e2182b1b6b1ab2b1c14Aa","unstructured":"A. L\u00f3pez-Alt, E. Tromer, and V. Vaikuntanathan. On-the-fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. STOC \u201912."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_015_w2aab3b7e2182b1b6b1ab2b1c15Aa","unstructured":"G. F. Lawler and V. Limic. Random Walk: A Modern Introduction."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_016_w2aab3b7e2182b1b6b1ab2b1c16Aa","doi-asserted-by":"crossref","unstructured":"R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511525926"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_017_w2aab3b7e2182b1b6b1ab2b1c17Aa","unstructured":"A. May. Cryptanalysis of NTRU, 1999."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_018_w2aab3b7e2182b1b6b1ab2b1c18Aa","unstructured":"A. May and J. H. Silverman. Dimension Reduction Methods for Convolution Modular Lattices. Cryptography and Lattices."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_019_w2aab3b7e2182b1b6b1ab2b1c19Aa","unstructured":"G. Pataki and M. Tural. On Sublattice Determinants in Reduced Bases, 2008."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_020_w2aab3b7e2182b1b6b1ab2b1c20Aa","unstructured":"P. Samuel. Algebraic Theory of Numbers. Hermann, 1970."},{"key":"2025120600161810667_j_jmc-2015-0055_ref_021_w2aab3b7e2182b1b6b1ab2b1c21Aa","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr. A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms. Theor. Comput. Sci., 53(2-3):201\u2013224, August 1987.","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_022_w2aab3b7e2182b1b6b1ab2b1c22Aa","doi-asserted-by":"crossref","unstructured":"D. Stehl\u00e9 and R. Steinfeld. Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. EUROCRYPT 2011.","DOI":"10.1007\/978-3-642-20465-4_4"},{"key":"2025120600161810667_j_jmc-2015-0055_ref_023_w2aab3b7e2182b1b6b1ab2b1c23Aa","doi-asserted-by":"crossref","unstructured":"R. Steinfeld. NTRU Cryptosystem: Recent Developments and Emerging Mathematical Problems in Finite Polynomial Rings. Walter de Gruyter, 2014.","DOI":"10.1515\/9783110317916.179"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/14\/1\/article-p110.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0055\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0055\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:16:38Z","timestamp":1764980198000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0055\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":23,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,6,14]]},"published-print":{"date-parts":[[2020,6,14]]}},"alternative-id":["10.1515\/jmc-2015-0055"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2015-0055","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}