{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:01Z","timestamp":1750308001221,"version":"3.41.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T00:00:00Z","timestamp":1735776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T00:00:00Z","timestamp":1735776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Dutch National Growth Fund","award":["Quantum Delta NL program"],"award-info":[{"award-number":["Quantum Delta NL program"]}]},{"name":"ERC Starting Grant","award":["947821 (ARTICULATE)","947821 (ARTICULATE)"],"award-info":[{"award-number":["947821 (ARTICULATE)","947821 (ARTICULATE)"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s10623-024-01545-0","type":"journal-article","created":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T01:34:04Z","timestamp":1735868044000},"page":"1611-1644","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum sieving for code-based cryptanalysis and its limitations for ISD"],"prefix":"10.1007","volume":"93","author":[{"given":"Lynn","family":"Engelberts","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simona","family":"Etinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johanna","family":"Loyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,2]]},"reference":[{"key":"1545_CR1","doi-asserted-by":"publisher","unstructured":"Ajtai M., Kumar R., Sivakumar D.: A sieve algorithm for the shortest lattice vector problem. In: Vitter J.S., Spirakis P.G., Yannakakis M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Crete, Greece, 6\u20138 July 2001, pp. 601\u2013610. ACM (2001). https:\/\/doi.org\/10.1145\/380752.380857.","DOI":"10.1145\/380752.380857"},{"issue":"1","key":"1545_CR2","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007). https:\/\/doi.org\/10.1137\/S0097539705447311.","journal-title":"SIAM J. Comput."},{"key":"1545_CR3","doi-asserted-by":"publisher","unstructured":"Becker A., Ducas L., Gama N., Laarhoven T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer R. (ed.) Proceedings of the Twenty-Seventh Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10\u201312 January 2016, pp. 10\u201324. SIAM (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch2.","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"1545_CR4","doi-asserted-by":"publisher","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.) Advances in Cryptology\u2014EUROCRYPT 2012\u201431st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 15\u201319 April 2012. Proceedings. Lecture Notes in Computer Science, vol. 7237, pp. 520\u2013536. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_31.","DOI":"10.1007\/978-3-642-29011-4_31"},{"issue":"3","key":"1545_CR5","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"ER Berlekamp","year":"1978","unstructured":"Berlekamp E.R., McEliece R.J., Tilborg H.C.A.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978). https:\/\/doi.org\/10.1109\/TIT.1978.1055873.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1545_CR6","doi-asserted-by":"publisher","unstructured":"Bernstein D.J., Jeffery S., Lange T., Meurer A.: Quantum algorithms for the subset-sum problem. In: Gaborit P. (ed.) Post-quantum Cryptography\u20145th International Workshop, PQCrypto 2013, Limoges, France, 4\u20137 June 2013. Proceedings. Lecture Notes in Computer Science, vol. 7932, pp. 16\u201333. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-38616-9_2.","DOI":"10.1007\/978-3-642-38616-9_2"},{"key":"1545_CR7","doi-asserted-by":"publisher","unstructured":"Bernstein D.J.: Grover vs. McEliece. In: Sendrier N. (ed.) Post-quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, 25\u201328 May 2010. Proceedings. Lecture Notes in Computer Science, vol. 6061, pp. 73\u201380. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-12929-2_6.","DOI":"10.1007\/978-3-642-12929-2_6"},{"key":"1545_CR8","doi-asserted-by":"publisher","unstructured":"Bonnetain X., Chailloux A., Schrottenloher A., Shen Y.: Finding many collisions via reusable quantum walks\u2014application to lattice sieving. In: Hazay C., Stam M. (eds.) Advances in Cryptology\u2014EUROCRYPT 2023\u201442nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23\u201327 April 2023, Proceedings, Part V. Lecture Notes in Computer Science, vol. 14008, pp. 221\u2013251. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-30589-4_8.","DOI":"10.1007\/978-3-031-30589-4_8"},{"key":"1545_CR9","doi-asserted-by":"publisher","unstructured":"Both L., May A.: Decoding linear codes with high error rate and its impact for LPN security. In: Lange T., Steinwandt R. (eds.) Post-quantum Cryptography\u20149th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, 9\u201311 April 2018, Proceedings. Lecture Notes in Computer Science, vol. 10786, pp. 25\u201346. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-79063-3_2.","DOI":"10.1007\/978-3-319-79063-3_2"},{"issue":"4\u20135","key":"1545_CR10","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M Boyer","year":"1998","unstructured":"Boyer M., Brassard G., H\u00f8yer P., Tapp A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4\u20135), 493\u2013505 (1998).","journal-title":"Fortschr. Phys."},{"key":"1545_CR11","doi-asserted-by":"publisher","unstructured":"Brassard G., H\u00f8yer P., Mosca M., Tapp A.: Quantum amplitude amplification and estimation. In: Quantum Computation and Information, pp. 53\u201374 (2000). https:\/\/doi.org\/10.1090\/conm\/305\/05215.","DOI":"10.1090\/conm\/305\/05215"},{"key":"1545_CR12","doi-asserted-by":"publisher","unstructured":"Carrier K., Debris-Alazard T., Meyer-Hilfiger C., Tillich J.: Statistical decoding 2.0: reducing decoding to LPN. In: Agrawal S., Lin D. (eds.) Advances in Cryptology\u2014ASIACRYPT 2022\u201428th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, 5\u20139 December 2022, Proceedings, Part IV. Lecture Notes in Computer Science, vol. 13794, pp. 477\u2013507. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-22972-5_17.","DOI":"10.1007\/978-3-031-22972-5_17"},{"key":"1545_CR13","unstructured":"Carrier K.: Recherche de presque-collisions pour le d\u00e9codage et la reconnaissance de codes correcteurs (near-collisions finding problem for decoding and recognition of error correcting codes). PhD Thesis, Sorbonne University (2020). https:\/\/tel.archives-ouvertes.fr\/tel-03370678."},{"key":"1545_CR14","doi-asserted-by":"publisher","unstructured":"Chailloux A., Loyer J.: Lattice sieving via quantum random walks. In: Tibouchi M., Wang H. (eds.) Advances in Cryptology\u2014ASIACRYPT 2021\u201427th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 6\u201310 December 2021, Proceedings, Part IV. Lecture Notes in Computer Science, vol. 13093, pp. 63\u201391. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-92068-5_3.","DOI":"10.1007\/978-3-030-92068-5_3"},{"issue":"3\u20134","key":"1545_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<197::AID-RSA2>3.0.CO;2-K","volume":"17","author":"C Cooper","year":"2000","unstructured":"Cooper C.: On the distribution of rank of a random matrix over a finite field. Random Struct. Algorithms 17(3\u20134), 197\u2013212 (2000).","journal-title":"Random Struct. Algorithms"},{"key":"1545_CR16","doi-asserted-by":"publisher","unstructured":"Ducas L., Esser A., Etinski S., Kirshanova E.: Asymptotics and improvements of sieving for codes. In: Joye M., Leander G. (eds.), Advances in Cryptology\u2014EUROCRYPT 2024\u201443rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, 26-30 May 2024, Proceedings, Part VI. Lecture Notes in Computer Science, vol. 14656, pp. 151\u2013180. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-58754-2_6.","DOI":"10.1007\/978-3-031-58754-2_6"},{"key":"1545_CR17","unstructured":"Dumer I.: On minimum distance decoding of linear codes. In: Proceedings of the 5th Joint Soviet\u2013Swedish International Workshop Information Theory, 1991, pp. 50\u201352 (1991)."},{"key":"1545_CR18","doi-asserted-by":"publisher","unstructured":"Finiasz M., Sendrier N.: Security bounds for the design of code-based cryptosystems. In: Matsui M. (ed.) Advances in Cryptology\u2014ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 6\u201310 December 2009. Proceedings. Lecture Notes in Computer Science, vol. 5912, pp. 88\u2013105. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-10366-7_6.","DOI":"10.1007\/978-3-642-10366-7_6"},{"key":"1545_CR19","doi-asserted-by":"publisher","unstructured":"Grover L.K.: A fast quantum mechanical algorithm for database search. In: Miller G.L. (ed.) Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, 22\u201324 May 1996, pp. 212\u2013219. ACM (1996). https:\/\/doi.org\/10.1145\/237814.237866.","DOI":"10.1145\/237814.237866"},{"key":"1545_CR20","unstructured":"Guo Q., Johansson T., Nguyen V.: A new sieving-style information-set decoding algorithm. IACR Cryptology ePrint Archive, p. 247 (2023)."},{"key":"1545_CR21","doi-asserted-by":"publisher","unstructured":"Kachigar G., Tillich J.: Quantum information set decoding algorithms. In: Lange T., Takagi T. (eds.) Post-quantum Cryptography\u20148th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, 26\u201328 June 2017, Proceedings. Lecture Notes in Computer Science, vol. 10346, pp. 69\u201389. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-59879-6_5.","DOI":"10.1007\/978-3-319-59879-6_5"},{"key":"1545_CR22","doi-asserted-by":"publisher","unstructured":"Kirshanova E.: Improved quantum information set decoding. In: Lange T., Steinwandt R. (eds.) Post-quantum Cryptography\u20149th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, 9\u201311 April 2018, Proceedings. Lecture Notes in Computer Science, vol. 10786, pp. 507\u2013527. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-79063-3_24.","DOI":"10.1007\/978-3-319-79063-3_24"},{"key":"1545_CR23","doi-asserted-by":"publisher","unstructured":"Kirshanova E., M\u00e5rtensson E., Postlethwaite E.W., Moulik S.R.: Quantum algorithms for the approximate k-list problem and their application to lattice sieving. In: Galbraith S.D., Moriai S. (eds.) Advances in Cryptology\u2014ASIACRYPT 2019\u201425th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 8\u201312 December 2019, Proceedings, Part I. Lecture Notes in Computer Science, vol. 11921, pp. 521\u2013551. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-34578-5_19.","DOI":"10.1007\/978-3-030-34578-5_19"},{"key":"1545_CR24","unstructured":"Laarhoven T.: Search problems in cryptography, from fingerprinting to lattice sieving. PhD Thesis, Eindhoven University of Technology (2015). https:\/\/thijs.com\/docs\/phd-final.pdf."},{"issue":"1","key":"1545_CR25","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1137\/090745854","volume":"40","author":"F Magniez","year":"2011","unstructured":"Magniez F., Nayak A., Roland J., Santha M.: Search via quantum walk. SIAM J. Comput. 40(1), 142\u2013164 (2011). https:\/\/doi.org\/10.1137\/090745854.","journal-title":"SIAM J. Comput."},{"key":"1545_CR26","doi-asserted-by":"publisher","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.) Advances in Cryptology\u2014ASIACRYPT 2011\u201417th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 4\u20138 December 2011. Proceedings. Lecture Notes in Computer Science, vol. 7073, pp. 107\u2013124. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-25385-0_6.","DOI":"10.1007\/978-3-642-25385-0_6"},{"key":"1545_CR27","doi-asserted-by":"publisher","unstructured":"May A., Ozerov I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald E., Fischlin M. (eds.) Advances in Cryptology\u2014EUROCRYPT 2015\u201434th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 26\u201330 April 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9056, pp. 203\u2013228. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-662-46800-5_9.","DOI":"10.1007\/978-3-662-46800-5_9"},{"key":"1545_CR28","doi-asserted-by":"publisher","unstructured":"Micciancio D., Voulgaris P.: Faster exponential time algorithms for the shortest vector problem. In: Charikar M. (ed.) Proceedings of the Twenty-First Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, 17\u201319 January 2010, pp. 1468\u20131480. SIAM (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.119.","DOI":"10.1137\/1.9781611973075.119"},{"issue":"2","key":"1545_CR29","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1515\/JMC.2008.009","volume":"2","author":"PQ Nguyen","year":"2008","unstructured":"Nguyen P.Q., Vidick T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptol. 2(2), 181\u2013207 (2008). https:\/\/doi.org\/10.1515\/JMC.2008.009.","journal-title":"J. Math. Cryptol."},{"issue":"5","key":"1545_CR30","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). https:\/\/doi.org\/10.1109\/TIT.1962.1057777.","journal-title":"IRE Trans. Inf. Theory"},{"issue":"3","key":"1545_CR31","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R Schroeppel","year":"1981","unstructured":"Schroeppel R., Shamir A.: A T = O(2$$^{\\text{ n\/2 }}$$), S = O(2$$^{\\text{ n\/4 }}$$) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456\u2013464 (1981). https:\/\/doi.org\/10.1137\/0210033.","journal-title":"SIAM J. Comput."},{"key":"1545_CR32","doi-asserted-by":"publisher","unstructured":"Stern J.: A method for finding codewords of small weight. In: Cohen G.D., Wolfmann J. (eds.) Coding Theory and Applications, 3rd International Colloquium, Toulon, France, 2\u20134 November 1988, Proceedings. Lecture Notes in Computer Science, vol. 388, pp. 106\u2013113. Springer (1988). https:\/\/doi.org\/10.1007\/BFb0019850.","DOI":"10.1007\/BFb0019850"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-024-01545-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-024-01545-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-024-01545-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:02:32Z","timestamp":1750305752000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-024-01545-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,2]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["1545"],"URL":"https:\/\/doi.org\/10.1007\/s10623-024-01545-0","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2025,1,2]]},"assertion":[{"value":"30 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}