{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T12:07:30Z","timestamp":1775477250486,"version":"3.50.1"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319315164","type":"print"},{"value":"9783319315171","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-31517-1_2","type":"book-chapter","created":{"date-parts":[[2016,4,6]],"date-time":"2016-04-06T16:48:05Z","timestamp":1459961285000},"page":"24-43","source":"Crossref","is-referenced-by-count":48,"title":["On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Buchmann","sequence":"first","affiliation":[]},{"given":"Florian","family":"G\u00f6pfert","sequence":"additional","affiliation":[]},{"given":"Rachel","family":"Player","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Wunderer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,7]]},"reference":[{"key":"2_CR1","unstructured":"Albrecht, M.R., Cid, C., Faug\u00e8re, J., Fitzpatrick, R., Perret, L.: Algebraic algorithms for LWE problems. In: IACR Cryptology ePrint Archive 2014, p. 1018 (2014)"},{"issue":"2","key":"2_CR2","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":"2_CR3","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/978-3-642-54631-0_25","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"Martin R. Albrecht","year":"2014","unstructured":"Albrecht, M.R., Faug\u00e8re, J., Fitzpatrick, R., Perret, L.: Lazy modulus switching for the BKW algorithm on LWE. In: Krawczyk [28], pp. 429\u2013445"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/978-3-319-12160-4_18","volume-title":"Information Security and Cryptology \u2013 ICISC 2013","author":"MR Albrecht","year":"2014","unstructured":"Albrecht, M.R., Fitzpatrick, R., G\u00f6pfert, F.: On the efficacy of solving LWE by reduction to unique-SVP. In: Lee, H.-S., Han, D.-G. (eds.) ICISC 2013. LNCS, vol. 8565, pp. 293\u2013310. Springer, Heidelberg (2014)"},{"issue":"3","key":"2_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","volume":"9","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptology 9(3), 169\u2013203 (2015)","journal-title":"J. Math. Cryptology"},{"key":"2_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)"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BFb0023990","volume-title":"STACS 85","author":"L Babai","year":"1985","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice pointproblem. In: Mehlhorn, K. (ed.) STACS 85. LNCS, vol. 182, pp. 13\u201320. Springer, Berlin (1985)"},{"issue":"1","key":"2_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1\u201313 (1986)","journal-title":"Combinatorica"},{"key":"2_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/978-3-319-08344-5_21","volume-title":"Information Security and Privacy","author":"S Bai","year":"2014","unstructured":"Bai, S., Galbraith, S.D.: Lattice decoding attacks on binary LWE. In: Susilo, W., Mu, Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 322\u2013337. Springer, Heidelberg (2014)"},{"key":"2_CR10","unstructured":"Bai, S., Galbraith, S.D., Li, L., Sheffield, D.: Improved exponential-time algorithms for inhomogeneous-sis. In: IACR Cryptology ePrint Archive 2014, p. 593 (2014)"},{"issue":"4","key":"2_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 50(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from(standard) LWE. In: Ostrovsky, R. (eds.) FOCS 2011, pp. 97\u2013106, Palm Springs, CA, USA. IEEE Computer Society , 22\u201325 October 2011","DOI":"10.1109\/FOCS.2011.12"},{"key":"2_CR13","unstructured":"Buchmann, J., G\u00f6pfert, F., Player, R., Wunderer, T.: On the hardness of LWE with binary error: revisiting the hybridlattice-reduction and meet-in-the-middle attack. Cryptology ePrint Archive, Report 2016\/089 (2016). http:\/\/eprint.iacr.org\/"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","year":"2013","unstructured":"Canetti, R., Garay, J.A. (eds.): CRYPTO 2013, Part I. LNCS, vol. 8042. Springer, Heidelberg (2013)"},{"key":"2_CR15","unstructured":"Chen, H., Lauter, K.E., Stange, K.E.: Attacks on search RLWE. IACR Cryptology ePrint Archive 2015, p. 971 (2015)"},{"key":"2_CR16","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":"2_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-662-46800-5_8","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"A Duc","year":"2015","unstructured":"Duc, A., Tram\u00e8r, F., Vaudenay, S.: Better algorithms for LWE and LWR. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 173\u2013202. Springer, Heidelberg (2015)"},{"key":"2_CR18","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/978-3-642-40041-4_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"L\u00e9o Ducas","year":"2013","unstructured":"Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) [14], pp. 40\u201356"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-319-13051-4_11","volume-title":"Selected Areas in Cryptography \u2013 SAC 2014","author":"K Eisentr\u00e4ger","year":"2014","unstructured":"Eisentr\u00e4ger, K., Hallgren, S., Lauter, K.: Weak Instances of PLWE. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 183\u2013194. Springer, Heidelberg (2014)"},{"key":"2_CR20","first-page":"63","volume-title":"Lecture Notes in Computer Science","author":"Yara Elias","year":"2015","unstructured":"Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Provably weak instances of ring-LWE. In: Gennaro, R., Robshaw, M. (eds.) [21], pp. 63\u201392"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"CRYPTO 2015","year":"2015","unstructured":"Gennaro, R., Robshaw, M. (eds.): CRYPTO 2015. LNCS, vol. 9215. Springer, Berlin (2015)"},{"key":"2_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/978-3-642-33027-8_31","volume-title":"Cryptographic Hardware and Embedded Systems \u2013 CHES 2012","author":"T G\u00fcneysu","year":"2012","unstructured":"G\u00fcneysu, T., Lyubashevsky, V., P\u00f6ppelmann, T.: Practical lattice-based cryptography: a signature scheme for embedded systems. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 530\u2013547. Springer, Heidelberg (2012)"},{"key":"2_CR23","first-page":"23","volume-title":"Lecture Notes in Computer Science","author":"Qian Guo","year":"2015","unstructured":"Guo, Q., Johansson, T., Stankovski, P.: Coded-BKW: solving LWE using lattice codes. In: Gennaro, R., Robshaw, M. (eds.) [21], pp. 23\u201342"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-642-01957-9_27","volume-title":"Applied Cryptography and Network Security","author":"PS Hirschhorn","year":"2009","unstructured":"Hirschhorn, P.S., Hoffstein, J., Howgrave-Graham, N., Whyte, W.: Choosing NTRUEncrypt parameters in light of combined lattice reduction and MITM approaches. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 437\u2013455. Springer, Heidelberg (2009)"},{"key":"2_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-74143-5_9","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"N Howgrave-Graham","year":"2007","unstructured":"Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150\u2013169. Springer, Heidelberg (2007)"},{"issue":"3","key":"2_CR26","doi-asserted-by":"publisher","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(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"2_CR27","first-page":"43","volume-title":"Lecture Notes in Computer Science","author":"Paul Kirchner","year":"2015","unstructured":"Kirchner, P., Fouque, P.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) [21], pp. 43\u201362"},{"key":"2_CR28","series-title":"Lecture Notes in Computer Science","volume-title":"Public-Key Cryptography \u2013 PKC 2014","year":"2014","unstructured":"Krawczyk, H. (ed.): PKC 2014. LNCS, vol. 8383. Springer, Heidelberg (2014)"},{"key":"2_CR29","unstructured":"Laine, K., Lauter, K.E.: Key recovery for LWE in polynomial time. IACR Cryptology ePrint Archive 2015, p. 176 (2015)"},{"key":"2_CR30","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/978-3-642-54631-0_20","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"Adeline Langlois","year":"2014","unstructured":"Langlois, A., Ling, S., Nguyen, K., Wang, H.: Lattice-based group signature scheme with verifier-local revocation. In: Krawczyk, H. (ed.) [28], pp. 345\u2013361"},{"issue":"1","key":"2_CR31","doi-asserted-by":"publisher","first-page":"66","DOI":"10.3923\/ajms.2011.66.70","volume":"4","author":"S Li","year":"2011","unstructured":"Li, S.: Concise formulas for the area and volume of a hyperspherical cap. Asian J. Math. Stat. 4(1), 66\u201370 (2011)","journal-title":"Asian J. Math. Stat."},{"key":"2_CR32","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":"2_CR33","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)"},{"issue":"6","key":"2_CR34","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":"2_CR35","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/978-3-642-40041-4_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"Daniele Micciancio","year":"2013","unstructured":"Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) [14], pp. 21\u201339"},{"key":"2_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88702-7_5","volume-title":"Lattice-based cryptography","author":"D Micciancio","year":"2009","unstructured":"Micciancio, D., Regev, O.: Lattice-based cryptography. Springer, Berlin (2009)"},{"key":"2_CR37","unstructured":"Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. IACR Cryptology ePrint Archive 2015, p. 1123 (2015)"},{"key":"2_CR38","volume-title":"NIST Handbook of Mathematical Functions","author":"FW Olver","year":"2010","unstructured":"Olver, F.W.: NIST Handbook of Mathematical Functions. Cambridge University Press, Cambridge (2010)"},{"key":"2_CR39","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher, M. (eds.) STOC 2009, pp. 333\u2013342, Bethesda, MD, USA. ACM, May 31\u2013June 2, 2009"},{"issue":"6","key":"2_CR40","doi-asserted-by":"publisher","first-page":"1803","DOI":"10.1137\/080733954","volume":"40","author":"C Peikert","year":"2011","unstructured":"Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. SIAM J. Comput. 40(6), 1803\u20131844 (2011)","journal-title":"SIAM J. Comput."},{"key":"2_CR41","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 84\u201393, Baltimore, MD, USA. ACM, 22\u201324 May 2005","DOI":"10.1145\/1060590.1060603"},{"key":"2_CR42","unstructured":"Stein, W., et al.: Sage Mathematics Software (Version 6.3). The Sage Development Team (2014). http:\/\/www.sagemath.org"}],"container-title":["Lecture Notes in Computer Science","Progress in Cryptology \u2013 AFRICACRYPT 2016"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-31517-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,17]],"date-time":"2022-06-17T05:26:05Z","timestamp":1655443565000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-31517-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319315164","9783319315171"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-31517-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}