{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:43:58Z","timestamp":1769298238395,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662538869","type":"print"},{"value":"9783662538876","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-53887-6_26","type":"book-chapter","created":{"date-parts":[[2016,11,8]],"date-time":"2016-11-08T12:11:21Z","timestamp":1478607081000},"page":"703-728","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Optimization of $$\\mathsf {LPN}$$ Solving Algorithms"],"prefix":"10.1007","author":[{"given":"Sonia","family":"Bogos","sequence":"first","affiliation":[]},{"given":"Serge","family":"Vaudenay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,9]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 11\u201314 October 2003, Cambridge, MA, USA, pp. 298\u2013307. IEEE Computer Society (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"26_CR2","first-page":"1209","volume":"11","author":"VL Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of a directed graph. Sov. Math. Dokl. 11, 1209\u20131210 (1970)","journal-title":"Sov. Math. Dokl."},{"issue":"9","key":"26_CR3","doi-asserted-by":"publisher","first-page":"4335","DOI":"10.1109\/TIT.2008.928277","volume":"54","author":"TS Baicheva","year":"2008","unstructured":"Baicheva, T.S., Bouyukliev, I., Dodunekov, S.M., Fack, V.: Binary and ternary linear quasi-perfect codes with small dimensions. IEEE Trans. Inf. Theory 54(9), 4335\u20134339 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"26_CR4","unstructured":"Bernstein, D.J.: Optimizing linear maps modulo 2. http:\/\/binary.cr.yp.to\/linearmod2-20090830.pdf"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-642-36140-1_10","volume-title":"Radio Frequency Identification. Security and Privacy Issues","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). doi:10.1007\/978-3-642-36140-1_10"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: Frances Yao, F., Luks, E.M. (eds.) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 21\u201323 May 2000, Portland, OR, USA, pp. 435\u2013440. ACM (2000)","DOI":"10.1145\/335305.335355"},{"issue":"3","key":"26_CR7","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)","journal-title":"Crypt. Commun."},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/978-3-662-48800-3_29","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"S Bogos","year":"2015","unstructured":"Bogos, S., Vaudenay, S.: How to sequentialize independent parallel attacks? In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 704\u2013731. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-48800-3_29"},{"key":"26_CR9","unstructured":"Bogos, S., Vaudenay, S.: Observations on the LPN Solving Algorithm from Eurocrypt2016. Cryptology ePrint Archive, Report 2016\/451 (2016). https:\/\/eprint.iacr.org\/2016\/451"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Bringer, J., Chabanne, H., Dottax, E.: HB$${}^{\\text{++}}$$: a lightweight authentication protocol secure against some attacks. In: Second International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2006), 29 June 2006, Lyon, France, pp. 28\u201333. IEEE Computer Society (2006)","DOI":"10.1109\/SECPERU.2006.10"},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1587\/transfun.E92.A.658","volume":"92\u2013A(2)","author":"J Carrijo","year":"2009","unstructured":"Carrijo, J., Tonicelli, R., Imai, H., Nascimento, A.C.A.: A novel probabilistic passive attack on the protocols HB and HB$${}^{\\text{+ }}$$. IEICE Trans. 92\u2013A(2), 658\u2013662 (2009)","journal-title":"IEICE Trans."},{"key":"26_CR12","volume-title":"Covering Codes","author":"G Cohen","year":"1997","unstructured":"Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. North-Holland Mathematical Library, Elsevier Science, Amsterdam (1997)"},{"issue":"3","key":"26_CR13","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1109\/TIT.1985.1057043","volume":"31","author":"GD Cohen","year":"1985","unstructured":"Cohen, G.D., Karpovsky, M.G., Mattson Jr., H.F., Schatz, J.R.: Covering radius - survey and recent results. IEEE Trans. Inf. Theory 31(3), 328\u2013343 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"26_CR14","first-page":"699","volume":"2012","author":"I Damg\u00e5rd","year":"2012","unstructured":"Damg\u00e5rd, I., Park, S.: Is public-key encryption based on LPN practical? IACR Cryptology ePrint Arch. 2012, 699 (2012)","journal-title":"IACR Cryptology ePrint Arch."},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-642-34961-4_30","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"N D\u00f6ttling","year":"2012","unstructured":"D\u00f6ttling, N., M\u00fcller-Quade, J., Nascimento, A.C.A.: IND-CCA secure cryptography based on a variant of the LPN problem. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 485\u2013503. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-34961-4_30"},{"key":"26_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-38553-7_6","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2013","author":"A Duc","year":"2013","unstructured":"Duc, A., Vaudenay, S.: HELEN: a public-key cryptosystem based on the LPN and the decisional minimal distance problems. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) AFRICACRYPT 2013. LNCS, vol. 7918, pp. 107\u2013126. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-38553-7_6"},{"issue":"11","key":"26_CR17","doi-asserted-by":"publisher","first-page":"3938","DOI":"10.1109\/TIT.2005.856944","volume":"51","author":"T Etzion","year":"2005","unstructured":"Etzion, T., Mounits, B.: Mounits.: quasi-perfect codes with small distance. IEEE Trans. Inf. Theory 51(11), 3938\u20133946 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/11941378_5","volume-title":"Progress in Cryptology - INDOCRYPT 2006","author":"MPC Fossorier","year":"2006","unstructured":"Fossorier, M.P.C., Mihaljevi\u0107, M.J., Imai, H., Cui, Y., Matsuura, K.: An algorithm for solving the LPN problem and its application to security evaluation of the HB protocols for RFID authentication. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 48\u201362. Springer, Heidelberg (2006). doi:10.1007\/11941378_5"},{"key":"26_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-540-78967-3_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"H Gilbert","year":"2008","unstructured":"Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB#: increasing the security and efficiency of HB$$^{+}$$. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361\u2013378. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-78967-3_21"},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/978-3-540-70583-3_55","volume-title":"Automata, Languages and Programming","author":"H Gilbert","year":"2008","unstructured":"Gilbert, H., Robshaw, M.J.B., Seurin, Y.: How to encrypt with the LPN problem. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 679\u2013690. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-70583-3_55"},{"issue":"3","key":"26_CR21","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1109\/TIT.1985.1057039","volume":"31","author":"RL Graham","year":"1985","unstructured":"Graham, R.L., Sloane, N.J.A.: On the covering radius of codes. IEEE Trans. Inf. Theory 31(3), 385\u2013401 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"26_CR22","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. LNCS, vol. 8873, pp. 1\u201320. Springer, Heidelberg (2014). doi:10.1007\/978-3-662-45611-8_1"},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"Advances in Cryptology \u2014 ASIACRYPT 2001","author":"NJ Hopper","year":"2001","unstructured":"Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52\u201366. Springer, Heidelberg (2001). doi:10.1007\/3-540-45682-1_4"},{"key":"26_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/11535218_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"A Juels","year":"2005","unstructured":"Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293\u2013308. Springer, Heidelberg (2005). doi:10.1007\/11535218_18"},{"key":"26_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-54631-0_1","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"E Kiltz","year":"2014","unstructured":"Kiltz, E., Masny, D., Pietrzak, K.: Simple chosen-ciphertext security from low-noise LPN. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 1\u201318. Springer, Heidelberg (2014). doi:10.1007\/978-3-642-54631-0_1"},{"key":"26_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-642-20465-4_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"E Kiltz","year":"2011","unstructured":"Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient authentication from hard learning problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 7\u201326. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-20465-4_3"},{"key":"26_CR27","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). doi:10.1007\/978-3-662-47989-6_3"},{"key":"26_CR28","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: Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348\u2013359. Springer, Heidelberg (2006). doi:10.1007\/11832072_24"},{"key":"26_CR29","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). doi:10.1007\/11538462_32"},{"key":"26_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-642-40084-1_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"V Lyubashevsky","year":"2013","unstructured":"Lyubashevsky, V., Masny, D.: Man-in-the-middle secure authentication schemes from LPN and weak PRFs. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 308\u2013325. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-40084-1_18"},{"key":"26_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-25385-0_6","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"A May","year":"2011","unstructured":"May, A., Meurer, A., Thomae, E.: Decoding random linear codes in $$\\tilde{\\cal{O}}(2^{0.054n})$$. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107\u2013124. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-25385-0_6"},{"key":"26_CR32","volume-title":"Error-Correcting Codes","author":"WW Peterson","year":"1972","unstructured":"Peterson, W.W., Weldon, E.J.: Error-Correcting Codes. MIT Press, Cambridge (1972)"},{"key":"26_CR33","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, Baltimore, MD, USA, 22\u201324 May 2005, pp. 84\u201393. ACM (2005)","DOI":"10.1145\/1060590.1060603"},{"issue":"1","key":"26_CR34","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00145-007-9013-7","volume":"21","author":"AA Sel\u00e7uk","year":"2008","unstructured":"Sel\u00e7uk, A.A.: On probability of success in linear and differential cryptanalysis. J. Cryptology 21(1), 131\u2013147 (2008)","journal-title":"J. Cryptology"},{"key":"26_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFb0019850","volume-title":"Coding Theory and Applications","author":"J Stern","year":"1989","unstructured":"Stern, J.: A method for finding codewords of small weight. In: Cohen, G.D., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106\u2013113. Springer, Heidelberg (1989). doi:10.1007\/BFb0019850"},{"key":"26_CR36","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. LNCS, vol. 9665, pp. 168\u2013195. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-49890-3_7"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2016"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53887-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T04:48:22Z","timestamp":1749703702000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-53887-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662538869","9783662538876"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53887-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 November 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ASIACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Theory and Application of Cryptology and Information Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hanoi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vietnam","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"asiacrypt2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.asiacrypt2016.org\/","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"}]}}