{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T04:24:42Z","timestamp":1769315082375,"version":"3.49.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319968803","type":"print"},{"value":"9783319968810","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-96881-0_22","type":"book-chapter","created":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T19:54:39Z","timestamp":1532375679000},"page":"638-666","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Dissection-BKW"],"prefix":"10.1007","author":[{"given":"Andre","family":"Esser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix","family":"Heuer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"K\u00fcbler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"May","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,24]]},"reference":[{"key":"22_CR1","unstructured":"http:\/\/csrc.nist.gov\/groups\/ST\/post-quantum-crypto\/"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: 44th FOCS, pp. 298\u2013307. IEEE Computer Society Press, October 2003","DOI":"10.1109\/SFCS.2003.1238204"},{"issue":"A","key":"22_CR3","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1112\/S1461157016000292","volume":"19","author":"S Bai","year":"2016","unstructured":"Bai, S., Laarhoven, T., Stehl\u00e9, D.: Tuple lattice sieving. LMS J. Comput. Math. 19(A), 146\u2013162 (2016)","journal-title":"LMS J. Comput. Math."},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 93","author":"A Blum","year":"1994","unstructured":"Blum, A., Furst, M.L., Kearns, M.J., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278\u2013291. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-48329-2_24"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd ACM STOC, pp. 435\u2013440. ACM Press, May 2000","DOI":"10.1145\/335305.335355"},{"issue":"3","key":"22_CR6","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s12095-015-0149-2","volume":"8","author":"S Bogos","year":"2016","unstructured":"Bogos, S., Tram\u00e8r, F., Vaudenay, S.: On solving LPN using BKW and variants - implementation and analysis. Crypt. Commun. 8(3), 331\u2013369 (2016). https:\/\/doi.org\/10.1007\/s12095-015-0149-2","journal-title":"Crypt. Commun."},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/978-3-662-53887-6_26","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2016","author":"S Bogos","year":"2016","unstructured":"Bogos, S., Vaudenay, S.: Optimization of $$\\sf LPN$$ solving algorithms. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 703\u2013728. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53887-6_26"},{"key":"22_CR8","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. arXiv preprint quant-ph\/9605034 (1996)"},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/978-3-319-70503-3_24","volume-title":"Theory of Cryptography","author":"S Devadas","year":"2017","unstructured":"Devadas, S., Ren, L., Xiao, H.: On iterative collision search for LPN and\u00a0subset sum. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part II. LNCS, vol. 10678, pp. 729\u2013746. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_24"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/978-3-642-32009-5_42","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"I Dinur","year":"2012","unstructured":"Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 719\u2013740. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32009-5_42"},{"key":"22_CR11","unstructured":"Dohotaru, C., Hoyer, P.: Exact quantum lower bound for grover\u2019s problem. arXiv preprint arXiv:0810.3647 (2008)"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-319-78381-9_5","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"L Ducas","year":"2018","unstructured":"Ducas, L.: Shortest vector from lattice sieving: a few dimensions for free. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 125\u2013145. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_5"},{"key":"22_CR13","unstructured":"Esser, A., Heuer, F., K\u00fcbler, R., May, A., Sohler, C.: Dissection-BKW. Cryptology ePrint Archive, Report 2018\/569 (2018). https:\/\/eprint.iacr.org\/2018\/569"},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/978-3-319-63715-0_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"A Esser","year":"2017","unstructured":"Esser, A., K\u00fcbler, R., May, A.: LPN decoded. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 486\u2013514. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_17"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: 28th ACM STOC, pp. 212\u2013219. ACM Press, May 1996","DOI":"10.1145\/237814.237866"},{"key":"22_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-45611-8_1","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2014","author":"Q Guo","year":"2014","unstructured":"Guo, Q., Johansson, T., L\u00f6ndahl, C.: Solving LPN using covering codes. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part I. LNCS, vol. 8873, pp. 1\u201320. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45611-8_1"},{"key":"22_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-662-47989-6_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"Q Guo","year":"2015","unstructured":"Guo, Q., Johansson, T., Stankovski, P.: Coded-BKW: solving LWE using lattice codes. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 23\u201342. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_2"},{"key":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-662-54365-8_2","volume-title":"Public-Key Cryptography \u2013 PKC 2017","author":"G Herold","year":"2017","unstructured":"Herold, G., Kirshanova, E.: Improved algorithms for the approximate k-list problem in euclidean norm. In: Fehr, S. (ed.) PKC 2017, Part I. LNCS, vol. 10174, pp. 16\u201340. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54365-8_2"},{"key":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-319-76578-5_14","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"G Herold","year":"2018","unstructured":"Herold, G., Kirshanova, E., Laarhoven, T.: Speed-Ups and time\u2013memory trade-offs for tuple lattice sieving. In: Abdalla, M., Dahab, R. (eds.) PKC 2018, Part I. LNCS, vol. 10769, pp. 407\u2013436. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76578-5_14"},{"key":"22_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-13190-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"N Howgrave-Graham","year":"2010","unstructured":"Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 235\u2013256. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_12"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: 15th ACM STOC, pp. 193\u2013206. ACM Press, April 1983","DOI":"10.1145\/800061.808749"},{"key":"22_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-47989-6_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"T Laarhoven","year":"2015","unstructured":"Laarhoven, T.: Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 3\u201322. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_1"},{"key":"22_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/978-3-319-79063-3_14","volume-title":"Post-Quantum Cryptography","author":"T Laarhoven","year":"2018","unstructured":"Laarhoven, T., Mariano, A.: Progressive lattice sieving. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 292\u2013311. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-79063-3_14"},{"key":"22_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-319-22174-8_6","volume-title":"Progress in Cryptology \u2013 LATINCRYPT 2015","author":"T Laarhoven","year":"2015","unstructured":"Laarhoven, T., de Weger, B.: Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. In: Lauter, K.E., Rodr\u00edguez-Henr\u00edquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 101\u2013118. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-22174-8_6"},{"key":"22_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11832072_24","volume-title":"Security and Cryptography for Networks","author":"\u00c9 Levieil","year":"2006","unstructured":"Levieil, \u00c9., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348\u2013359. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11832072_24"},{"key":"22_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-642-38348-9_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"V Lyubashevsky","year":"2013","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-LWE cryptography. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 35\u201354. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_3"},{"key":"22_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Regev, O.: New lattice based cryptographic constructions. In: 35th ACM STOC, pp. 407\u2013416. ACM Press, June 2003","DOI":"10.1145\/780542.780603"},{"issue":"6","key":"22_CR29","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1\u201334:40 (2009). https:\/\/doi.org\/10.1145\/1568318.1568324","journal-title":"J. ACM"},{"issue":"3","key":"22_CR30","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R Schroeppel","year":"1981","unstructured":"Schroeppel, R., Shamir, A.: A T=O(2$${}^{\\text{ n\/2 }}$$), S=O(2$${}^{\\text{ n\/4 }}$$) algorithm for certain np-complete problems. SIAM J. Comput. 10(3), 456\u2013464 (1981). https:\/\/doi.org\/10.1137\/0210033","journal-title":"SIAM J. Comput."},{"key":"22_CR31","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"},{"key":"22_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-662-49890-3_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"B Zhang","year":"2016","unstructured":"Zhang, B., Jiao, L., Wang, M.: Faster algorithms for solving LPN. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 168\u2013195. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49890-3_7"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-96881-0_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T23:45:29Z","timestamp":1751759129000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-96881-0_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319968803","9783319968810"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96881-0_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"24 July 2018","order":1,"name":"first_online","label":"First Online","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":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"38","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}