{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T12:50:12Z","timestamp":1763988612825,"version":"3.41.2"},"reference-count":26,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T00:00:00Z","timestamp":1736726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE39-0002"],"award-info":[{"award-number":["ANR-20-CE39-0002"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,3,11]]},"abstract":"<jats:p>  In 2015, May and Ozerov proposed a new method to solve the Nearest Neighbor   Problem. They also observed that it could be used as a subroutine in various   Information Set Decoding (ISD) algorithms for arbitrary linear codes. This led to an   asymptotic improvement in their complexity. However, the proposed improvement   has been widely perceived as impractical because of the huge hidden factors in   its asymptotic complexity. The main contribution of this article is to provide   a sound foundation for this claim. We show that it is indeed \u201cgalactic\u201d,   namely that it only improves upon much simpler methods when instances are so   large that they fill the whole universe.<\/jats:p>\n          <jats:p>  More precisely, we argue that for the May-Ozerov ISD algorithm to require less   operations than a technique based on the Stern ISD algorithm, the length of   the code has to be greater than 1,874,400 with a number of   operation beyond 2 to the power 63489, making it practically useless. <\/jats:p>","DOI":"10.62056\/akjbksuc2","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:23:17Z","timestamp":1744147397000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["The May-Ozerov Algorithm for Syndrome Decoding is \u201cGalactic\u201d"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9416-6244","authenticated-orcid":false,"given":"Charles","family":"Bouillaguet","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05krcen59","id-type":"ROR","asserted-by":"publisher"}],"name":"Sorbonne Universit\u00e9, CNRS, LIP6","place":["Paris, F-75005, France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5314-1806","authenticated-orcid":false,"given":"Claire","family":"Delaplace","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05w9qrp28","id-type":"ROR","asserted-by":"publisher"}],"name":"Laboratoire MIS, Universit\u00e9 de Picardie Jules Verne","place":["Amiens, France"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0597-6221","authenticated-orcid":false,"given":"Micka\u00ebl","family":"Hamdad","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05krcen59","id-type":"ROR","asserted-by":"publisher"}],"name":"Sorbonne Universit\u00e9, CNRS, LIP6","place":["Paris, F-75005, France"]},{"id":[{"id":"https:\/\/ror.org\/05w9qrp28","id-type":"ROR","asserted-by":"publisher"}],"name":"Laboratoire MIS, Universit\u00e9 de Picardie Jules Verne","place":["Amiens, France"]}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:Lipton13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-41422-0_20","article-title":"David Johnson: Galactic Algorithms","author":"Richard J. Lipton","year":"2013"},{"key":"ref2:COPPERSMITH1990251","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Don Coppersmith","year":"1990","journal-title":"Journal of Symbolic Computation","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"electronic"},{"key":"ref3:McEliece78","first-page":"114","article-title":"A Public-Key Cryptosystem Based On Algebraic Coding\n  Theory","volume":"44","author":"Robert J. McEliece","year":"1978","journal-title":"Deep Space Network Progress Report"},{"key":"ref4:BMT1978","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems\n  (Corresp.)","volume":"24","author":"Elwyn Berlekamp","year":"1978","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref5:LeeB88","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/3-540-45961-8_25","article-title":"An Observation on the Security of McEliece's Public-Key\n  Cryptosystem","volume":"330","author":"Pil Joong Lee","year":"1988"},{"key":"ref6:Stern88","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFb0019850","article-title":"A method for finding codewords of small weight","volume":"388","author":"Jacques Stern","year":"1988"},{"key":"ref7:BernsteinLP11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/978-3-642-22792-9_42","article-title":"Smaller Decoding Exponents: Ball-Collision Decoding","volume":"6841","author":"Daniel J. Bernstein","year":"2011"},{"key":"ref8:MayMT11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-25385-0_6","article-title":"Decoding Random Linear Codes in $\\widetilde{O}\\left(2^{0.054\n  n}\\right)$","volume":"7073","author":"Alexander May","year":"2011"},{"key":"ref9:BeckerJMM12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-29011-4_31","article-title":"Decoding Random Binary Linear Codes in $2^{n\/20}$: How $1 +\n  1 = 0$ Improves Information Set Decoding","volume":"7237","author":"Anja Becker","year":"2012"},{"key":"ref10:MO2015","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-662-46800-5_9","article-title":"On Computing Nearest Neighbors with Applications to Decoding\n  of Binary Linear Codes","volume":"9056","author":"Alexander May","year":"2015"},{"key":"ref11:BernsteinLP08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-88403-3_3","article-title":"Attacking and Defending the McEliece Cryptosystem","volume":"5299","author":"Daniel J. Bernstein","year":"2008"},{"key":"ref12:EsserMZ22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-031-07082-2_16","article-title":"McEliece Needs a Break - Solving McEliece-1284 and\n  Quasi-Cyclic-2918 with Modern ISD","volume":"13277","author":"Andre Esser","year":"2022"},{"key":"ref13:NUOFAF24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-75764-8_1","article-title":"Solving McEliece-1409 in One Day - Cryptanalysis with the\n  Improved BJMM Algorithm","volume":"15258","author":"Shintaro Narisada","year":"2024"},{"key":"ref14:IndykM98","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1145\/276698.276876","article-title":"Approximate Nearest Neighbors: Towards Removing the Curse of\n  Dimensionality","author":"Piotr Indyk","year":"1998"},{"key":"ref15:Esser022","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-030-97121-2_5","article-title":"Syndrome Decoding Estimator","volume":"13177","author":"Andre Esser","year":"2022"},{"key":"ref16:KarpWZ95","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1109\/SFCS.1995.492663","article-title":"The Bit Vector Intersection Problem (Preliminary Version)","author":"Richard M. Karp","year":"1995"},{"key":"ref17:Rivest74","first-page":"678","article-title":"On the Optimality of Elia's Algorithm for Performing\n  Best-Match Searches","author":"Ronald L. Rivest","year":"1974"},{"volume-title":"Bounds on information retrieval efficiency in static file\n  structures","year":"1971","author":"Terry A. Welch","key":"ref18:welch1971"},{"key":"ref19:dubiner2010","doi-asserted-by":"publisher","first-page":"4166","DOI":"10.1109\/TIT.2010.2050814","article-title":"Bucketing coding and information theory for the statistical\n  high-dimensional nearest-neighbor problem","volume":"56","author":"Moshe Dubiner","year":"2010","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref20:Topsoe2001","article-title":"Bounds for entropy and divergence for distributions over a\n  two-element set.","volume":"2","author":"Flemming Tops\u00f8e","year":"2001","journal-title":"JIPAM. Journal of Inequalities in Pure and Applied\n  Mathematics"},{"volume-title":"Classic McEliece","year":"2017","author":"Daniel J. Bernstein","key":"ref21:NistMcEliece"},{"key":"ref22:DBLP:conf\/crypto\/Stern93","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-48329-2_2","article-title":"A New Identification Scheme Based on Syndrome Decoding","volume":"773","author":"Jacques Stern","year":"1993"},{"key":"ref23:DBLP:conf\/eurocrypt\/FischerS96","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/3-540-68339-9_22","article-title":"An Efficient Pseudo-Random Generator Provably as Secure as\n  Syndrome Decoding","volume":"1070","author":"Jean-Bernard Fischer","year":"1996"},{"key":"ref24:DBLP:conf\/mycrypt\/AugotFS05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/11554868_6","article-title":"A Family of Fast Syndrome Based Cryptographic Hash\n  Functions","volume":"3715","author":"Daniel Augot","year":"2005"},{"key":"ref25:DBLP:conf\/crypto\/FeneuilJR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/978-3-031-15979-4_19","article-title":"Syndrome Decoding in the Head: Shorter Signatures from\n  Zero-Knowledge Proofs","volume":"13508","author":"Thibauld Feneuil","year":"2022"},{"volume-title":"The Syndrome Decoding in the Head (SD-in-the-Head) Signature\n  Scheme","year":"2023","author":"Carlos Aguilar Melchor","key":"ref26:NistSDitH"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:25:10Z","timestamp":1744147510000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/akjbksuc2","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2025-01-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-1-53"}}