{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:05:06Z","timestamp":1757311506778,"version":"3.41.2"},"reference-count":43,"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>The Crossbred algorithm is currently the state-of-the-art method for solving overdetermined multivariate polynomial systems over <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:msub>\n                  <mml:mi>\ud835\udd3d<\/mml:mi>\n                  <mml:mn>2<\/mml:mn>\n                <\/mml:msub>\n              <\/mml:mrow>\n            <\/mml:math>. Since its publication in 2017, several record breaking implementations have been proposed and demonstrate the power of this hybrid approach. Despite these practical results, the complexity of this algorithm and the choice of optimal parameters for it are difficult open questions. In this paper, we prove a bivariate generating series for potentially admissible parameters of the Crossbred algorithm. <\/jats:p>","DOI":"10.62056\/ak86cy7qiu","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["An analysis of the Crossbred Algorithm for the MQ Problem"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6311-1047","authenticated-orcid":false,"given":"Damien","family":"Vidal","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/031v4g827","id-type":"ROR","asserted-by":"publisher"}],"name":"Laboratoire MIS, Universit\u00e9 de Picardie Jules Verne","place":["33 rue Saint Leu, Amiens, 80039, France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5314-1806","authenticated-orcid":false,"given":"Claire","family":"Delaplace","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/031v4g827","id-type":"ROR","asserted-by":"publisher"}],"name":"Laboratoire MIS, Universit\u00e9 de Picardie Jules Verne","place":["33 rue Saint Leu, Amiens, 80039, France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4038-454X","authenticated-orcid":false,"given":"Sorina","family":"Ionica","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/031v4g827","id-type":"ROR","asserted-by":"publisher"}],"name":"Laboratoire MIS, Universit\u00e9 de Picardie Jules Verne","place":["33 rue Saint Leu, Amiens, 80039, France"]}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:FRAENKEL197915","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0166-218X(79)90012-X","article-title":"Complexity of problems in games, graphs and algebraic\n  equations","volume":"1","author":"A.S. Fraenkel","year":"1979","journal-title":"Discrete Applied Mathematics"},{"key":"ref2:MI","isbn-type":"print","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/3-540-45961-8_39","article-title":"Public Quadratic Polynomial-Tuples for Efficient\n  Signature-Verification and Message-Encryption","author":"Tsutomu Matsumoto","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540459613"},{"key":"ref3:Patarin95","isbn-type":"print","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-44750-4_20","article-title":"Cryptanalysis of the Matsumoto and Imai Public Key Scheme\n  of Eurocrypt'88","author":"Jacques Patarin","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540447504"},{"key":"ref4:UOV","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/3-540-48910-X_15","article-title":"Unbalanced Oil and Vinegar Signature Schemes","author":"Aviad Kipnis","year":"1999"},{"volume-title":"PROV: PRovable unbalanced Oil and Vinegar","year":"2023","author":"Beno\u00eet Cogliati","key":"ref5:PROV"},{"volume-title":"A Simple Noncommutative UOV Scheme","year":"2022","author":"Lih-Chung Wang","key":"ref6:SNOVA"},{"key":"ref7:LUOV","isbn-type":"print","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-319-71667-1_12","article-title":"Field Lifting for Smaller UOV Public Keys","author":"Ward Beullens","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319716671"},{"key":"ref8:Rainbow","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/11496137_12","article-title":"Rainbow, a New Multivariable Polynomial Signature Scheme","author":"Jintai Ding","year":"2005"},{"volume-title":"MQDSS specifications","year":"2019","author":"Ming-Shing Chen","key":"ref9:MQDSS"},{"volume-title":"GeMSS: a great multivariate short signature","year":"2017","author":"Antoine Casanova","key":"ref10:Gemss"},{"key":"ref11:LUOVattack","first-page":"1071","article-title":"QuantumHammer: A Practical Hybrid Attack on the LUOV\n  Signature Scheme","author":"Koksal Mus","year":"2020"},{"key":"ref12:BeuRainbows","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/978-3-031-15979-4_16","article-title":"Breaking Rainbow Takes a Weekend on a Laptop","volume":"13508","author":"Ward Beullens","year":"2022"},{"key":"ref13:HFEKeyRecovery","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-030-84242-0_4","article-title":"Efficient Key Recovery for All HFE Signature Variants","author":"Chengdong Tao","year":"2021"},{"key":"ref14:MQDSSattack","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-65411-5_1","article-title":"An Attack on Some Signature Schemes Constructed From\n  Five-Pass Identification Schemes","author":"Daniel Kales","year":"2020"},{"volume-title":"TUOV: Triangular Unbalanced Oil and Vinegar","year":"2023","author":"Ding Jintai","key":"ref15:TUOV"},{"volume-title":"Vox Specification v1.0","year":"2023","author":"Beno\u00eet Cogliati","key":"ref16:VOX"},{"volume-title":"QR-UOV","year":"2023","author":"Hiroki Furue","key":"ref17:QR-UOV"},{"key":"ref18:Biscuit","series-title":"Lecture Notes in Computer Science","first-page":"457","article-title":"Biscuit: Shorter MPC-based Signature from PoSSo","volume":"14583","author":"Luk Bettale","year":"2024"},{"key":"ref19:MQOM","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1109\/EuroSP60621.2024.00032","article-title":"MQ on my Mind: Post-Quantum Signatures from the\n  Non-Structured Multivariate Quadratic Problem","author":"Ryad Benadjila","year":"2024","journal-title":"2024 IEEE 9th European Symposium on Security and Privacy\n  (EuroS&P)"},{"key":"ref20:TW12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-642-30057-8_10","article-title":"Solving Underdetermined Systems of Multivariate Quadratic\n  Equations Revisited","author":"Enrico Thomae","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642300578"},{"volume-title":"Ein Algorithmus zum Auffinden der Basiselemente des\n  Restklassenringes nach einem nulldimensionalen Polynomideal","year":"1965","author":"Bruno Buchberger","key":"ref21:Buchberger65"},{"key":"ref22:Faugere99","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  (F4)","volume":"139","author":"Jean-Charles Faug\u00e9re","year":"1999","journal-title":"Journal of Pure and Applied Algebra"},{"key":"ref23:Faugere02","series-title":"ISSAC '02","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/780506.780516","article-title":"A New Efficient Algorithm for Computing Gr\u00f6bner Basis\n  Without Reduction to Zero (F5)","author":"Jean-Charles Faug\u00e8re","year":"2002"},{"key":"ref24:XL","isbn-type":"print","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","article-title":"Efficient Algorithms for Solving Overdefined Systems of\n  Multivariate Polynomial Equations","author":"Nicolas Courtois","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540455394"},{"key":"ref25:FES","isbn-type":"print","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-642-15031-9_14","article-title":"Fast Exhaustive Search for Polynomial Systems in\n  $\\mathbb{F}_2$","author":"Charles Bouillaguet","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642150319"},{"key":"ref26:BooleanSolve","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jco.2012.07.001","article-title":"On the complexity of solving quadratic Boolean systems","volume":"29","author":"Magali Bardet","year":"2013","journal-title":"Journal of Complexity"},{"key":"ref27:Crossbred","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-76620-1_1","article-title":"A Crossbred Algorithm for Solving Boolean Polynomial\n  Systems","volume":"10737","author":"Antoine Joux","year":"2017"},{"key":"ref28:Niederhagen","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-319-79063-3_6","article-title":"Implementing Joux-Vitse's Crossbred Algorithm for Solving\n  MQ Systems over GF(2) on GPUs","volume":"10786","author":"Ruben Niederhagen","year":"2018"},{"year":"2017","author":"Ruben Niederhagen","key":"ref29:mqsolver"},{"volume-title":"High-Performance Xbred","year":"2023","author":"Charles Bouillaguet","key":"ref30:Xbred"},{"volume-title":"Fukuoka MQ Challenge","year":"2015","author":"Takanori Yasuda","key":"ref31:mq-challenge-online"},{"volume-title":"Etude des syst\u00e8mes alg\u00e9briques surd\u00e9termin\u00e9s.\n  Applications aux codes correcteurs et \u00e0 la cryptographie","year":"2004","author":"Magali Bardet","key":"ref32:Bardet"},{"volume-title":"On the Complexity and Admissible Parameters of the\n  Crossbred Algorithm in $\\mathbb{F}_{q\\geq2}$","year":"2023","author":"Jo\u00e3o Diogo Duarte","key":"ref33:Duarte"},{"volume-title":"Admissible Parameter Sets and Complexity Estimation of\n  Crossbred Algorithm","year":"2024","author":"Shuhei Nakamura","key":"ref34:Nakamura"},{"volume-title":"Admissible Parameters for the Crossbred Algorithm and\n  Semi-regular Sequences over Finite Fields","year":"2024","author":"John Baena","key":"ref35:Verbel"},{"key":"ref36:Lazard","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/3-540-12868-9_99","article-title":"Gr\u00f6bner bases, Gaussian elimination and resolution of\n  systems of algebraic equations","volume":"162","author":"Daniel Lazard","year":"1983"},{"key":"ref37:Cox","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16721-3","volume-title":"Ideals, Varieties and Algorithms","author":"David A. Cox","year":"1997"},{"volume-title":"The solving degrees for computing Gr\u00f6bner bases of affine\n  semi-regular polynomial sequences","year":"2024","author":"Momonari Kudo","key":"ref38:Kudo"},{"key":"ref39:Tsakou","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77700-5_3","article-title":"Semi-regular sequences and other random systems of\n  equations","author":"Mina Bigdeli","year":"2022"},{"key":"ref40:BMSV22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-031-17433-9_14","article-title":"An Estimator for the Hardness of the MQ Problem","author":"Emanuele Bellini","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031174339"},{"volume-title":"mq-comparaison-suite","year":"2022","author":"Vladim\u00edr Sedl\u00e1\u010dek","key":"ref41:mq-comparaison-suite"},{"volume-title":"MQ Challenge: Hardness Evaluation of Solving Multivariate\n  Quadratic Problems","year":"2015","author":"Takanori Yasuda","key":"ref42:MQ_Challenge"},{"volume-title":"Complexity of Gr\u00f6bner basis computation for\n  semi-regular overdetermined sequences over $\\F_2$ with solutions in $\\F_2$","year":"2003","author":"Magali Bardet","key":"ref43:GrobnerBasisComplexity"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:37Z","timestamp":1733866117000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":43,"URL":"https:\/\/doi.org\/10.62056\/ak86cy7qiu","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"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-103"}}