{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T13:26:08Z","timestamp":1778073968041,"version":"3.51.4"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319637143","type":"print"},{"value":"9783319637150","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-63715-0_17","type":"book-chapter","created":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T01:19:51Z","timestamp":1501204791000},"page":"486-514","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":56,"title":["LPN Decoded"],"prefix":"10.1007","author":[{"given":"Andre","family":"Esser","sequence":"first","affiliation":[]},{"given":"Robert","family":"K\u00fcbler","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"May","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,29]]},"reference":[{"key":"17_CR1","unstructured":"http:\/\/csrc.nist.gov\/groups\/ST\/post-quantum-crypto\/"},{"key":"17_CR2","unstructured":"https:\/\/computing.llnl.gov\/?set=resources&page=SCF_resources#sequoia"},{"key":"17_CR3","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"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-29011-4_31","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"A Becker","year":"2012","unstructured":"Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in 2 n\/20: How 1 + 1 = 0 improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520\u2013536. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-29011-4_31"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-662-48324-4_20","volume-title":"Cryptographic Hardware and Embedded Systems \u2013 CHES 2015","author":"S Bela\u00efd","year":"2015","unstructured":"Bela\u00efd, S., Coron, J.-S., Fouque, P.-A., G\u00e9rard, B., Kammerer, J.-G., Prouff, E.: Improved side-channel analysis of finite-field multiplication. In: G\u00fcneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 395\u2013415. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-48324-4_20"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/978-3-642-22792-9_42","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"DJ Bernstein","year":"2011","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 743\u2013760. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-22792-9_42"},{"key":"17_CR7","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"},{"key":"17_CR8","unstructured":"Bogos, S., Tramer, F., Vaudenay, S.: On solving LPN using BKW and variants. Cryptology ePrint Archive, Report 2015\/049 (2015). http:\/\/eprint.iacr.org\/2015\/049"},{"key":"17_CR9","unstructured":"Bogos, S., Vaudenay, S.: Observations on the LPN solving algorithm from eurocrypt\u201916 (2016). http:\/\/eprint.iacr.org\/2016\/437"},{"key":"17_CR10","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. arXiv preprint quant-ph\/9605034 (1996)"},{"key":"17_CR11","unstructured":"Carrijo, J., Tonicelli, R., Imai, H., Nascimento, A.C.A.: A novel probabilistic passive attack on the protocols HB and HB+ (2008). http:\/\/eprint.iacr.org\/2008\/231"},{"key":"17_CR12","unstructured":"Damg\u00e5rd, I., Park, S.: How practical is public-key encryption based on LPN and ring-LPN? Cryptology ePrint Archive, Report 2012\/699 (2012). http:\/\/eprint.iacr.org\/2012\/699"},{"key":"17_CR13","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":"17_CR14","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"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Fossorier, M.P., Mihaljevic, M.J., Imai, H., Cui, Y., Matsuura, K.: A novel algorithm for solving the LPN problem and its application to security evaluation of the HB protocol for RFID authentication. Cryptology ePrint Archive, Report 2006\/197 (2006). http:\/\/eprint.iacr.org\/2006\/197","DOI":"10.1007\/11941378_5"},{"key":"17_CR16","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":"17_CR17","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":"17_CR18","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":"17_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-642-34047-5_20","volume-title":"Fast Software Encryption","author":"S Heyse","year":"2012","unstructured":"Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., Pietrzak, K.: Lapin: an efficient authentication protocol based on ring-LPN. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 346\u2013365. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-34047-5_20"},{"key":"17_CR20","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":"17_CR21","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":"17_CR22","doi-asserted-by":"crossref","unstructured":"Kachigar, G., Tillich, J.-P.: Quantum information set decoding algorithms. arXiv preprint arXiv:1703.00263 (2017)","DOI":"10.1007\/978-3-319-59879-6_5"},{"key":"17_CR23","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":"17_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: Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348\u2013359. Springer, Heidelberg (2006). doi:10.1007\/11832072_24"},{"key":"17_CR25","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":"17_CR26","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":"17_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-662-46800-5_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"A May","year":"2015","unstructured":"May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 203\u2013228. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-46800-5_9"},{"issue":"5","key":"17_CR28","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1109\/TIT.1962.1057777","volume":"8","author":"E Prange","year":"1962","unstructured":"Prange, E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5\u20139 (1962)","journal-title":"IRE Trans. Inf. Theory"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84\u201393. ACM Press, May 2005","DOI":"10.1145\/1060590.1060603"},{"key":"17_CR30","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 CRYPTO 2017"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-63715-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T18:33:09Z","timestamp":1750789989000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-63715-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319637143","9783319637150"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-63715-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"29 July 2017","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","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":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 August 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iacr.org\/conferences\/crypto2017\/","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"}]}}