{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T00:06:40Z","timestamp":1769299600174,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T00:00:00Z","timestamp":1571097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T00:00:00Z","timestamp":1571097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003252","name":"Lund University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003252","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>We present a new algorithm for solving the LPN problem. The algorithm has a similar form as some previous methods, but includes a new key step that makes use of approximations of random words to a nearest codeword in a linear code. It outperforms previous methods for many parameter choices. In particular, we can now solve the <jats:inline-formula><jats:alternatives><jats:tex-math>$$(512,\\frac{1}{8})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>512<\/mml:mn><mml:mo>,<\/mml:mo><mml:mfrac><mml:mn>1<\/mml:mn><mml:mn>8<\/mml:mn><\/mml:mfrac><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> LPN instance with complexity less than <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{80}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>2<\/mml:mn><mml:mn>80<\/mml:mn><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula> operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.<\/jats:p>","DOI":"10.1007\/s00145-019-09338-8","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T21:37:43Z","timestamp":1571175463000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Solving LPN Using Covering Codes"],"prefix":"10.1007","volume":"33","author":[{"given":"Qian","family":"Guo","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Johansson","sequence":"additional","affiliation":[]},{"given":"Carl","family":"L\u00f6ndahl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"9338_CR1","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":"Martin R. Albrecht","year":"2014","unstructured":"M.R. Albrecht, J.C. Faug\u00e8re, R. Fitzpatrick, L. Perret, Lazy Modulus switching for the BKW algorithm on LWE, in H. Krawczyk, editor, Public-Key Cryptography\u2014PKC 2014. Lecture Notes in Computer Science, vol. 8383 (Springer Berlin, 2014), pp. 429\u2013445"},{"key":"9338_CR2","unstructured":"M. Alekhnovich, More on average case versus approximation complexity, in FOCS (IEEE Computer Society, 2003), pp. 298\u2013307"},{"issue":"4","key":"9338_CR3","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"A. Blum, A. Kalai, H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM,\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"9338_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-642-36140-1_10","volume-title":"Never trust a bunny, in Radio Frequency Identification Security and Privacy Issues","author":"D Bernstein","year":"2013","unstructured":"D. Bernstein, T. Lange, Never trust a bunny, in Radio Frequency Identification Security and Privacy Issues (Springer, Berlin, 2013), pp. 137\u2013148"},{"key":"9338_CR5","unstructured":"S. Bogos, F. Tramer, S. Vaudenay, On Solving LPN using BKW and Variants. Tech. rep., Cryptology ePrint Archive, Report 2015\/049 (2015)"},{"key":"9338_CR6","doi-asserted-by":"crossref","unstructured":"S. Bogos, S. Vaudenay, Optimization of lpn solving algorithms, in Advances in Cryptology\u2013ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4\u20138, 2016, Proceedings, Part I 22 (Springer, 2016) pp. 703\u2013728","DOI":"10.1007\/978-3-662-53887-6_26"},{"key":"9338_CR7","volume-title":"Covering Codes","author":"G Cohen","year":"1997","unstructured":"G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes (Elsevier, Amsterdam, 1997)"},{"key":"9338_CR8","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2012","unstructured":"T.M. Cover, J.A. Thomas, Elements of Information Theory (Wiley, New York, 2012)"},{"key":"9338_CR9","unstructured":"I. Damg\u00e5rd, S. Park, Is Public-Key Encryption Based on LPN Practical? Cryptology ePrint Archive, Report 2012\/699 (2012). \nhttp:\/\/eprint.iacr.org\/"},{"key":"9338_CR10","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-642-29011-4_22","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"Yevgeniy Dodis","year":"2012","unstructured":"Y. Dodis, E. Kiltz, K. Pietrzak, D. Wichs, Message authentication, revisited, in D. Pointcheval, T. Johansson, editors, EUROCRYPT 2012. LNCS, vol. 7237 (Springer, Heidelberg, 2012), pp. 355\u2013374"},{"key":"9338_CR11","first-page":"107","volume-title":"HELEN: a public-key cryptosystem based on the LPN and the decisional minimal distance problems, in AFRICACRYPT 2013","author":"A Duc","year":"2013","unstructured":"A. Duc, S. Vaudenay, HELEN: a public-key cryptosystem based on the LPN and the decisional minimal distance problems, in AFRICACRYPT 2013 (Springer, Berlin, 2013), pp. 107\u2013126"},{"key":"9338_CR12","doi-asserted-by":"crossref","unstructured":"A. Esser, R. K\u00fcbler, A. May, LPN decoded, in J. Katz, H. Shacham, editors, Advances in Cryptology\u2014CRYPTO 2017\u201437th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20\u201324, 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10402 (Springer, 2017), pp. 486\u2013514","DOI":"10.1007\/978-3-319-63715-0_17"},{"key":"9338_CR13","doi-asserted-by":"crossref","unstructured":"H. Gilbert, M.J.B. Robshaw, Y. Seurin, $$\\text{HB}^{\\#}$$: Increasing the security and the efficiency of $$\\text{ HB }^+$$, in N.P. Smart, editors, EUROCRYPT 2008. LNCS, vol. 4965 (Springer, Heidelberg, 2008), pp. 361\u2013378","DOI":"10.1007\/978-3-540-78967-3_21"},{"key":"9338_CR14","doi-asserted-by":"crossref","unstructured":"H. Gilbert, M.J.B. Robshaw, Y. Seurin, How to encrypt with the LPN problem, in L. Aceto, I. Damg\u00e5rd, L.A. Goldberg, M.M. Halldorsson, A. Ingolfsdottir, I. Walukiewicz, editors, ICALP 2008, Part II. LNCS, vol. 5126 (Springer, Heidelberg, 2008), pp. 679\u2013690","DOI":"10.1007\/978-3-540-70583-3_55"},{"key":"9338_CR15","unstructured":"H. Gilbert, M.J.B. Robshaw, H. Sibert, An Active Attack Against $$\\text{ HB }^+$$\u2014A Provably Secure Lightweight Authentication Protocol. Cryptology ePrint Archive, Report 2005\/237 (2005). \nhttp:\/\/eprint.iacr.org\/"},{"key":"9338_CR16","doi-asserted-by":"crossref","unstructured":"Q. Guo, T. Johansson, C. L\u00f6ndahl, Solving LPN using covering codes, in Advances in Cryptology\u2014ASIACRYPT 2014 (Springer, 2014), pp. 1\u201320","DOI":"10.1007\/978-3-662-45611-8_1"},{"issue":"11","key":"9338_CR17","doi-asserted-by":"publisher","first-page":"6204","DOI":"10.1109\/TIT.2015.2475738","volume":"61","author":"Q Guo","year":"2015","unstructured":"Q. Guo, T. Johansson, C. L\u00f6ndahl, A new algorithm for solving ring-LPN with a reducible polynomial. IEEE Trans. Inf. Theory,\u00a061(11), 6204\u20136212 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9338_CR18","doi-asserted-by":"crossref","unstructured":"Q. Guo, T. Johansson, P. Stankovski, Coded-BKW: solving LWE using lattice codes, in Advances in Cryptology\u2014CRYPTO 2015 (Springer, 2015), pp. 23\u201342","DOI":"10.1007\/978-3-662-47989-6_2"},{"key":"9338_CR19","doi-asserted-by":"crossref","unstructured":"Q. Guo, T. Johansson, E.M\u00e5rtensson, P. Stankovski, Coded-bkw with sieving, in T. Takagi, T. Peyrin, editors, Advances in Cryptology\u2014ASIACRYPT 2017\u201423rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3\u20137, 2017, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10624 (Springer, 2017), pp. 323\u2013346","DOI":"10.1007\/978-3-319-70694-8_12"},{"key":"9338_CR20","first-page":"346","volume":"2012","author":"S Heyse","year":"2012","unstructured":"S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K. Pietrzak, Lapin: an efficient authentication protocol based on ring-LPN, in FSE 2012 (2012), pp. 346\u2013365","journal-title":"FSE"},{"key":"9338_CR21","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"Advances in Cryptology \u2014 ASIACRYPT 2001","author":"Nicholas J. Hopper","year":"2001","unstructured":"N.J. Hopper, M. Blum, Secure human identification protocols, in C. Boyd, editor, ASIACRYPT 2001. LNCS, vol. 2248 (Springer, Heidelberg, 2001), pp. 52\u201366"},{"key":"9338_CR22","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/11535218_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"Ari Juels","year":"2005","unstructured":"A. Juels, S.A. Weis, Authenticating pervasive devices with human protocols, in V. Shoup, editor, CRYPTO 2005. LNCS, vol. 3621 (Springer, Heidelberg, 2005), pp. 293\u2013308"},{"key":"9338_CR23","doi-asserted-by":"crossref","unstructured":"J. Katz, J.S. Shin, Parallel and concurrent security of the HB and $$\\text{ HB }^+$$ protocols, in S. Vaudenay, editor, EUROCRYPT 2006. LNCS, vol. 4004 (Springer, Heidelberg, 2006), pp. 73\u201387","DOI":"10.1007\/11761679_6"},{"key":"9338_CR24","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":"Eike Kiltz","year":"2011","unstructured":"E. Kiltz, K. Pietrzak, D. Cash, A. Jain, D. Venturi, Efficient authentication from hard learning problems, in K.G Paterson, editor, EUROCRYPT 2011. LNCS, vol. 6632 (Springer, Heidelberg, 2011) pp. 7\u201326"},{"key":"9338_CR25","unstructured":"P. Kirchner, Improved Generalized Birthday Attack. Cryptology ePrint Archive, Report 2011\/377 (2011). \nhttp:\/\/eprint.iacr.org\/"},{"key":"9338_CR26","doi-asserted-by":"crossref","unstructured":"P. Kirchner, P.A. Fouque, An improved BKW algorithm for LWE with applications to cryptography and lattices, in Advances in Cryptology\u2014CRYPTO 2015 (Springer, 2015), pp. 43\u201362","DOI":"10.1007\/978-3-662-47989-6_3"},{"issue":"1","key":"9338_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10623-011-9484-2","volume":"62","author":"M Lamberger","year":"2012","unstructured":"M. Lamberger, F. Mendel, V. Rijmen, K. Simoens, Memoryless near-collisions via coding theory. Des. Codes Cryptogr.\u00a062(1), 1-18 (2012)","journal-title":"Des. Codes Cryptogr."},{"issue":"3","key":"9338_CR28","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.ipl.2012.11.004","volume":"113","author":"M Lamberger","year":"2013","unstructured":"M. Lamberger, E. Teufl, Memoryless near-collisions, revisited. Inf. Process. Lett.,\u00a0113(3), 60-66 (2013)","journal-title":"Inf. Process. Lett."},{"key":"9338_CR29","first-page":"348","volume-title":"Lecture Notes in Computer Science","author":"\u00c9ric Levieil","year":"2006","unstructured":"E. Levieil, P.A. Fouque, An improved LPN algorithm, in Proceedings of SCN 2006. LNCS 4116 (Springer, Heidelberg, 2006), pp. 348\u2013359"},{"issue":"1","key":"9338_CR30","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00145-007-9013-7","volume":"21","author":"AA Sel\u00e7uk","year":"2008","unstructured":"A.A. Sel\u00e7uk, On probability of success in linear and differential cryptanalysis. J. Cryptol.\u00a021(1), 131\u2013147 (2008)","journal-title":"J. Cryptol."},{"key":"9338_CR31","unstructured":"S. Vaudenay, Private Communication"},{"key":"9338_CR32","doi-asserted-by":"crossref","unstructured":"B. Zhang, L. Jiao, M. Wang, Faster algorithms for solving LPN, in EUROCRYPT 2016 (Springer, 2016), pp. 168\u2013195","DOI":"10.1007\/978-3-662-49890-3_7"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09338-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-019-09338-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09338-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,13]],"date-time":"2020-10-13T23:12:19Z","timestamp":1602630739000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-019-09338-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,15]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["9338"],"URL":"https:\/\/doi.org\/10.1007\/s00145-019-09338-8","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,15]]},"assertion":[{"value":"23 October 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}