{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:56:31Z","timestamp":1767930991631,"version":"3.49.0"},"reference-count":27,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:00:00Z","timestamp":1759881600000},"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":[[2025,12,2]]},"abstract":"<jats:p>The Linear Code Equivalence (LCE) problem and the Matrix Code Equivalence (MCE) problem are two examples of code-based hard problems that have gained attention as candidates for use in post-quantum cryptography. They are straightforward to implement, can be viewed as group actions, and offer a good trade-off between compactness and performance in the realm of post-quantum group actions.<\/jats:p>\n                  <jats:p>With the community gaining confidence in the security of these problems, new variants of these problems have been introduced to achieve particular functionalities in advanced protocols or efficiency improvements. A natural question is then whether the problem variants are as secure as the original ones.<\/jats:p>\n                  <jats:p>In this work, we consider three problem variants of LCE or MCE. We first consider a variant based on LCE, and reduce it to the original LCE assumption. This problem was presented in a prior version of the blind signature scheme, proposed by Duong, Khuc, Qiao, Susilo and Zhang. Second, we analyse an MCE variant, MIMCE, proposed in the context of another blind signature scheme, by Kutcha, Legrow and Persichetti, and show that the parameters proposed are not sufficient to reach the claimed bit security. Finally, we consider a multi-sample version of MIMCE which we solve in polynomial time.<\/jats:p>","DOI":"10.62056\/aesg893y6","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:39:47Z","timestamp":1767915587000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["On the security of two blind signatures from code equivalence problems"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-0159-6495","authenticated-orcid":false,"given":"Valerie","family":"Gilchrist","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01r9htc13","id-type":"ROR","asserted-by":"publisher"}],"name":"Universit\u00e9 Libre de Bruxelles","place":["Belgium"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5693-210X","authenticated-orcid":false,"given":"Laurane","family":"Marco","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02s376052","id-type":"ROR","asserted-by":"publisher"}],"name":"EPFL","place":["Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3482-6743","authenticated-orcid":false,"given":"Christophe","family":"Petit","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01r9htc13","id-type":"ROR","asserted-by":"publisher"}],"name":"Universit\u00e9 Libre de Bruxelles","place":["Belgium"]},{"id":[{"id":"https:\/\/ror.org\/03angcq70","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Birmingham","place":["United Kingdom"]}]},{"given":"Gang","family":"Tang","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03angcq70","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Birmingham","place":["United Kingdom"]}]}],"member":"48349","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"ref1:multi-sigs","isbn-type":"print","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-031-91823-0_4","article-title":"A Framework for Group Action-Based Multi-signatures and\n  Applications to LESS, MEDS, and ALTEQ","author":"Giuseppe D'Alconzo","year":"2025","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031918230"},{"key":"ref2:AC:DAlFlaGan23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-981-99-8739-9_8","article-title":"Non-interactive Commitment from Non-transitive Group\n  Actions","volume":"14444","author":"Giuseppe D'Alconzo","year":"2023"},{"key":"ref3:JWLLGPW25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-031-91124-8_5","article-title":"Re-randomize and Extract: A Novel Commitment Construction\n  Framework Based on Group Actions","volume":"15602","author":"Kaijie Jiang","year":"2025"},{"key":"ref4:cutting-the-grass","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/978-3-031-58868-6_18","article-title":"Cutting the GRASS: Threshold GRoup Action Signature\n  Schemes","volume":"14643","author":"Michele Battagliola","year":"2024"},{"key":"ref5:PQCRYPTO:BBDMP25","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-031-86599-2_5","article-title":"Enhancing Threshold Group Action Signature Schemes: Adaptive\n  Security and Scalability Improvements","author":"Michele Battagliola","year":"2025"},{"key":"ref6:EPRINT:DKQSZ25","volume-title":"Blind Signatures from Cryptographic Group Actions","author":"Dung Hoang Duong","year":"2025"},{"key":"ref7:PQCRYPTO:SenSim13","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-642-38616-9_14","article-title":"The Hardness of Code Equivalence over and Its Application to\n  Code-Based Cryptography","author":"Nicolas Sendrier","year":"2013"},{"key":"ref8:AFRICACRYPT:BMPS20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-030-51938-4_3","article-title":"LESS is More: Code-Based Signatures Without Syndromes","volume":"12174","author":"Jean-Fran\u00e7ois Biasse","year":"2020"},{"key":"ref9:AFRICACRYPT:CNPRRS23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-031-37679-5_2","article-title":"Take Your MEDS: Digital Signatures from Matrix Code\n  Equivalence","volume":"14064","author":"Tung Chou","year":"2023"},{"key":"ref10:C:GMPT24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-031-68376-3_5","article-title":"Solving the Tensor Isomorphism Problem for Special Orbits\n  with Low Rank Points: Cryptanalysis and Repair of an Asiacrypt 2023\n  Commitment Scheme","volume":"14920","author":"Valerie Gilchrist","year":"2024"},{"key":"ref11:AC:BCDSK24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-981-96-0944-4_2","article-title":"Don't Use it Twice! Solving Relaxed Linear Equivalence\n  Problems","volume":"15491","author":"Alessandro Budroni","year":"2024"},{"key":"ref12:EPRINT:KuLePe25","volume-title":"Post-Quantum Blind Signatures from Matrix Code Equivalence","author":"Veronika Kuchta","year":"2025"},{"key":"ref13:code-hardness","doi-asserted-by":"publisher","first-page":"23","DOI":"10.3934\/amc.2022064","article-title":"On the computational hardness of the code equivalence\n  problem in cryptography","volume":"17","author":"Alessandro Barenghi","year":"2023","journal-title":"Advances in Mathematics of Communications","ISSN":"https:\/\/id.crossref.org\/issn\/1930-5346","issn-type":"electronic"},{"key":"ref14:meds-spec","volume-title":"Matrix Equivalence Digital Signature","author":"Tung Chou","year":"2023"},{"key":"ref15:barenghi2022advanced","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1080\/23799927.2022.2048206","article-title":"Advanced signature functionalities from the code equivalence\n  problem","volume":"7","author":"Alessandro Barenghi","year":"2022","journal-title":"International Journal of Computer Mathematics: Computer\n  Systems Theory"},{"key":"ref16:jesus","volume-title":"Weak Instances of the Inverse Matrix Code Equivalence\n  Problem","author":"Jes\u00fas-Javier Chi-Dom\u00ednguez","year":"2025"},{"key":"ref17:square_roots_matrices","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1016\/j.jco.2015.04.001","article-title":"Polynomial-time algorithms for quadratic isomorphism of\n  polynomials","volume":"31","author":"J\u00e9r\u00e9my Berthomieu","year":"2015","journal-title":"J. Complex.","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"electronic"},{"key":"ref18:rigidcodes","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10623-023-01338-x","article-title":"Hardness estimates of the code equivalence problem in the\n  rank metric","volume":"92","author":"Krijn Reijnders","year":"2024","journal-title":"Designs, Codes and Cryptography"},{"key":"ref19:solving-degree","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2112.05579","volume-title":"Solving degree, last fall degree, and related invariants","author":"Alessio Caminata","year":"2021"},{"key":"ref20:EPRINT:PerSmi20","volume-title":"Rainbow Band Separation is Better than we Thought","author":"Ray Perlner","year":"2020"},{"key":"ref21:NIW20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.TCS.2021.09.043","volume-title":"New complexity estimation on the Rainbow-Band-Separation\n  attack","volume":"896","author":"Shuhei Nakamura","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref22:alteq-alg-attack","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-031-46495-9_5","article-title":"Algebraic Algorithm for the Alternating Trilinear Form\n  Equivalence Problem","volume":"14311","author":"Lars Ran","year":"2023"},{"key":"ref23:BeWi2025","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/S10623-024-01542-3","article-title":"Relating code equivalence to other isomorphism problems","volume":"93","author":"Huck Bennett","year":"2025","journal-title":"Des. Codes Cryptogr."},{"key":"ref24:Fulman_2015","doi-asserted-by":"publisher","DOI":"10.1214\/13-aop889","article-title":"Stein\u2019s method and the rank distribution of random\n  matrices over finite fields","volume":"43","author":"Jason Fulman","year":"2015","journal-title":"The Annals of Probability","ISSN":"https:\/\/id.crossref.org\/issn\/0091-1798","issn-type":"electronic"},{"key":"ref25: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":"Journal of Symbolic Computation"},{"key":"ref26:curtis","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1136-5","volume-title":"Linear Algebra - An Introductory Approach","author":"Charles W. Curtis","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387909929"},{"key":"ref27:neumann1995cyclic","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1112\/jlms\/52.2.263","article-title":"Cyclic matrices over finite fields","volume":"52","author":"Peter M Neumann","year":"1995","journal-title":"Journal of the London Mathematical Society"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:40:21Z","timestamp":1767915621000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/4\/27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":27,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,1,8]]}},"URL":"https:\/\/doi.org\/10.62056\/aesg893y6","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-10-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-4-57"}}