{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T02:27:56Z","timestamp":1749781676684,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,9]],"date-time":"2022-08-09T00:00:00Z","timestamp":1660003200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,9]],"date-time":"2022-08-09T00:00:00Z","timestamp":1660003200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["2019-04166"],"award-info":[{"award-number":["2019-04166"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001729","name":"Stiftelsen f\u00f6r&Strategisk Forskning","doi-asserted-by":"publisher","award":["RIT17-0005"],"award-info":[{"award-number":["RIT17-0005"]}],"id":[{"id":"10.13039\/501100001729","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001729","name":"Stiftelsen f\u00f6r&Strategisk Forskning","doi-asserted-by":"publisher","award":["SM17-0062"],"award-info":[{"award-number":["SM17-0062"]}],"id":[{"id":"10.13039\/501100001729","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Security Authority of Norway"},{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase. In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt\u201915 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show via simulation that it performs much better than previous theory predicts and develop a sample complexity model that matches the simulations better. We also introduce an improved, pruned version of the FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.<\/jats:p>","DOI":"10.1007\/s12095-022-00597-0","type":"journal-article","created":{"date-parts":[[2022,8,9]],"date-time":"2022-08-09T08:02:38Z","timestamp":1660032158000},"page":"331-350","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms"],"prefix":"10.1007","volume":"15","author":[{"given":"Qian","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5824-7282","authenticated-orcid":false,"given":"Erik","family":"M\u00e5rtensson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Stankovski Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,9]]},"reference":[{"key":"597_CR1","doi-asserted-by":"crossref","unstructured":"Guo, Q., M\u00e5rtensson, E., Stankovski Wagner, P: On the sample complexity of solving LWE using BKW-style algorithms. In: 2021 IEEE International Symposium on Information Theory (ISIT) (2021)","DOI":"10.1109\/ISIT45174.2021.9518190"},{"key":"597_CR2","unstructured":"Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, pp 124\u2013134. IEEE Computer Society Press, Santa Fe (1994)"},{"key":"597_CR3","unstructured":"NIST Post-Quantum Cryptography Standardization, https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography\/Post-Quantum-Cryptography-Standardization, accessed: 2019-09-24"},{"key":"597_CR4","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 Annual ACM Symposium on Theory of Computing, pp 84\u201393. ACM Press, Baltimore (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"597_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M. L., Kearns, M. J., Lipton, R. J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) Advances in Cryptology \u2013 CRYPTO\u201993, ser. Lecture Notes in Computer Science, vol. 773, pp 278\u2013291. Springer, Santa Barbara (1994)","DOI":"10.1007\/3-540-48329-2_24"},{"key":"597_CR6","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd Annual ACM Symposium on Theory of Computing, pp 435\u2013440. ACM Press, Portland (2000)","DOI":"10.1145\/335305.335355"},{"issue":"4","key":"597_CR7","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). [Online]. Available: https:\/\/doi.org\/10.1145\/792538.792543","journal-title":"J. ACM"},{"issue":"3","key":"597_CR8","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. Mathematical Cryptology 9(3), 169\u2013203 (2015)","journal-title":"J. Mathematical Cryptology"},{"issue":"1","key":"597_CR9","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10623-016-0326-0","volume":"86","author":"G Herold","year":"2018","unstructured":"Herold, G., Kirshanova, E., May, A.: On the asymptotic complexity of solving LWE. Des. Codes Cryptogr. 86(1), 55\u201383 (2018). [Online]. Available: https:\/\/doi.org\/10.1007\/s10623-016-0326-0","journal-title":"Des. Codes Cryptogr."},{"issue":"8","key":"597_CR10","doi-asserted-by":"publisher","first-page":"5243","DOI":"10.1109\/TIT.2019.2906233","volume":"65","author":"Q Guo","year":"2019","unstructured":"Guo, Q., Johansson, T., M\u00e5rtensson, E., Stankovski Wagner, P.: On the asymptotics of solving the LWE problem using coded-bkw with sieving. IEEE Trans. Information Theory 65(8), 5243\u20135259 (2019). [Online]. Available: https:\/\/doi.org\/10.1109\/TIT.2019.2906233","journal-title":"IEEE Trans. Information Theory"},{"key":"597_CR11","doi-asserted-by":"crossref","unstructured":"Duc, A., Tram\u00e8r, F., Vaudenay, S.: Better algorithms for LWE and LWR. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology \u2013 EUROCRYPT 2015, Part I, ser. Lecture Notes in Computer Science, vol. 9056, pp 173\u2013202. Springer, Sofia (2015)","DOI":"10.1007\/978-3-662-46800-5_8"},{"key":"597_CR12","doi-asserted-by":"crossref","unstructured":"Levieil, \u00c9., Fouque, P.-A.: An improved LPN algorithm. In: Prisco, R.D., Yung, M. (eds.) SCN 06: 5th International Conference on Security in Communication Networks, ser. Lecture Notes in Computer Science, vol. 4116, pp 348\u2013359. Springer, Maiori (2006)","DOI":"10.1007\/11832072_24"},{"key":"597_CR13","unstructured":"Kirchner, P.: Improved generalized birthday attack, Cryptology ePrint Archive, Report 2011\/377 (2011) http:\/\/eprint.iacr.org\/2011\/377"},{"key":"597_CR14","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) Advances in Cryptology \u2013 CRYPTO 2009, ser. Lecture Notes in Computer Science, vol. 5677, pp 595\u2013618. Springer, Santa Barbara (2009)","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"597_CR15","unstructured":"Bernstein, D.J., Lange, T.: Never trust a bunny, Cryptology ePrint Archive, Report 2012\/355 (2012) http:\/\/eprint.iacr.org\/2012\/355"},{"key":"597_CR16","doi-asserted-by":"crossref","unstructured":"Guo, Q., Johansson, T., L\u00f6ndahl, C.: Solving LPN using covering codes. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology \u2013 ASIACRYPT 2014, Part I, ser. Lecture Notes in Computer Science, vol. 8873, pp 1\u201320. Springer, Kaoshiung (2014)","DOI":"10.1007\/978-3-662-45611-8_1"},{"issue":"1","key":"597_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00145-019-09338-8","volume":"33","author":"Q Guo","year":"2020","unstructured":"Guo, Q., Johansson, T., L\u00f6ndahl, C.: Solving LPN using covering codes. J. Cryptology 33(1), 1\u201333 (2020). [Online]. Available: https:\/\/doi.org\/10.1007\/s00145-019-09338-8","journal-title":"J. Cryptology"},{"key":"597_CR18","doi-asserted-by":"crossref","unstructured":"Zhang, B., Jiao, L., Wang, M.: Faster algorithms for solving LPN. In: Fischlin, M., Coron, J.-S. (eds.) Advances in Cryptology \u2013 EUROCRYPT 2016, Part I, ser. Lecture Notes in Computer Science, vol. 9665, pp 168\u2013195. Springer, Vienna (2016)","DOI":"10.1007\/978-3-662-49890-3_7"},{"key":"597_CR19","doi-asserted-by":"crossref","unstructured":"Bogos, S., Vaudenay, S.: Optimization of LPN solving algorithms. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology \u2013 ASIACRYPT 2016, Part I, ser. Lecture Notes in Computer Science, vol. 10031, pp 703\u2013728. Springer, Hanoi (2016)","DOI":"10.1007\/978-3-662-53887-6_26"},{"issue":"3","key":"597_CR20","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 L P N using B K W and variants - implementation and analysis. Cryptogr Commun 8(3), 331\u2013369 (2016). [Online]. Available: https:\/\/doi.org\/10.1007\/s12095-015-0149-2","journal-title":"Cryptogr Commun"},{"issue":"2","key":"597_CR21","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. -C., Fitzpatrick, R., Perret, L: On the complexity of the BKW algorithm on LWE. Des Codes Cryptogr 74(2), 325\u2013354 (2015)","journal-title":"Des Codes Cryptogr"},{"key":"597_CR22","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Faug\u00e8re, J.-C., Fitzpatrick, R., Perret, L.: Lazy modulus switching for the BKW algorithm on LWE. In: Krawczyk, H. (ed.) PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography, ser. Lecture Notes in Computer Science, vol. 8383, pp 429\u2013445. Springer, Buenos Aires (2014)","DOI":"10.1007\/978-3-642-54631-0_25"},{"key":"597_CR23","doi-asserted-by":"crossref","unstructured":"Guo, Q., Johansson, T., Stankovski, P.: Coded-BKW: Solving LWE using lattice codes. In: Gennaro, R., Robshaw, M. J. B. (eds.) Advances in Cryptology \u2013 CRYPTO 2015, Part I, ser. Lecture Notes in Computer Science, vol. 9215, pp 23\u201342. Springer, Santa Barbara (2015)","DOI":"10.1007\/978-3-662-47989-6_2"},{"key":"597_CR24","doi-asserted-by":"crossref","unstructured":"Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. J. B. (eds.) Advances in Cryptology \u2013 CRYPTO 2015, Part I, ser. Lecture Notes in Computer Science, vol. 9215, pp 43\u201362. Springer, Santa Barbara (2015)","DOI":"10.1007\/978-3-662-47989-6_3"},{"key":"597_CR25","doi-asserted-by":"crossref","unstructured":"Guo, Q., Johansson, T., M\u00e5rtensson, E., Stankovski, P.: Coded-BKW with sieving. In: Advances in Cryptology \u2013 ASIACRYPT 2017, Part I, ser. Lecture Notes in Computer Science. In: Takagi, T., Peyrin, T. (eds.) , vol. 10624, pp 323\u2013346. Springer, Hong Kong (2017)","DOI":"10.1007\/978-3-319-70694-8_12"},{"key":"597_CR26","doi-asserted-by":"crossref","unstructured":"Esser, A., K\u00fcbler, R., May, A.: LPN decoded. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology \u2013 CRYPTO 2017, Part II, ser. Lecture Notes in Computer Science, vol. 10402, pp 486\u2013514. Springer, Santa Barbara (2017)","DOI":"10.1007\/978-3-319-63715-0_17"},{"key":"597_CR27","doi-asserted-by":"crossref","unstructured":"Esser, A., Heuer, F., K\u00fcbler, R., May, A., Sohler, C.: Dissection-BKW. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology \u2013 CRYPTO 2018, Part II, ser. Lecture Notes in Computer Science, vol. 10992, pp 638\u2013666. Springer, Santa Barbara (2018)","DOI":"10.1007\/978-3-319-96881-0_22"},{"key":"597_CR28","doi-asserted-by":"crossref","unstructured":"Delaplace, C., Esser, A., May, A.: Improved low-memory subset sum and LPN algorithms via multiple collisions. In: Albrecht, M. (ed.) 17th IMA International Conference on Cryptography and Coding, ser. Lecture Notes in Computer Science, vol. 11929, pp 178\u2013199. Springer, Oxford (2019)","DOI":"10.1007\/978-3-030-35199-1_9"},{"key":"597_CR29","doi-asserted-by":"publisher","unstructured":"M\u00e5rtensson, E.: The asymptotic complexity of coded-bkw with sieving using increasing reduction factors. In: IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, July 7-12, 2019. [Online]. Available: https:\/\/doi.org\/10.1109\/ISIT.2019.8849218, pp 2579\u20132583. IEEE (2019)","DOI":"10.1109\/ISIT.2019.8849218"},{"key":"597_CR30","doi-asserted-by":"crossref","unstructured":"Baign\u00e8res, T., Junod, P., Vaudenay, S.: How far can we go beyond linear cryptanalysis? In: Lee, P.J. (ed.) Advances in Cryptology \u2013 ASIACRYPT 2004, ser. Lecture Notes in Computer Science, vol. 3329, pp 432\u2013450. Springer, Jeju Island (2004)","DOI":"10.1007\/978-3-540-30539-2_31"},{"issue":"3","key":"597_CR31","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1109\/78.205723","volume":"41","author":"HV Sorensen","year":"1993","unstructured":"Sorensen, H. V., Burrus, C. S.: Efficient computation of the dft with only a subset of input or output points. IEEE Trans. Signal Process. 41(3), 1184\u20131200 (1993)","journal-title":"IEEE Trans. Signal Process."},{"key":"597_CR32","unstructured":"Budroni, A., M\u00e5rtensson, E., Stankovski Wagner, P.: FBBL - file-Based BKW for LWE https:\/\/github.com\/{{FBBL}}\/fbbl (2020)"},{"key":"597_CR33","doi-asserted-by":"crossref","unstructured":"Budroni, A., Guo, Q., Johansson, T., M\u00e5rtensson, E., Wagner, P.S.: Making the bkw algorithm practical for lwe. In: Bhargavan, K., Oswald, E., Prabhakaran, M. (eds.) Progress in Cryptology \u2013 INDOCRYPT 2020, pp 417\u201339. Springer International Publishing, Cham (2020)","DOI":"10.1007\/978-3-030-65277-7_19"},{"key":"597_CR34","unstructured":"TU Darmstadt Learning with Errors Challenge, https:\/\/www.latticechallenge.org\/lwe_challenge\/challenge.php, accessed: 2020-09-30"},{"key":"597_CR35","doi-asserted-by":"crossref","unstructured":"Albrecht, M. R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E. W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Ishai, Y. , Rijmen, V. (eds.) Advances in Cryptology \u2013 EUROCRYPT 2019, Part II, ser. Lecture Notes in Computer Science, vol. 11477, pp 717\u2013746. Springer, Darmstadt (2019)","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"597_CR36","unstructured":"Wikipedia contributors: Cumulative distribution function of order statistics \u2014 Wikipedia, the free encyclopedia, (2021) [Online; accessed 2021-09-29]. [Online]. Available: https:\/\/en.wikipedia.org\/wiki\/Orderstatistic#Cumulative_distribution_function_of_order_statistics"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-022-00597-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-022-00597-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-022-00597-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T16:13:17Z","timestamp":1676304797000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-022-00597-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,9]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["597"],"URL":"https:\/\/doi.org\/10.1007\/s12095-022-00597-0","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"type":"print","value":"1936-2447"},{"type":"electronic","value":"1936-2455"}],"subject":[],"published":{"date-parts":[[2022,8,9]]},"assertion":[{"value":"22 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}