{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T19:44:51Z","timestamp":1778528691878,"version":"3.51.4"},"reference-count":18,"publisher":"Walter de Gruyter GmbH","issue":"1","funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["16H02830"],"award-info":[{"award-number":["16H02830"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In 2015,\nFukase and Kashiwabara proposed an efficient method to find a very short lattice vector.\nTheir method has been applied to solve Darmstadt shortest vector problems of dimensions 134 to 150.\nTheir method is based on Schnorr\u2019s random sampling, but their preprocessing is different from others.\nIt aims to decrease the sum of the squared lengths of the Gram\u2013Schmidt vectors of a lattice basis, before executing random sampling of short lattice vectors.\nThe effect is substantiated from their statistical analysis, and it implies that the smaller the sum becomes, the shorter sampled vectors can be. However, no guarantee is known to strictly decrease the sum.\nIn this paper, we study Fukase\u2013Kashiwabara\u2019s method in both theory and practice, and give a heuristic but practical condition that the sum is strictly decreased.\nWe believe that our condition would enable one to monotonically decrease the sum\nand to find a very short lattice vector in fewer steps.<\/jats:p>","DOI":"10.1515\/jmc-2016-0008","type":"journal-article","created":{"date-parts":[[2017,2,17]],"date-time":"2017-02-17T05:00:41Z","timestamp":1487307641000},"page":"1-24","source":"Crossref","is-referenced-by-count":8,"title":["Analysis of decreasing squared-sum of Gram\u2013Schmidt lengths for short lattice vectors"],"prefix":"10.1515","volume":"11","author":[{"given":"Masaya","family":"Yasuda","sequence":"first","affiliation":[{"name":"Institute of Mathematics for Industry, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhiro","family":"Yokoyama","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Rikkyo University, Nishi-Ikebukuro, Tokyo 171-850, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Shimoyama","sequence":"additional","affiliation":[{"name":"Fujitsu Laboratories Ltd., 1-1, Kamikodanaka 4-chome, Nakahara-ku, Kawasaki, Kanagawa 211-8588, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Kogure","sequence":"additional","affiliation":[{"name":"Fujitsu Laboratories Ltd., 1-1, Kamikodanaka 4-chome, Nakahara-ku, Kawasaki, Kanagawa 211-8588, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Koshiba","sequence":"additional","affiliation":[{"name":"Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University, 255 Shimo-Okubo, Sakura, Saitama 338-8570, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2017,2,17]]},"reference":[{"key":"2025120600295340297_j_jmc-2016-0008_ref_001_w2aab3b7d566b1b6b1ab2b1b1Aa","doi-asserted-by":"crossref","unstructured":"Ajtai M.,\nThe shortest vector problem in L2${L_{2}}$ is NP-hard for randomized reductions,\nProceedings of the 30th Annual ACM Symposium on Theory of Computing \u2013 STOC 1998,\nACM, New York (1998), 10\u201319.","DOI":"10.1145\/276698.276705"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_002_w2aab3b7d566b1b6b1ab2b1b2Aa","doi-asserted-by":"crossref","unstructured":"Ajtai M., Kumar R. and Sivakumar D.,\nA sieve algorithm for the shortest lattice vector problem,\nProceedings of the 33rd Annual ACM Symposium on Theory of Computing \u2013 STOC 2001,\nACM, New York (2001), 601\u2013610.","DOI":"10.1145\/380752.380857"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_003_w2aab3b7d566b1b6b1ab2b1b3Aa","unstructured":"Bremner M. R.,\nLattice Basis Reduction: An Introduction to the LLL Algorithm and its Applications,\nCRC Press, Boca Raton, 2011."},{"key":"2025120600295340297_j_jmc-2016-0008_ref_004_w2aab3b7d566b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"Buchmann J. and Ludwig C.,\nPractical lattice basis sampling reduction,\nAlgorithmic Number Theory \u2013 ANTS 2006,\nLecture Notes in Comput. Sci. 4076,\nSpringer, Berlin (2006), 222\u2013237.","DOI":"10.1007\/11792086_17"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_005_w2aab3b7d566b1b6b1ab2b1b5Aa","doi-asserted-by":"crossref","unstructured":"Fukase M. and Kashiwabara K.,\nAn accelerated algorithm for solving SVP based on statistical analysis,\nJ. Inform. Process. 23 (2015), no. 1, 1\u201315.","DOI":"10.2197\/ipsjjip.23.67"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_006_w2aab3b7d566b1b6b1ab2b1b6Aa","doi-asserted-by":"crossref","unstructured":"Galbraith S. D.,\nMathematics of Public Key Cryptography,\nCambridge University Press, Cambridge, 2012.","DOI":"10.1017\/CBO9781139012843"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_007_w2aab3b7d566b1b6b1ab2b1b7Aa","doi-asserted-by":"crossref","unstructured":"Gama N. and Nguyen P. Q.,\nPredicting lattice reduction,\nAdvances in Cryptology \u2013 EUROCRYPT 2008,\nLecture Notes in Computer Sci. 4965,\nSpringer, Berlin (2008), 31\u201351.","DOI":"10.1007\/978-3-540-78967-3_3"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_008_w2aab3b7d566b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"Gama N., Nguyen P. Q. and Regev O.,\nLattice enumeration using extreme pruning,\nAdvances in Cryptology \u2013 EUROCRYPT 2010,\nLecture Notes in Computer Sci. 6110,\nSpringer, Berlin (2010), 257\u2013278.","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_009_w2aab3b7d566b1b6b1ab2b1b9Aa","doi-asserted-by":"crossref","unstructured":"Goldreich O., Goldwasser S. and Halevi S.,\nPublic-key cryptosystems from lattice reduction problems,\nAdvances in Cryptology \u2013 CRYPTO 1997,\nLecture Notes in Computer Sci. 1294,\nSpringer, Berlin (1997), 112\u2013131.","DOI":"10.1007\/BFb0052231"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_010_w2aab3b7d566b1b6b1ab2b1c10Aa","doi-asserted-by":"crossref","unstructured":"Hoffstein J., Pipher J. and Silverman J. H.,\nNTRU: A ring-based public key cryptosystem,\nAlgorithmic Number Theory \u2013 ANTS III,\nLecture Notes in Computer Sci. 1423,\nSpringer, Berlin (1998), 267\u2013288.","DOI":"10.1007\/BFb0054868"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_011_w2aab3b7d566b1b6b1ab2b1c11Aa","doi-asserted-by":"crossref","unstructured":"Lenstra A. K., Lenstra H. W. and Lov\u00e1sz L.,\nFactoring polynomials with rational coefficients,\nMath. Ann. 261 (1982), no. 4, 515\u2013534.","DOI":"10.1007\/BF01457454"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_012_w2aab3b7d566b1b6b1ab2b1c12Aa","unstructured":"Ludwig C.,\nPractical lattice basis sampling reduction,\nPh.D thesis, Technische Universit\u00e4t Darmstadt, 2005."},{"key":"2025120600295340297_j_jmc-2016-0008_ref_013_w2aab3b7d566b1b6b1ab2b1c13Aa","doi-asserted-by":"crossref","unstructured":"Micciancio D.,\nThe shortest vector in a lattice is hard to approximate to within some constant,\nSIAM J. Comput. 30 (2001), no. 6, 2008\u20132035.","DOI":"10.1137\/S0097539700373039"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_014_w2aab3b7d566b1b6b1ab2b1c14Aa","doi-asserted-by":"crossref","unstructured":"Micciancio D. and Michael W.,\nFast lattice point enumeration with minimal overhead,\nProceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms \u2013 SODA 2015,\nSIAM, Philadelphia (2015), 276\u2013294.","DOI":"10.1137\/1.9781611973730.21"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_015_w2aab3b7d566b1b6b1ab2b1c15Aa","doi-asserted-by":"crossref","unstructured":"Nguyen P. Q. and Vall\u00e9e B.,\nThe LLL algorithm,\nInf. Secur. Cryptography,\nSpringer, Berlin, 2010.","DOI":"10.1007\/978-3-642-02295-1"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_016_w2aab3b7d566b1b6b1ab2b1c16Aa","doi-asserted-by":"crossref","unstructured":"Schneider M. and G\u00f6ttert N.,\nRandom sampling for short lattice vectors on graphics cards,\nCryptographic Hardware and Embedded Systems \u2013 CHES 2011,\nLecture Notes in Computer Sci. 6917,\nSpringer, Berlin (2011), 160\u2013175.","DOI":"10.1007\/978-3-642-23951-9_11"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_017_w2aab3b7d566b1b6b1ab2b1c17Aa","doi-asserted-by":"crossref","unstructured":"Schnorr C. P.,\nLattice reduction by random sampling and birthday methods,\n20th Annual Symposium of Theoretical Aspects on Computer Science \u2013 STACS 2003,\nLecture Notes in Computer Sci. 2606,\nSpringer, Berlin (2003), 145\u2013156.","DOI":"10.1007\/3-540-36494-3_14"},{"key":"2025120600295340297_j_jmc-2016-0008_ref_018_w2aab3b7d566b1b6b1ab2b1c18Aa","doi-asserted-by":"crossref","unstructured":"Schnorr C. P. and Euchner M.,\nLattice basis reduction: Improved practical algorithms and solving subset sum problems,\nMath. Program. 66 (1994), 181\u2013199.","DOI":"10.1007\/BF01581144"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/11\/1\/article-p1.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0008\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0008\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:30:23Z","timestamp":1764981023000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0008\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,17]]},"references-count":18,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,3,1]]},"published-print":{"date-parts":[[2017,3,1]]}},"alternative-id":["10.1515\/jmc-2016-0008"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2016-0008","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"value":"1862-2984","type":"electronic"},{"value":"1862-2976","type":"print"}],"subject":[],"published":{"date-parts":[[2017,2,17]]}}}