{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T22:54:11Z","timestamp":1793314451091,"version":"4.5.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,1,20]],"date-time":"2017-01-20T00:00:00Z","timestamp":1484870400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Deutschen Forschungsgemeinschaft (DFG)","award":["GRK 1817 Ubicrypt"],"award-info":[{"award-number":["GRK 1817 Ubicrypt"]}]},{"name":"Deutschen Forschungsgemeinschaft (DFG)","award":["UbiCrypt (GRK 1817\/1)"],"award-info":[{"award-number":["UbiCrypt (GRK 1817\/1)"]}]},{"name":"FSC: Fast and Sound Cryptography","award":["ERC Starting Grant 307952"],"award-info":[{"award-number":["ERC Starting Grant 307952"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s10623-016-0326-0","type":"journal-article","created":{"date-parts":[[2017,1,20]],"date-time":"2017-01-20T05:55:14Z","timestamp":1484891714000},"page":"55-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["On the asymptotic complexity of solving LWE"],"prefix":"10.1007","volume":"86","author":[{"given":"Gottfried","family":"Herold","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8924-7605","authenticated-orcid":false,"given":"Elena","family":"Kirshanova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"May","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,1,20]]},"reference":[{"key":"326_CR1","unstructured":"Aggarwal D., Dadush D., Regev O., Stephens-Davidowitz N.: Solving the shortest vector problem in $$2^{{\\rm n}}$$ 2 n time via discrete gaussian sampling. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC \u201915), pp. 733\u2013742. ACM, New York (2015)."},{"key":"326_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai M., Kumar R., Sivakumar D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of STOC, pp. 601\u2013610 (2001).","DOI":"10.1145\/380752.380857"},{"key":"326_CR3","unstructured":"Albrecht M., Faug\u00e9re J.-C., Fitzpatrick R., Perret L.: Lazy Modulus Switching for the BKW Algorithm on LWE. Lecture Notes in Computer Science, vol. 8383, pp. 429\u2013445. Springer, Berlin (2014)."},{"key":"326_CR4","doi-asserted-by":"crossref","unstructured":"Albrecht M.R., Player R., Scott S.: On the concrete hardness of learning with errors. Cryptology ePrint Archive, Report 2015\/046 (2015).","DOI":"10.1515\/jmc-2015-0016"},{"issue":"2","key":"326_CR5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","volume":"74","author":"M Albrecht","year":"2013","unstructured":"Albrecht M., Cid C., Faug\u00e9re J.C., Fitzpatrick R., Perret L.: On the complexity of the bkw algorithm on lwe. Des. Codes Cryptogr. 74(2), 325\u2013354 (2013).","journal-title":"Des. Codes Cryptogr."},{"key":"326_CR6","unstructured":"Alkim E., Ducas L., P\u00f6ppelmann T., Schwabe P.: Post-quantum key exchange \u2014a new hope. In: Proceedings of the 25th USENIX Security Symposium. USENIX Association (2016)."},{"key":"326_CR7","doi-asserted-by":"crossref","unstructured":"Aono Y., Boyen X., Phong L., Wang L.: Key-private proxy re-encryption under LWE. In: INDOCRYPT 2013, pp. 1\u201318 (2013).","DOI":"10.1007\/978-3-319-03515-4_1"},{"key":"326_CR8","doi-asserted-by":"crossref","unstructured":"Applebaum B., Cash D., Peikert C., Sahai A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Advances in Cryptology\u2014CRYPTO 2009. Lecture Notes in Computer Science, vol. 5677, pp. 595\u2013618. Springer, Berlin (2009).","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"326_CR9","doi-asserted-by":"crossref","unstructured":"Arora S., Ge R.: New algorithms for learning in presence of errors. In: Proceedings of the 38th International Colloquim Conference on Automata, Languages and Programming (ICALP\u201911), pp. 403\u2013415 (2011).","DOI":"10.1007\/978-3-642-22006-7_34"},{"key":"326_CR10","doi-asserted-by":"crossref","unstructured":"Babai L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem (shortened version). In: STACS, pp. 13\u201320 (1985).","DOI":"10.1007\/BFb0023990"},{"issue":"1","key":"326_CR11","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1007\/BF01445125","volume":"296","author":"W Banaszczyk","year":"1993","unstructured":"Banaszczyk W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(1), 625\u2013635 (1993).","journal-title":"Math. Ann."},{"key":"326_CR12","doi-asserted-by":"crossref","unstructured":"Becker A., Ducas L., Gama N., Laarhoven T.: New directions in nearest neighbor searching with applications to lattice sieving. In: SODA (2016).","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"326_CR13","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"Blum A., Kalai A.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50, 506\u2013519 (2003).","journal-title":"J. ACM"},{"key":"326_CR14","unstructured":"Bos J., Costello C., Ducas L., Mironov I., Naehrig M., Nikolaenko V., Raghunathan A., Stebila D.: Frodo: Take off the ring! practical, quantum secure key exchange from LWE. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS \u201916, pp. 1006\u20131018, (2016)."},{"key":"326_CR15","doi-asserted-by":"crossref","unstructured":"Brakerski Z., Langlois A., Peikert C., Regev O., Stehl\u00e9 D.: Classical hardness of learning with errors. In: Proceedings of STOC, pp. 575\u2013584 (2013).","DOI":"10.1145\/2488608.2488680"},{"key":"326_CR16","unstructured":"D\u00f6ttling N.: Low noise LPN: KDM secure public key encryption and sample amplification. In: Public-Key Cryptography\u2014PKC 2015\u2014Proceedings of the 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, 30 March\u20131 April 2015, pp. 604\u2013626 (2015)."},{"key":"326_CR17","doi-asserted-by":"crossref","unstructured":"Duc A., Tram\u00e9r F., Vaudenay S.: Better algorithms for LWE and LWR. In: EUROCRYPT (2015).","DOI":"10.1007\/978-3-662-46800-5_8"},{"key":"326_CR18","doi-asserted-by":"crossref","unstructured":"Fincke U., Pohst M.: A procedure for determining algebraic integers of given norm. In: Proceedings of EUROCAL. Lecture Notes in Computer Science, vol. 162, pp. 194\u2013202 (1983).","DOI":"10.1007\/3-540-12868-9_103"},{"key":"326_CR19","doi-asserted-by":"crossref","unstructured":"Gama N., Nguyen P.Q.: Predicting lattice reduction. In: EUROCRYPT, pp. 31\u201351 (2008).","DOI":"10.1007\/978-3-540-78967-3_3"},{"key":"326_CR20","doi-asserted-by":"crossref","unstructured":"Gama N., Nguyen P., Regev O.: Lattice enumeration using extreme pruning. In: EUROCRYPT 2010, LNCS, vol. 6110, pp. 257\u2013278. Springer, Berlin (2010).","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"326_CR21","doi-asserted-by":"crossref","unstructured":"Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC \u201908, pp. 197\u2013206 (2008).","DOI":"10.1145\/1374376.1374407"},{"issue":"3","key":"326_CR22","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1006\/jcss.1999.1686","volume":"60","author":"O Goldreich","year":"2000","unstructured":"Goldreich O., Goldwasser S.: On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. 60(3), 540\u2013563 (2000).","journal-title":"J. Comput. Syst. Sci."},{"key":"326_CR23","doi-asserted-by":"crossref","unstructured":"Goldreich O., Rubinfeld R., Sudan M.: Learning polynomials with queries: the highly noisy case. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS, pp. 294\u2013303 (1995).","DOI":"10.1109\/SFCS.1995.492485"},{"key":"326_CR24","doi-asserted-by":"crossref","unstructured":"Guo Q., Johansson T., Stankovski P.: Coded-BKW: solving LWE using lattice codes. In: Advances in Cryptology\u2014CRYPTO 2015. Lecture Notes in Computer Science, vol. 9215, pp. 23\u201342. Springer, Berlin (2015).","DOI":"10.1007\/978-3-662-47989-6_2"},{"key":"326_CR25","unstructured":"Hanrot G., Stehl\u00e9 D.: Improved analysis of kannans shortest lattice vector algorithm. In: Advances in Cryptology\u2014CRYPTO 2007, LNCS, vol. 4622, pp. 170\u2013186 (2007)."},{"key":"326_CR26","unstructured":"Hanrot G., Pujol X., Stehl\u00e9 D.: Analyzing Blockwise Lattice Algorithms Using Dynamical Systems, LNCS, vol. 6841, pp. 447\u2013464. Springer, Berlin (2011)."},{"key":"326_CR27","doi-asserted-by":"crossref","unstructured":"Kannan R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of STOC, pp. 193\u2013206 (1983).","DOI":"10.1145\/800061.808749"},{"key":"326_CR28","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12, 415\u2013440 (1987).","journal-title":"Math. Oper. Res."},{"key":"326_CR29","doi-asserted-by":"crossref","unstructured":"Kirchner P., Fouque P.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Advances in Cryptology\u2014CRYPTO 2015. Lecture Notes in Computer Science, vol. 9215, pp. 43\u201362. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-47989-6_3"},{"key":"326_CR30","unstructured":"Kirshanova E., May A., Wiemer F.: Parallel Implementation of BDD Enumeration for LWE, pp. 580\u2013591. Springer, Cham (2016)."},{"key":"326_CR31","unstructured":"Kleinjung T., Aoki K., Franke J., Lenstra A.K., Thom\u00e9 E., Bos J.W., Gaudry P., Kruppa A., Montgomery P.L., Osvik D.A., et\u00a0al. Factorization of a 768-bit rsa modulus. In: Advances in Cryptology\u2014CRYPTO 2010, pp. 333\u2013350. Springer, Berlin (2010)."},{"key":"326_CR32","doi-asserted-by":"crossref","unstructured":"Laarhoven T.: Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In: CRYPTO (2015).","DOI":"10.1007\/978-3-662-47989-6_1"},{"issue":"4","key":"326_CR33","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/s00145-001-0009-4","volume":"14","author":"AK Lenstra","year":"2001","unstructured":"Lenstra A.K., Verheul E.R.: Selecting cryptographic key sizes. J. Cryptol. 14(4), 255\u2013293 (2001).","journal-title":"J. Cryptol."},{"key":"326_CR34","unstructured":"Levieil \u00c9., Fouque P.-A.: An improved LPN algorithm. In: Security and Cryptography for Networks. Lecture Notes in Computer Science, vol. 4116, pp. 348\u2013359. Springer, Berlin (2006)."},{"key":"326_CR35","doi-asserted-by":"crossref","unstructured":"Lindner R., Peikert C.: Better key sizes (and attacks) for LWE-based encryption. In: CT-RSA\u201911, pp. 319\u2013339 (2011).","DOI":"10.1007\/978-3-642-19074-2_21"},{"key":"326_CR36","doi-asserted-by":"crossref","unstructured":"Liu M., Nguyen P.Q.: Solving BDD by enumeration: an update. In: CT-RSA, pp. 293\u2013309 (2013).","DOI":"10.1007\/978-3-642-36095-4_19"},{"key":"326_CR37","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: RANDOM. Lecture Notes in Computer Science, vol. 3624, pp. 378\u2013389. Springer, Berlin (2005).","DOI":"10.1007\/11538462_32"},{"key":"326_CR38","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V., Micciancio D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Advances in Cryptology\u2014CRYPTO 2009. Lecture Notes in Computer Science, vol. 5677, pp. 577\u2013594. Springer, Berlin (2009).","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"326_CR39","doi-asserted-by":"crossref","unstructured":"Micciancio D., Goldwasser S.: Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science. Kluwer Academic, Boston (2002).","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"326_CR40","doi-asserted-by":"crossref","unstructured":"Micciancio D., Regev O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 372\u2013381 (2004).","DOI":"10.1109\/FOCS.2004.72"},{"key":"326_CR41","volume-title":"Lattice-Based Cryptography","author":"D Micciancio","year":"2009","unstructured":"Micciancio D., Regev O.: Lattice-Based Cryptography. Springer, Berlin (2009)."},{"key":"326_CR42","doi-asserted-by":"crossref","unstructured":"Micciancio D., Voulgaris P.: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In: Proceedings of STOC \u201910, pp. 351\u2013358 (2010).","DOI":"10.1145\/1806689.1806739"},{"key":"326_CR43","doi-asserted-by":"crossref","unstructured":"Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of STOC, pp. 333\u2013342 (2009).","DOI":"10.1145\/1536414.1536461"},{"key":"326_CR44","unstructured":"Peikert C., Micciancio D.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: EUROCRYPT, pp. 700\u2013718 (2012)."},{"issue":"1","key":"326_CR45","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1112\/jlms\/s1-21.1.34","volume":"s1\u201321","author":"R Rado","year":"1946","unstructured":"Rado R.: A theorem on the geometry of numbers. J. Lond. Math. Soc. s1\u201321(1), 34\u201347 (1946).","journal-title":"J. Lond. Math. Soc."},{"key":"326_CR46","doi-asserted-by":"crossref","unstructured":"Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84\u201393. ACM Press, New York (2005).","DOI":"10.1145\/1060590.1060603"},{"key":"326_CR47","doi-asserted-by":"crossref","unstructured":"Schnorr C.-P.: Lattice reduction by random sampling and birthday methods. In: STACS, pp. 145\u2013156 (2003).","DOI":"10.1007\/3-540-36494-3_14"},{"key":"326_CR48","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"C-P Schnorr","year":"1993","unstructured":"Schnorr C.-P., Euchner M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181\u2013191 (1993).","journal-title":"Math. Program."},{"key":"326_CR49","unstructured":"Yearly report on algorithms and keysizes. D.SPA.20 Rev. 1.0, ICT-2007-216676 ECRYPT II (2012)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-016-0326-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-016-0326-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-016-0326-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T16:17:41Z","timestamp":1568737061000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-016-0326-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,20]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["326"],"URL":"https:\/\/doi.org\/10.1007\/s10623-016-0326-0","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,20]]}}}