{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T18:24:33Z","timestamp":1785435873010,"version":"3.56.0"},"reference-count":22,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>\n                    Restricted syndrome decoding problems (R-SDP and R-SDP(\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    )) provide an interesting basis for post-quantum cryptography. Indeed, they feature in CROSS, a submission in the ongoing process for standardizing post-quantum signatures.\n                  <\/jats:p>\n                  <jats:p>\n                    This work improves our understanding of the security of both problems. Firstly, we propose and implement a novel collision attack on R-SDP(\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    ) that provides the best attack under realistic restrictions on memory. Secondly, we derive precise complexity estimates for algebraic attacks on R-SDP that are shown to be accurate by our experiments. We note that neither of these improvements threatens the updated parameters of CROSS.\n                  <\/jats:p>","DOI":"10.62056\/a06cy7qiu","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T11:13:33Z","timestamp":1728299613000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["A Security Analysis of Restricted Syndrome Decoding Problems"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0888-283X","authenticated-orcid":false,"given":"Ward","family":"Beullens","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02js37d36","id-type":"ROR","asserted-by":"publisher"}],"name":"IBM Research Europe","place":["Z\u00fcrich, Switzerland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0191-3181","authenticated-orcid":false,"given":"Pierre","family":"Briaud","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05kmggt55","id-type":"ROR","asserted-by":"publisher"}],"name":"Simula UiB","place":["Bergen, Norway"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1783-1700","authenticated-orcid":false,"given":"Morten","family":"\u00d8ygarden","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05kmggt55","id-type":"ROR","asserted-by":"publisher"}],"name":"Simula UiB","place":["Bergen, Norway"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:NIST1","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.IR.8413","volume-title":"Status report on the third round of the NIST post-quantum\n  cryptography standardization process","author":"Gorjan Alagic","year":"2022"},{"key":"ref2:RSDP1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2008.06403","article-title":"A New Path to Code-based Signatures via Identification\n  Schemes with Restricted Errors","author":"Marco Baldi","year":"2020","journal-title":"CoRR"},{"key":"ref3:RSDP2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-031-57722-2_8","article-title":"Zero Knowledge Protocols and Signatures from the Restricted\n  Syndrome Decoding Problem","author":"Marco Baldi","year":"2024"},{"key":"ref4:CROSS1","volume-title":"CROSS: Codes and Restricted Objects Signature Scheme","author":"Marco Baldi","year":"2023"},{"key":"ref5:pcg","isbn-type":"print","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/978-3-031-30589-4_14","article-title":"A New Algebraic Approach to the Regular Syndrome Decoding\n  Problem and Implications for PCG Constructions","author":"Pierre Briaud","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031305894"},{"key":"ref6:dumer","first-page":"50","article-title":"On minimum distance decoding of linear codes","author":"Ilya Dumer","year":"1991"},{"key":"ref7:stern","isbn-type":"print","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFb0019850","article-title":"A method for finding codewords of small weight","author":"Jacques Stern","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540467267"},{"key":"ref8:artin","volume-title":"Algebra","author":"Michael Artin","year":"2010"},{"key":"ref9:vOW","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","article-title":"Parallel collision search with cryptanalytic\n  applications","volume":"12","author":"Paul C. van Oorschot","year":"1999","journal-title":"Journal of Cryptology"},{"key":"ref10:IdealVarietiesAlgorithms","volume-title":"Ideals, Varieties, and Algorithms: an Introduction to\n  Computational Algebraic Geometry and Commutative Algebra","author":"David Cox","year":"2013"},{"key":"ref11:F5","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/780506.780516","article-title":"A new efficient algorithm for computing Gr\u00f6bner bases\n  without reduction to zero (F$_5$)","author":"Jean-Charles Faug\u00e8re","year":"2002"},{"key":"ref12:magma","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Wieb Bosma","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"electronic"},{"key":"ref13:bardet_these","volume-title":"\u00c9tude des syst\u00e8mes alg\u00e9briques\n  surd\u00e9termin\u00e9s. Applications aux codes correcteurs et \u00e0 la\n  cryptographie","author":"Magali Bardet","year":"2004"},{"key":"ref14:rocco","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-99-8730-6_1","article-title":"A new approach based on quadratic forms to attack the\n  McEliece cryptosystem","author":"Alain Couvreur","year":"2023"},{"key":"ref15:F4","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","article-title":"A new efficient algorithm for computing Gr\u00f6bner bases\n  (F$_4$)","volume":"139","author":"Jean-Charles Faug\u00e8re","year":"1999","journal-title":"Journal of pure and applied algebra"},{"key":"ref16:CaminataGorla","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.jsc.2022.05.001","article-title":"Solving degree, last fall degree, and related invariants","volume":"114","author":"Alessio Caminata","year":"2023","journal-title":"Journal of Symbolic Computation"},{"key":"ref17:bettale_these","volume-title":"Cryptanalyse alg\u00e9brique : outils et applications","author":"Luk Bettale","year":"2012"},{"key":"ref18:BFS","first-page":"1","article-title":"Asymptotic Behaviour of the Index of Regularity of\n  Semi-Regular Quadratic Polynomial Systems","author":"Magali Bardet","year":"2005"},{"key":"ref19:hybrid","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1515\/JMC.2009.009","article-title":"Hybrid approach for solving multivariate systems over\n  finite fields","volume":"3","author":"Luk Bettale","year":"2009","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref20:biscuit_cryp","doi-asserted-by":"publisher","DOI":"10.62056\/aemp-4c2h","article-title":"Preliminary Cryptanalysis of the Biscuit Signature\n  Scheme","author":"Charles Bouillaguet","year":"2024","journal-title":"IACR Communications in Cryptology"},{"key":"ref21:CVE","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-19574-7_12","article-title":"A Zero-Knowledge Identification Scheme Based on the q-ary\n  Syndrome Decoding Problem","author":"Pierre-Louis Cayrel","year":"2010"},{"key":"ref22:FiatShamir","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","article-title":"How to Prove Yourself: Practical Solutions to\n  Identification and Signature Problems","author":"Amos Fiat","year":"1986"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T16:28:34Z","timestamp":1733848114000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":22,"URL":"https:\/\/doi.org\/10.62056\/a06cy7qiu","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-94"}}