{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:19:32Z","timestamp":1761581972040,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T00:00:00Z","timestamp":1591142400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T00:00:00Z","timestamp":1591142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"JST CREST","award":["JPMJCR14D6"],"award-info":[{"award-number":["JPMJCR14D6"]}]},{"name":"JSPS KAKENHI","award":["JP16H02830."],"award-info":[{"award-number":["JP16H02830."]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s10623-020-00765-4","type":"journal-article","created":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T19:03:43Z","timestamp":1591211023000},"page":"2077-2100","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Analysis of DeepBKZ reduction for finding short lattice vectors"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1534-5648","authenticated-orcid":false,"given":"Masaya","family":"Yasuda","sequence":"first","affiliation":[]},{"given":"Satoshi","family":"Nakamura","sequence":"additional","affiliation":[]},{"given":"Junpei","family":"Yamaguchi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,3]]},"reference":[{"key":"765_CR1","doi-asserted-by":"crossref","unstructured":"Albrecht, M., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Advances in Cryptology\u2014EUROCRYPT 2019. Lecture Notes in Computer Science, vol. 11477, pp. 717\u2013746. Springer, Berline (2019)","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"765_CR2","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Curtis, B.R., Deo, A., Davidson, A., Player, R., Postlethwaite, E.W., Virdia, F., Wunderer, T.: Estimate all the LWE, NTRU schemes! In: Security and Cryptography for Networks (SCN 2018). Lecture Notes in Computer Science, vol. 11035, pp. 351\u2013367 (2018)","DOI":"10.1007\/978-3-319-98113-0_19"},{"key":"765_CR3","doi-asserted-by":"crossref","unstructured":"Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Advances in Cryptology\u2014EUROCRYPT 2016. Lecture Notes in Computer Science, vol. 9665, pp. 789\u2013819. Springer, New York (2016). Progressive BKZ library is available from https:\/\/www2.nict.go.jp\/security\/pbkzcode\/.","DOI":"10.1007\/978-3-662-49890-3_30"},{"key":"765_CR4","doi-asserted-by":"publisher","DOI":"10.1201\/b11066","volume-title":"Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications","author":"MR Bremner","year":"2011","unstructured":"Bremner M.R.: Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications. CRC Press, Boca Raton (2011)."},{"key":"765_CR5","unstructured":"Chen, Y.: R\u00e9duction de r\u00e9seau et s\u00e9curit\u00e9 concrete du chiffrement completement homomorphe. Ph.D. thesis, Paris 7 (2013)"},{"key":"765_CR6","doi-asserted-by":"crossref","unstructured":"Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Advances in Cryptology\u2014ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 1\u201320. Springer, New York (2011)","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"765_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A Course in Computational Algebraic Number Theory, Graduate Texts in Math","author":"H Cohen","year":"1993","unstructured":"Cohen H.: A Course in Computational Algebraic Number Theory, Graduate Texts in Math, vol. 138. Springer-Verlag, Berlin, Heidelberg (1993)."},{"key":"765_CR8","unstructured":"Ding, J., Kim, S., Takagi, T., Wang, Y.: LLL and stochastic sandpile models. arXiv:1804.03285v3 (2018)."},{"key":"765_CR9","doi-asserted-by":"crossref","unstructured":"Ducas, L.: Shortest vector from lattice sieving: a few dimensions for free. In: Advances in Cryptology\u2014EUROCRYPT 2018. Lecture Notes in Computer Science, vol. 10820, pp. 125\u2013145. Springer, New York (2018)","DOI":"10.1007\/978-3-319-78381-9_5"},{"issue":"2","key":"765_CR10","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10623-014-9918-8","volume":"73","author":"F Fontein","year":"2014","unstructured":"Fontein F., Schneider M., Wagner U.: PotLLL: a polynomial time version of LLL with deep insertions. Designs Codes Cryptogr. 73(2), 355\u2013368 (2014).","journal-title":"Designs Codes Cryptogr."},{"key":"765_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139012843","volume-title":"Mathematics of Public Key Cryptography","author":"SD Galbraith","year":"2012","unstructured":"Galbraith S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)."},{"key":"765_CR12","doi-asserted-by":"crossref","unstructured":"Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Advances in Cryptology\u2014EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 31\u201351. Springer, New York (2008)","DOI":"10.1007\/978-3-540-78967-3_3"},{"key":"765_CR13","doi-asserted-by":"crossref","unstructured":"Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Advances in Cryptology\u2014EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 257\u2013278. Springer, New York (2010)","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"765_CR14","doi-asserted-by":"crossref","unstructured":"Hanrot, G., Pujol, X., Stehl\u00e9, D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Advances in Cryptology\u2014CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 447\u2013464. Springer, New York (2011)","DOI":"10.1007\/978-3-642-22792-9_25"},{"issue":"4","key":"765_CR15","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra A.K., Lenstra H.W., Lov\u00e1sz L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982).","journal-title":"Math. Ann."},{"key":"765_CR16","unstructured":"Li, J.: On the smallest ratio problem of lattice bases. IACR ePrint 2016\/847 (2016)"},{"key":"765_CR17","unstructured":"Martinet, J.: Perfect lattices in Euclidean spaces. Comprehensive Studies in Mathematics, vol. 327. Springer Science & Business Media, New York (2013)"},{"key":"765_CR18","volume-title":"Complexity of Lattice Problems: A Cryptographic Perspective","author":"D Micciancio","year":"2012","unstructured":"Micciancio D., Goldwasser S.: Complexity of Lattice Problems: A Cryptographic Perspective, vol. 671. Springer Science & Business Media, Berlin (2012)."},{"key":"765_CR19","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: Advances in Cryptology\u2014EUROCRYPT 2016. Lecture Notes in Computer Science, vol. 9665, pp. 820\u2013849. Springer, New York (2016)","DOI":"10.1007\/978-3-662-49890-3_31"},{"key":"765_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-88330-9","volume-title":"Symmetric Bilinear Forms","author":"JW Milnor","year":"1973","unstructured":"Milnor J.W., Husemoller D.: Symmetric Bilinear Forms, vol. 60. Springer, New York (1973)."},{"key":"765_CR21","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q.: Hermite\u2019s constant and lattice algorithms. In: The LLL Algorithm, pp. 19\u201369. Springer, New York (2009)","DOI":"10.1007\/978-3-642-02295-1_2"},{"issue":"1","key":"765_CR22","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0747-7171(87)80061-5","volume":"4","author":"M Pohst","year":"1987","unstructured":"Pohst M.: A modification of the LLL reduction algorithm. J. Symbol. Comput. 4(1), 123\u2013127 (1987).","journal-title":"J. Symbol. Comput."},{"issue":"2\u20133","key":"765_CR23","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"CP Schnorr","year":"1987","unstructured":"Schnorr C.P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret Comput. Sci. 53(2\u20133), 201\u2013224 (1987).","journal-title":"Theoret Comput. Sci."},{"key":"765_CR24","unstructured":"Schnorr, C.P.: Block Korkin\u2013Zolotarev bases and successive minima. International Computer Science Institute (1992)"},{"key":"765_CR25","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Symposium on Theoretical Aspects of Computer Science\u2013STACS 2003. Lecture Notes in Computer Science, vol. 2607, pp. 145\u2013156. Springer, New York (2003)","DOI":"10.1007\/3-540-36494-3_14"},{"key":"765_CR26","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"CP Schnorr","year":"1994","unstructured":"Schnorr C.P., Euchner M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181\u2013199 (1994).","journal-title":"Math. Program."},{"key":"765_CR27","unstructured":"Shoup, V.: NTL: A Library for Doing Number Theory. http:\/\/www.shoup.net\/ntl\/."},{"key":"765_CR28","unstructured":"The FPLLL development team: FPLLL, a lattice reduction library (2016). https:\/\/github.com\/fplll\/fplll"},{"key":"765_CR29","unstructured":"TU Darmstadt: SVP challenge. https:\/\/www.latticechallenge.org\/svp-challenge\/."},{"key":"765_CR30","doi-asserted-by":"crossref","unstructured":"Yamaguchi, J., Yasuda, M.: Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications. In: International Conference on Number-Theoretic Methods in Cryptology\u2014NuTMiC 2017. Lecture Notes in Computer Science, vol. 10737, pp. 142\u2013160. Springer, Berlin (2017)","DOI":"10.1007\/978-3-319-76620-1_9"},{"key":"765_CR31","unstructured":"Yasuda, M.: Self-dual DeepBKZ for finding short lattice vectors. To appear in a MathCrypt special issue of J. Math. Cryptol."},{"key":"765_CR32","doi-asserted-by":"publisher","first-page":"2489","DOI":"10.1007\/s10623-019-00634-9","volume":"87","author":"M Yasuda","year":"2019","unstructured":"Yasuda M., Yamaguchi J.: A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths. Designs Codes Cryptogr. 87, 2489\u20132505 (2019).","journal-title":"Designs Codes Cryptogr."},{"key":"765_CR33","doi-asserted-by":"crossref","unstructured":"Yasuda, M., Yamaguchi, J., Ooka, M., Nakamura, S.: Development of a dual version of DeepBKZ and its application to solving the LWE challenge. In: Progress in Cryptology\u2014AFRICACRYPT 2018. Lecture Notes in Computer Science, vol. 10831, pp. 162\u2013182. Springer, New York (2018)","DOI":"10.1007\/978-3-319-89339-6_10"},{"issue":"1","key":"765_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/jmc-2016-0008","volume":"11","author":"M Yasuda","year":"2017","unstructured":"Yasuda M., Yokoyama K., Shimoyama T., Kogure J., Koshiba T.: Analysis of decreasing squared-sum of Gram\u2013Schmidt lengths for short lattice vectors. J. Math. Cryptol. 11(1), 1\u201324 (2017).","journal-title":"J. Math. Cryptol."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-020-00765-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-020-00765-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-020-00765-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,3]],"date-time":"2021-06-03T01:29:12Z","timestamp":1622683752000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-020-00765-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,3]]},"references-count":34,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["765"],"URL":"https:\/\/doi.org\/10.1007\/s10623-020-00765-4","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2020,6,3]]},"assertion":[{"value":"21 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}