{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T09:44:30Z","timestamp":1766223870460,"version":"3.48.0"},"reference-count":21,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,4,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>MinRank is an NP-complete problem in linear algebra whose characteristics make it attractive to build post-quantum cryptographic primitives. Several MinRank-based digital signature schemes have been proposed. In particular, two of them, MIRA and MiRitH, have been submitted to the NIST post-quantum cryptography standardization process. In this article, we propose a key-generation algorithm for MinRank-based schemes that reduces the size of the public key to about 50% of the size of the public key generated by the previous best (in terms of public-key size) algorithm. Precisely, the size of the public key generated by our algorithm sits in the range of 328\u2013676 bits for security levels of 128\u2013256 bits. We also prove that our algorithm is as secure as the previous ones.<\/jats:p>","DOI":"10.1515\/jmc-2024-0008","type":"journal-article","created":{"date-parts":[[2025,4,14]],"date-time":"2025-04-14T09:57:50Z","timestamp":1744624670000},"source":"Crossref","is-referenced-by-count":0,"title":["Smaller public keys for MinRank-based schemes"],"prefix":"10.1515","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0758-7062","authenticated-orcid":false,"given":"Antonio J.","family":"Di Scala","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Politecnico di Torino, Corso Duca degli Abruzzi 24 , Torino , 10129 , Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2111-7596","authenticated-orcid":false,"given":"Carlo","family":"Sanna","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Politecnico di Torino, Corso Duca degli Abruzzi 24 , Torino , 10129 , Italy"}]}],"member":"374","published-online":{"date-parts":[[2025,4,14]]},"reference":[{"key":"2025122009205586628_j_jmc-2024-0008_ref_001","doi-asserted-by":"crossref","unstructured":"Buss JF, Frandsen GS, Shallit JO. The computational complexity of some problems of linear algebra. J. Comput. System Sci. 1999;58(3):572\u201396.","DOI":"10.1006\/jcss.1998.1608"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_002","doi-asserted-by":"crossref","unstructured":"Beullens W. Improved cryptanalysis of UOV and Rainbow. In: Advances in cryptology-EUROCRYPT 2021. Part I, volume 12696 of Lecture Notes in Comput. Sci., Cham: Springer; 2021. p. 348\u201373.","DOI":"10.1007\/978-3-030-77870-5_13"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_003","doi-asserted-by":"crossref","unstructured":"Gaborit P, Ruatta O, Schrek J. On the complexity of the rank syndrome decoding problem. IEEE Trans. Inform. Theory, 2016;62(2):1006\u201319.","DOI":"10.1109\/TIT.2015.2511786"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_004","doi-asserted-by":"crossref","unstructured":"Tao C, Petzoldt A, Ding J. Efficient key recovery for all HFE signature variants. In: Advances in cryptology-CRYPTO 2021. Part I, volume 12825 of Lecture Notes in Comput. Sci., Cham: Springer; 2021. p. 70\u201393.","DOI":"10.1007\/978-3-030-84242-0_4"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_005","doi-asserted-by":"crossref","unstructured":"Bardet M, Bertin M. Improvement of algebraic attacks for solving superdetermined MinRank instances. Lecture Notes Comput Sci. 2022;13512:107\u201323.","DOI":"10.1007\/978-3-031-17234-2_6"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_006","unstructured":"Bardet M, Briaud P, Bros M, Gaborit P, Tillich J-P. Revisiting algebraic attacks on MinRank and on the rank decoding problem. Cryptology ePrint Archive, Paper 2022\/1031, 2022. https:\/\/eprint.iacr.org\/2022\/1031."},{"key":"2025122009205586628_j_jmc-2024-0008_ref_007","doi-asserted-by":"crossref","unstructured":"Bardet M, Bros M, Cabarcas D, Gaborit P, Perlner R, Smith-Tone D, et al. Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In: Advances in cryptology-ASIACRYPT 2020. Part I, volume 12491 of Lecture Notes in Comput. Sci., Cham: Springer; 2020. p. 507\u201336.","DOI":"10.1007\/978-3-030-64837-4_17"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_008","doi-asserted-by":"crossref","unstructured":"Bettale L, Faug\u00e8re J-C, Perret L. Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des. Codes Cryptogr. 2013;69(1):1\u201352.","DOI":"10.1007\/s10623-012-9617-2"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_009","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J-C, Levy-dit Vehel F, Perret L. Cryptanalysis of MinRank. In: Advances in cryptology-CRYPTO 2008, volume 5157 of Lecture Notes in Comput. Sci., Berlin: Springer; 2008. p. 280\u201396.","DOI":"10.1007\/978-3-540-85174-5_16"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_010","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J-C, Safey El Din M, Spaenlehauer P-J. Computing loci of rank defects of linear matrices using Gr\u00f6bner bases and applications to cryptology. In: ISSAC 2010-Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, New York: ACM; 2010. p. 257\u201364.","DOI":"10.1145\/1837934.1837984"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_011","doi-asserted-by":"crossref","unstructured":"Kipnis A, Shamir A. Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Advances in cryptology-CRYPTO \u201999 (Santa Barbara, CA), volume 1666 of Lecture Notes in Comput. Sci., Berlin: Springer; 1999. p. 19\u201330.","DOI":"10.1007\/3-540-48405-1_2"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_012","doi-asserted-by":"crossref","unstructured":"Verbel J, Baena J, Cabarcas D, Perlner R, Smith-Tone D. On the complexity of \u201csuperdetermined\u201d MinRank instances. In: Post-quantum cryptography, volume 11505 of Lecture Notes in Comput. Sci., Cham: Springer; 2019. p. 167\u201386.","DOI":"10.1007\/978-3-030-25510-7_10"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_013","doi-asserted-by":"crossref","unstructured":"Courtois NT. Efficient zero-knowledge authentication based on a linear algebra problem MinRank. In: Advances in cryptology-ASIACRYPT 2001 (Gold Coast), volume 2248 of Lecture Notes in Comput. Sci., Berlin: Springer; 2001. p. 402\u201321.","DOI":"10.1007\/3-540-45682-1_24"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_014","doi-asserted-by":"crossref","unstructured":"Bellini E, Esser A, Sanna C, Verbel J. M-DSS-Smaller MinRank-based (ring-)signatures. In: Post-quantum cryptography, volume 13512 of Lecture Notes in Comput. Sci., Cham: Springer; 2022. p. 144\u201369.","DOI":"10.1007\/978-3-031-17234-2_8"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_015","unstructured":"Aragon N, Bidoux L, Chi-Dom\u00ednguez J-J, Feneuil T, Gaborit P, Neveu R, et al. MIRA: a Digital Signature Scheme based on the MinRank problem and the MPC-in-the-Head paradigm. 2023. https:\/\/arxiv.org\/abs\/2307.08575."},{"key":"2025122009205586628_j_jmc-2024-0008_ref_016","unstructured":"Feneuil T. Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP. Cryptology ePrint Archive, Paper 2022\/1512, 2022. https:\/\/eprint.iacr.org\/2022\/1512."},{"key":"2025122009205586628_j_jmc-2024-0008_ref_017","unstructured":"Adj G, Barbero S, Bellini E, Esser A, Rivera-Zamarripa L, Sanna C, et al. MiRitH: MinRank in the Head. Submission to NIST, 2023. https:\/\/csrc.nist.gov\/csrc\/media\/Projects\/pqc-dig-sig\/documents\/round-1\/spec-files\/MiRitH_spec-web.pdf. see also https:\/\/pqc-mirith.org."},{"key":"2025122009205586628_j_jmc-2024-0008_ref_018","doi-asserted-by":"crossref","unstructured":"Adj G, Rivera-Zamarripa L, Verbel J. MinRank in the head. In: El Mrabet N, De Feo L, Duquesne S, editors, Progress in Cryptology - AFRICACRYPT 2023, Cham: Springer Nature Switzerland; 2023. p. 3\u201327.","DOI":"10.1007\/978-3-031-37679-5_1"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_019","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J-C, Safey El Din M, Spaenlehauer P-J. On the complexity of the generalized MinRank problem. J Symbolic Comput. 2013;55:30\u201358.","DOI":"10.1016\/j.jsc.2013.03.004"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_020","doi-asserted-by":"crossref","unstructured":"Bernstein DJ, Chou T, Schwabe P. McBits: fast constant-time code-based cryptography. In: Bertoni G, Coron J-S, editors, Cryptographic Hardware and Embedded Systems - CHES 2013, Berlin, Heidelberg: Springer; 2013. p. 250\u201372.","DOI":"10.1007\/978-3-642-40349-1_15"},{"key":"2025122009205586628_j_jmc-2024-0008_ref_021","doi-asserted-by":"crossref","unstructured":"Fisher SD, Alexander MN. Classroom notes: matrices over a finite field. Amer Math Monthly. 1966;73(6):639\u201341.","DOI":"10.2307\/2314805"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0008\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0008\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T09:40:02Z","timestamp":1766223602000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0008\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,1]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,14]]},"published-print":{"date-parts":[[2025,4,14]]}},"alternative-id":["10.1515\/jmc-2024-0008"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2024-0008","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2025,1,1]]},"article-number":"20240008"}}