{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T14:39:48Z","timestamp":1775745588589,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662479889","type":"print"},{"value":"9783662479896","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47989-6_3","type":"book-chapter","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T22:36:05Z","timestamp":1438295765000},"page":"43-62","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":69,"title":["An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices"],"prefix":"10.1007","author":[{"given":"Paul","family":"Kirchner","sequence":"first","affiliation":[]},{"given":"Pierre-Alain","family":"Fouque","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,1]]},"reference":[{"key":"3_CR1","unstructured":"Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, 9\u201312 June 2010. IEEE Computer Society (2010)"},{"key":"3_CR2","first-page":"1018","volume":"2014","author":"MR Albrecht","year":"2014","unstructured":"Albrecht, M.R., Cid, C., Faug\u00e8re, J., Fitzpatrick, R., Perret, L.: Algebraic algorithms for LWE problems. IACR Cryptology ePrint Arch. 2014, 1018 (2014)","journal-title":"IACR Cryptology ePrint Arch."},{"issue":"2","key":"3_CR3","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","volume":"74","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Cid, C., Faug\u00e8re, J., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Des. Codes Crypt. 74(2), 325\u2013354 (2015)","journal-title":"Des. Codes Crypt."},{"key":"3_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)"},{"key":"3_CR5","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: Halevi [19], pp. 595\u2013618","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-22006-7_34","volume-title":"Automata, Languages and Programming","author":"S Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 403\u2013415. Springer, Heidelberg (2011)"},{"issue":"1","key":"3_CR7","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(1), 625\u2013635 (1993)","journal-title":"Math. Ann."},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-642-36140-1_10","volume-title":"Radio Frequency Identification","author":"DJ Bernstein","year":"2013","unstructured":"Bernstein, D.J., Lange, T.: Never trust a bunny. In: Hoepman, J.-H., Verbauwhede, I. (eds.) RFIDSec 2012. LNCS, vol. 7739, pp. 137\u2013148. Springer, Heidelberg (2013). \n                      https:\/\/eprint.iacr.org\/2012\/355.pdf"},{"issue":"4","key":"3_CR9","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 50(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: Symposium on Theory of Computing Conference, STOC 2013, pp. 575\u2013584 (2013. \n                      http:\/\/perso.ens-lyon.fr\/damien.stehle\/downloads\/LWE.pdf","DOI":"10.1145\/2488608.2488680"},{"issue":"2","key":"3_CR11","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/120868669","volume":"43","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43(2), 831\u2013871 (2014)","journal-title":"SIAM J. Comput."},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-25385-0_1","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"Y Chen","year":"2011","unstructured":"Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1\u201320. Springer, Heidelberg (2011)"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01201999","volume":"2","author":"MJ Coster","year":"1992","unstructured":"Coster, M.J., Joux, A., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C., Stern, J.: Improved low-density subset sum algorithms. Comput. Complex. 2, 111\u2013128 (1992)","journal-title":"Comput. Complex."},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-38348-9_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"N D\u00f6ttling","year":"2013","unstructured":"D\u00f6ttling, N., M\u00fcller-Quade, J.: Lossy codes and a new variant of the learning-with-errors problem. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 18\u201334. Springer, Heidelberg (2013)"},{"key":"3_CR15","unstructured":"Duc, A., Tram\u00e8r, F., Vaudenay, S.: Better algorithms for lwe and LWR. Cryptology ePrint Archive, Report 2015\/056 (2015). \n                      http:\/\/eprint.iacr.org\/"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"C Gentry","year":"2013","unstructured":"Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 75\u201392. Springer, Heidelberg (2013)"},{"issue":"6","key":"3_CR17","doi-asserted-by":"publisher","first-page":"2325","DOI":"10.1109\/18.720541","volume":"44","author":"RM Gray","year":"1998","unstructured":"Gray, R.M., Neuhoff, D.L.: Quantization. IEEE Trans. Inf. Theor. 44(6), 2325\u20132383 (1998)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-319-07425-2","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. LNCS, vol. 8873, pp. 1\u201320. Springer, Heidelberg (2014)"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - CRYPTO 2009","year":"2009","unstructured":"Halevi, S. (ed.): CRYPTO 2009. LNCS, vol. 5677. Springer, Heidelberg (2009)"},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BFb0054868","volume-title":"Algorithmic Number Theory","author":"J Hoffstein","year":"1998","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267\u2013288. Springer, Heidelberg (1998)"},{"key":"3_CR21","first-page":"377","volume":"2011","author":"P Kirchner","year":"2011","unstructured":"Kirchner, P.: Improved generalized birthday attack. IACR Cryptology ePrint Arch. 2011, 377 (2011). \n                      http:\/\/eprint.iacr.org\/2011\/377.pdf","journal-title":"IACR Cryptology ePrint Arch."},{"issue":"1","key":"3_CR22","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"JC Lagarias","year":"1985","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM 32(1), 229\u2013246 (1985)","journal-title":"J. ACM"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A Lenstra","year":"1982","unstructured":"Lenstra, A., Lenstra, J.H., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathe. Ann. 261, 515\u2013534 (1982)","journal-title":"Mathe. Ann."},{"key":"3_CR24","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)"},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2011","author":"R Lindner","year":"2011","unstructured":"Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319\u2013339. Springer, Heidelberg (2011)"},{"key":"3_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-642-36095-4_19","volume-title":"Topics in Cryptology \u2013 CT-RSA 2013","author":"M Liu","year":"2013","unstructured":"Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293\u2013309. Springer, Heidelberg (2013)"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi [19], pp. 577\u2013594","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-11799-2_23","volume-title":"Theory of Cryptography","author":"V Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 382\u2013400. Springer, Heidelberg (2010)"},{"issue":"6","key":"3_CR29","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/2535925","volume":"60","author":"V Lyubashevsky","year":"2013","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 43 (2013)","journal-title":"J. ACM"},{"key":"3_CR30","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, Part I. LNCS, vol. 8042, pp. 21\u201339. Springer, Heidelberg (2013)"},{"issue":"1","key":"3_CR31","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s13389-014-0072-z","volume":"4","author":"ED Mulder","year":"2014","unstructured":"Mulder, E.D., Hutter, M., Marson, M.E., Pearson, P.: Using Bleichenbacher\u2019s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version. J. Crypt. Eng. 4(1), 33\u201345 (2014)","journal-title":"J. Crypt. Eng."},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31\u2013June 2 2009, pp. 333\u2013342. ACM (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"3_CR33","first-page":"254","volume":"2014","author":"T P\u00f6ppelmann","year":"2014","unstructured":"P\u00f6ppelmann, T., Ducas, L., G\u00fcneysu, T.: Enhanced lattice-based signatures on reconfigurable hardware. IACR Cryptology ePrint Arch. 2014, 254 (2014). \n                      https:\/\/eprint.iacr.org\/2014\/254.pdf","journal-title":"IACR Cryptology ePrint Arch."},{"issue":"6","key":"3_CR34","doi-asserted-by":"publisher","first-page":"34","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 (JACM) 56(6), 34 (2009). \n                      http:\/\/www.cims.nyu.edu\/regev\/papers\/qcrypto.pdf","journal-title":"J. ACM (JACM)"},{"key":"3_CR35","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 - 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\u2013303. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology -- CRYPTO 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47989-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T20:03:12Z","timestamp":1565380992000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47989-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662479889","9783662479896"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47989-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"1 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}