{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T22:13:21Z","timestamp":1768947201333,"version":"3.49.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032018540","type":"print"},{"value":"9783032018557","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-032-01855-7_12","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T19:41:40Z","timestamp":1755373300000},"page":"353-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Wagner\u2019s Algorithm Provably Runs in\u00a0Subexponential Time for\u00a0$$\\textrm{SIS}^\\infty $$"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2510-4829","authenticated-orcid":false,"given":"L\u00e9o","family":"Ducas","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8069-5775","authenticated-orcid":false,"given":"Lynn","family":"Engelberts","sequence":"additional","affiliation":[]},{"given":"Johanna","family":"Loyer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"12_CR1","unstructured":"Aggarwal, D., Chen, Y., Kumar, R., Shen, Y.: Improved (provable) algorithms for the shortest vector problem via bounded distance decoding. In: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 of LIPIcs, pp. 4:1\u20134:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in $$2^n$$ time using discrete Gaussian sampling: extended abstract. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, pp. 733\u2013742. ACM (2015)","DOI":"10.1145\/2746539.2746606"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Stephens-Davidowitz, N.: Solving the closest vector problem in $$2^n$$ time - the discrete Gaussian strikes again! In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 563\u2013582. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.41"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-3-642-54631-0_25","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"MR Albrecht","year":"2014","unstructured":"Albrecht, M.R., Faug\u00e8re, J.-C., Fitzpatrick, R., Perret, L.: Lazy modulus switching for the BKW algorithm on LWE. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 429\u2013445. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54631-0_25"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996, pp. 99\u2013108. Association for Computing Machinery (1996)","DOI":"10.1145\/237814.237838"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-030-77870-5_17","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2021","author":"D Aggarwal","year":"2021","unstructured":"Aggarwal, D., Li, Z., Stephens-Davidowitz, N.: A $$2^{n\/2}$$-time algorithm for $$\\sqrt{n}$$-SVP and $$\\sqrt{n}$$-hermite SVP, and an improved time-approximation tradeoff for (H)SVP. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 467\u2013497. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77870-5_17"},{"issue":"5","key":"12_CR7","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D Aharonov","year":"2005","unstructured":"Aharonov, D., Regev, O.: Lattice problems in NP $$\\cap $$ coNP. J. ACM (JACM) 52(5), 749\u2013765 (2005)","journal-title":"J. ACM (JACM)"},{"key":"12_CR8","unstructured":"Aggarwal, D., Stephens-Davidowitz, N.: Just take the average! An embarrassingly simple $$2^n$$-time algorithm for SVP (and CVP). In: 1st Symposium on Simplicity in Algorithms (SOSA 2018), volume\u00a061 of Open Access Series in Informatics, pp. 12:1\u201312:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"12_CR9","doi-asserted-by":"publisher","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, 625\u2013635 (1993)","journal-title":"Math. Ann."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF02574039","volume":"13","author":"W Banaszczyk","year":"1995","unstructured":"Banaszczyk, W.: Inequalites for convex bodies and polar reciprocal lattices in $${\\mathbb{R} ^n}$$. Discrete Comput. Geom. 13, 217\u2013231 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM (JACM) 50(4), 506\u2013519 (2003)","journal-title":"J. ACM (JACM)"},{"key":"12_CR12","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 the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 575\u2013584. ACM (2013)","DOI":"10.1145\/2488608.2488680"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Ducas, L., Engelberts, L., Loyer, J.: Wagner\u2019s algorithm provably runs in subexponential time for SIS$$^\\infty $$. Cryptology ePrint Archive, Paper 2025\/575 (2025). Full version","DOI":"10.1007\/978-3-032-01855-7_12"},{"key":"12_CR14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-031-38548-3_6","volume-title":"CRYPTO 2023","author":"L Ducas","year":"2023","unstructured":"Ducas, L., Espitau, T., Postlethwaite, E.W.: Finding short integer solutions when the modulus is small. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14083, pp. 150\u2013176. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38548-3_6"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Ducas, L., et al.: CRYSTALS-Dilithium: a lattice-based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst., 238\u2013268 (2018)","DOI":"10.46586\/tches.v2018.i1.238-268"},{"key":"12_CR16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-031-15979-4_9","volume-title":"CRYPTO 2022","author":"T Espitau","year":"2022","unstructured":"Espitau, T., Tibouchi, M., Wallet, A., Yu, Y.: Shorter hash-and-sign lattice-based signatures. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 245\u2013275. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15979-4_9"},{"key":"12_CR17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-981-99-8739-9_3","volume-title":"ASIACRYPT 2023","author":"T Espitau","year":"2023","unstructured":"Espitau, T., Wallet, A., Yang, Yu.: On Gaussian sampling, smoothing parameter and application to signatures. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023. LNCS, vol. 14444, pp. 65\u201397. Springer, Singapore (2023). https:\/\/doi.org\/10.1007\/978-981-99-8739-9_3"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-319-70694-8_12","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"Q Guo","year":"2017","unstructured":"Guo, Q., Johansson, T., M\u00e5rtensson, E., Stankovski, P.: Coded-BKW with sieving. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 323\u2013346. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70694-8_12"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 197\u2013206. ACM (2008)","DOI":"10.1145\/1374376.1374407"},{"issue":"1","key":"12_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10623-016-0326-0","volume":"86","author":"G Herold","year":"2018","unstructured":"Herold, G., Kirshanova, E., May, A.: On the asymptotic complexity of solving LWE. Des. Codes Crypt. 86(1), 55\u201383 (2018)","journal-title":"Des. Codes Crypt."},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-662-47989-6_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"P Kirchner","year":"2015","unstructured":"Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 43\u201362. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_3"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/11538462_32","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V Lyubashevsky","year":"2005","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX\/RANDOM 2005. LNCS, vol. 3624, pp. 378\u2013389. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11538462_32"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-40041-4_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"D Micciancio","year":"2013","unstructured":"Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21\u201339. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_2"},{"issue":"1","key":"12_CR24","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D Micciancio","year":"2007","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267\u2013302 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"12_CR25","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/s00037-008-0251-3","volume":"17","author":"C Peikert","year":"2008","unstructured":"Peikert, C.: Limits on the hardness of lattice problems in $$l_{{p}}$$ norms. Comput. Complex. 17(2), 300\u2013351 (2008)","journal-title":"Comput. Complex."},{"key":"12_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-642-14623-7_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"C Peikert","year":"2010","unstructured":"Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80\u201397. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_5"},{"key":"12_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/11681878_8","volume-title":"Theory of Cryptography","author":"C Peikert","year":"2006","unstructured":"Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145\u2013166. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11681878_8"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 84\u201393. ACM (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","volume-title":"Advances in Cryptology \u2014 CRYPTO 2002","author":"D Wagner","year":"2002","unstructured":"Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288\u2013304. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45708-9_19"}],"updated-by":[{"DOI":"10.1007\/978-3-032-01855-7_23","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T00:00:00Z","timestamp":1768867200000}}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01855-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T19:21:49Z","timestamp":1768850509000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01855-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032018540","9783032018557"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01855-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"20 January 2026","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"A correction has been published.","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}