{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:29:20Z","timestamp":1760236160820,"version":"build-2065373602"},"reference-count":38,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"publisher","award":["2015-04528","2019-04166"],"award-info":[{"award-number":["2015-04528","2019-04166"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001729","name":"Swedish Foundation for Strategic Research","doi-asserted-by":"publisher","award":["RIT17-0005","SM17-0062"],"award-info":[{"award-number":["RIT17-0005","SM17-0062"]}],"id":[{"id":"10.13039\/501100001729","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norwegian Research Council","doi-asserted-by":"publisher","award":["247742\/070"],"award-info":[{"award-number":["247742\/070"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>The learning with errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum\u2013Kalai\u2013Wasserman (BKW) algorithm. This paper presents new improvements of BKW-style algorithms for solving LWE instances. We target minimum concrete complexity, and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the fast Walsh Hadamard transform. The complexity of the resulting algorithm compares favorably with all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. We provide two implementations of the algorithm, one RAM-based approach that is optimized for speed, and one file-based approach which overcomes RAM limitations by using file-based storage.<\/jats:p>","DOI":"10.3390\/cryptography5040031","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T23:52:35Z","timestamp":1635465155000},"page":"31","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Improvements on Making BKW Practical for Solving LWE"],"prefix":"10.3390","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3544-5128","authenticated-orcid":false,"given":"Alessandro","family":"Budroni","sequence":"first","affiliation":[{"name":"Selmer Center, Department of Informatics, University of Bergen, 5007 Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qian","family":"Guo","sequence":"additional","affiliation":[{"name":"Selmer Center, Department of Informatics, University of Bergen, 5007 Bergen, Norway"},{"name":"Department of Electrical and Information Technology, Lund University, 221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1798-570X","authenticated-orcid":false,"given":"Thomas","family":"Johansson","sequence":"additional","affiliation":[{"name":"Department of Electrical and Information Technology, Lund University, 221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5824-7282","authenticated-orcid":false,"given":"Erik","family":"M\u00e5rtensson","sequence":"additional","affiliation":[{"name":"Selmer Center, Department of Informatics, University of Bergen, 5007 Bergen, Norway"},{"name":"Department of Electrical and Information Technology, Lund University, 221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2002-4240","authenticated-orcid":false,"given":"Paul Stankovski","family":"Wagner","sequence":"additional","affiliation":[{"name":"Department of Electrical and Information Technology, Lund University, 221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"ref_1","unstructured":"Shor, P.W. (1994, January 20\u201322). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA."},{"key":"ref_2","unstructured":"(2018, September 24). NIST Post-Quantum Cryptography Standardization, Available online: https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography\/Post-Quantum-Cryptography-Standardization."},{"key":"ref_3","unstructured":"Gabow, H.N., and Fagin, R. (2005). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 22\u201324 May 2005, ACM Press."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","article-title":"Cryptographic Primitives Based on Hard Learning Problems","volume":"Volume 773","author":"Stinson","year":"1994","journal-title":"Advances in Cryptology\u2014CRYPTO\u201993"},{"key":"ref_5","first-page":"403","article-title":"New Algorithms for Learning in Presence of Errors","volume":"Volume 6755","author":"Aceto","year":"2011","journal-title":"Proceedings of the ICALP 2011: 38th International Colloquium on Automata, Languages and Programming, Part I, Zurich, Switzerland, 4\u20138 July 2011"},{"key":"ref_6","unstructured":"Albrecht, M., Cid, C., Faugere, J.C., Fitzpatrick, R., and Perret, L. (2012, January 11\u201313). On the complexity of the Arora-Ge algorithm against LWE. Proceedings of the SCC 2012\u2013Third international conference on Symbolic Computation and Cryptography, Castro Urdiales, Spain."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of Learning with Errors","volume":"9","author":"Albrecht","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10623-016-0326-0","article-title":"On the asymptotic complexity of solving LWE","volume":"86","author":"Herold","year":"2018","journal-title":"Des. Codes Cryptogr."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"5243","DOI":"10.1109\/TIT.2019.2906233","article-title":"On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving","volume":"65","author":"Guo","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","unstructured":"Moriai, S., and Wang, H. (2020). Scalable Ciphertext Compression Techniques for Post-quantum KEMs and Their Applications. Advances in Cryptology\u2014ASIACRYPT 2020, Springer International Publishing."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., and Wasserman, H. (2000). Noise-tolerant learning, the parity problem, and the statistical query model. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, ACM Press.","DOI":"10.1145\/335305.335355"},{"key":"ref_12","first-page":"348","article-title":"An Improved LPN Algorithm","volume":"Volume 4116","author":"Prisco","year":"2006","journal-title":"Proceedings of the SCN 06: 5th International Conference on Security in Communication Networks, Maiori, Italy, 6\u20138 September 2006"},{"key":"ref_13","first-page":"1","article-title":"Solving LPN Using Covering Codes","volume":"Volume 8873","author":"Sarkar","year":"2014","journal-title":"Advances in Cryptology\u2014ASIACRYPT 2014, Part I"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00145-019-09338-8","article-title":"Solving LPN Using Covering Codes","volume":"33","author":"Guo","year":"2020","journal-title":"J. Cryptol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","article-title":"On the complexity of the BKW algorithm on LWE","volume":"74","author":"Albrecht","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref_16","first-page":"429","article-title":"Lazy Modulus Switching for the BKW Algorithm on LWE","volume":"Volume 8383","author":"Krawczyk","year":"2014","journal-title":"Proceedings of the PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography, Buenos Aires, Argentina, 26\u201328 March 2014"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/978-3-662-47989-6_2","article-title":"Coded-BKW: Solving LWE Using Lattice Codes","volume":"Volume 9215","author":"Gennaro","year":"2015","journal-title":"Advances in Cryptology\u2014CRYPTO 2015, Part I"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/978-3-662-47989-6_3","article-title":"An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices","volume":"Volume 9215","author":"Gennaro","year":"2015","journal-title":"Advances in Cryptology\u2014CRYPTO 2015, Part I"},{"key":"ref_19","unstructured":"Krauthgamer, R. (2016). New directions in nearest neighbor searching with applications to lattice sieving. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA, 10\u201312 January 2016, ACM-SIAM."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/978-3-319-70694-8_12","article-title":"Coded-BKW with Sieving","volume":"Volume 10624","author":"Takagi","year":"2017","journal-title":"Advances in Cryptology\u2014ASIACRYPT 2017, Part I"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"M\u00e5rtensson, E. (2019, January 7\u201312). The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849218"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-662-46800-5_8","article-title":"Better Algorithms for LWE and LWR","volume":"Volume 9056","author":"Oswald","year":"2015","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2015, Part I"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1007\/978-3-319-63715-0_17","article-title":"LPN Decoded","volume":"Volume 10402","author":"Katz","year":"2017","journal-title":"Advances in Cryptology\u2014CRYPTO 2017, Part II"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/978-3-319-96881-0_22","article-title":"Dissection-BKW","volume":"Volume 10992","author":"Shacham","year":"2018","journal-title":"Advances in Cryptology\u2014CRYPTO 2018, Part II"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Delaplace, C., Esser, A., and May, A. (2019). Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions. Lecture Notes in Computer Science, Proceedings of the 17th IMA International Conference on Cryptography and Coding, Oxford, UK, 16\u201318 December 2019, Springer.","DOI":"10.1007\/978-3-030-35199-1_9"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wiggers, T., and Samardjiska, S. (2021, January 12\u201320). Practically Solving LPN. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9518109"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","article-title":"Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems","volume":"Volume 5677","author":"Halevi","year":"2009","journal-title":"Advances in Cryptology\u2014CRYPTO 2009"},{"key":"ref_28","unstructured":"Kirchner, P. (2021, October 25). Improved Generalized Birthday Attack. Cryptology ePrint Archive, Report 2011\/377. Available online: http:\/\/eprint.iacr.org\/2011\/377."},{"key":"ref_29","unstructured":"(2021, May 01). TU Darmstadt Learning with Errors Challenge. Available online: https:\/\/www.latticechallenge.org\/lwe_challenge\/challenge.php."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","article-title":"Better Key Sizes (and Attacks) for LWE-Based Encryption","volume":"Volume 6558","author":"Kiayias","year":"2011","journal-title":"Topics in Cryptology\u2014CT-RSA 2011"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s13389-014-0072-z","article-title":"Using Bleichenbacher\u2019s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: Extended version","volume":"4","author":"Mulder","year":"2014","journal-title":"J. Cryptogr. Eng."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Guo, Q., M\u00e5rtensson, E., and Stankovski Wagner, P. (2021, January 12\u201320). On the Sample Complexity of solving LWE using BKW-Style Algorithms. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9518190"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1007\/978-3-540-30539-2_31","article-title":"How Far Can We Go Beyond Linear Cryptanalysis?","volume":"Volume 3329","author":"Lee","year":"2004","journal-title":"Advances in Cryptology\u2014ASIACRYPT 2004"},{"key":"ref_34","unstructured":"M\u00e5rtensson, E. (2020). Some Notes on Post-Quantum Cryptanalysis. [Ph.D. Thesis, Lund University]."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF02252874","article-title":"Fast Correlation Attacks on Certain Stream Ciphers","volume":"1","author":"Meier","year":"1989","journal-title":"J. Cryptol."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Knudsen, L.R. (2002). Fast Correlation Attacks: An Algorithmic Point of View. Advances in Cryptology\u2014EUROCRYPT 2002, Springer.","DOI":"10.1007\/3-540-46035-7"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/11535218_7","article-title":"The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption","volume":"Volume 3621","author":"Shoup","year":"2005","journal-title":"Advances in Cryptology\u2014CRYPTO 2005"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Budroni, A., Guo, Q., Johansson, T., M\u00e5rtensson, E., and Stankovski Wagner, P. (2020). Making the BKW Algorithm Practical for LWE. Progress in Cryptology\u2014INDOCRYPT 2020, Proceedings of the International Conference on Cryptology in India (INDOCRYPT 2020), Bangalore, India,13\u201316 December 2020, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-030-65277-7_19"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/5\/4\/31\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:22:21Z","timestamp":1760167341000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/5\/4\/31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":38,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["cryptography5040031"],"URL":"https:\/\/doi.org\/10.3390\/cryptography5040031","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2021,10,28]]}}}