An analysis of the Crossbred Algorithm for the MQ Problem
Authors
Damien Vidal, Claire Delaplace, Sorina Ionica
Damien Vidal
Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France
damien dot vidal at u-picardie dot fr
damien dot vidal at u-picardie dot fr
Claire Delaplace
Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France
claire dot delaplace at u-picardie dot fr
claire dot delaplace at u-picardie dot fr
Sorina Ionica
Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France
sorina dot ionica at u-picardie dot fr
sorina dot ionica at u-picardie dot fr
Abstract
The Crossbred algorithm is currently the state-of-the-art method for solving overdetermined multivariate polynomial systems over $\mathbb{F}_2$. 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.
References
[Bar04]
Magali Bardet. Etude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. PhD thesis, Université Paris 6, 2004.
[BCC+10]
Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang. Fast Exhaustive Search for Polynomial Systems in $\mathbb{F}_2$. In Cryptographic Hardware and Embedded Systems, CHES 2010, pages 203–218. 2010. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-642-15031-9_14
[BCT+24]
John Baena, Daniel Cabarcas, Sharwan K. Tiwari, Javier Verbel, and Luis Villota. Admissible Parameters for the Crossbred Algorithm and Semi-regular Sequences over Finite Fields. https://eprint.iacr.org/2024/758. 2024.
[Beu22]
Ward Beullens. Breaking Rainbow Takes a Weekend on a Laptop. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, Proceedings, Part II, volume 13508 of Lecture Notes in Computer Science, pages 464–479. 2022. Springer. DOI: https://doi.org/10.1007/978-3-031-15979-4_16
[BFR24]
Ryad Benadjila, Thibauld Feneuil, and Matthieu Rivain. MQ on my Mind: Post-Quantum Signatures from the Non-Structured Multivariate Quadratic Problem. 2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P), 2024. DOI: https://doi.ieeecomputersociety.org/10.1109/EuroSP60621.2024.00032
[BFS03]
Magali Bardet, Jean-Charles Faugère, and Bruno Salvy. Complexity of Gröbner basis computation for semi-regular overdetermined sequences over $\F_2$ with solutions in $\F_2$. Technical report number RR-5049, INRIA. 2003.
[BFSS13]
Magali Bardet, Jean-Charles Faugère, Bruno Salvy, and Pierre-Jean Spaenlehauer. On the complexity of solving quadratic Boolean systems. Journal of Complexity, 29(1):53-75, 2013. DOI: https://doi.org/10.1016/j.jco.2012.07.001
[BMSV22]
Emanuele Bellini, Rusydi H. Makarim, Carlo Sanna, and Javier Verbel. An Estimator for the Hardness of the MQ Problem. In Lejla Batina and Joan Daemen, editors, Progress in Cryptology - AFRICACRYPT 2022, pages 323–347. 2022. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-17433-9_14
[BND+22]
Mina Bigdeli, Emanuela De Negri, Manuela M. Dizdarevic, Romy Minko, and Sulamithe Tsakou. Semi-regular sequences and other random systems of equations. In Sorina Ionica Alina Cojocaru and Elisa Lorenzo Garcia, editors, Women in Numbers Europe III: Research Directions in Number Theory. 2022. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-030-77700-5_3
[BP17]
Ward Beullens and Bart Preneel. Field Lifting for Smaller UOV Public Keys. In Arpita Patra and Nigel P. Smart, editors, Progress in Cryptology – INDOCRYPT 2017, pages 227–246. 2017. Springer International Publishing. DOI: https://doi.org/10.1007/978-3-319-71667-1_12
[BPKV24]
Luk Bettale, Ludovic Perret, Delaram Kahrobaei, and Javier Verbel. Biscuit: Shorter MPC-based Signature from PoSSo. In Christina Pöpper and Lejla Batina, editors, Applied Cryptography and Network Security - 22nd International Conference, ACNS 2024, Proceedings, Part I, volume 14583 of Lecture Notes in Computer Science, pages 457–486. 2024. Springer.
[BS23]
Charles Bouillaguet and Julia Sauvage. High-Performance Xbred. https://gitlab.lip6.fr/almasty/hpXbred. 2023.
[Buc65]
Bruno Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, University of Innsbruck, 1965.
[CFF+23a]
Benoît Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Goubin, Robin Larrieu, Gilles Macario-Rat, Brice Minaud, and Jacques Patarin. PROV: PRovable unbalanced Oil and Vinegar. 2023.
[CFF+23b]
Benoît Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Goubin, Robin Larrieu, Gilles Macario-Rat, Brice Minaud, and Jacques Patarin. Vox Specification v1.0. 2023.
[CFMR+17]
Antoine Casanova, Jean-Charles Faugere, Gilles Macario-Rat, Jacques Patarin, Ludovic Perret, and Jocelyn Ryckeghem. GeMSS: a great multivariate short signature. 2017.
[CHR+19]
Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe. MQDSS specifications. 2019.
[CKPS00]
Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In Bart Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, pages 392–407. 2000. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/3-540-45539-6_27
[CLO97]
David A. Cox, John Little, and Donal O'Shea. Springer, editor. Ideals, Varieties and Algorithms. Springer Berlin, Heidelberg 1997. DOI: https://doi.org/10.1007/978-3-319-16721-3
[DS05]
Jintai Ding and Dieter Schmidt. Rainbow, a New Multivariable Polynomial Signature Scheme. In John Ioannidis, Angelos Keromytis, and Moti Yung, editors, Applied Cryptography and Network Security, pages 164–175, Berlin, Heidelberg. 2005. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/11496137_12
[Dua23]
João Diogo Duarte. On the Complexity and Admissible Parameters of the Crossbred Algorithm in $\mathbb{F}_{q\geq2}$. https://eprint.iacr.org/2023/1664.pdf. 2023.
[Fau99]
Jean-Charles Faugére. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1):61-88, 1999. DOI: https://doi.org/10.1016/S0022-4049(99)00005-5
[Fau02]
Jean-Charles Faugère. A New Efficient Algorithm for Computing Gröbner Basis Without Reduction to Zero (F5). In Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pages 75–83, New York, NY, USA. 2002. ACM. DOI: https://doi.org/10.1145/780506.780516
[FHI+23]
Hiroki Furue, Fumitaka Hoshino, Yasuhiko Ikematsu, Toshiyuki Miyazawa, Akira Nagai, Tsunekazu Saito, Tsuyoshi Takagi, and Kan Yasuda. QR-UOV. 2023.
[FY79]
A.S. Fraenkel and Y. Yesha. Complexity of problems in games, graphs and algebraic equations. Discrete Applied Mathematics, 1(1):15-30, 1979. DOI: https://doi.org/10.1016/0166-218X(79)90012-X
[JBH+23]
Ding Jintai, Gong Boru, Guo Hao, He Xiaoou, Jin Yi, Pan Yuansheng, Dieter Schmidt, Tao Chengdong, Xie Danli, Yang Bo-Yin, and Zhao Ziyu. TUOV: Triangular Unbalanced Oil and Vinegar. 2023.
[JV17]
Antoine Joux and Vanessa Vitse. A Crossbred Algorithm for Solving Boolean Polynomial Systems. In Number-Theoretic Methods in Cryptology - NuTMiC 2017, volume 10737 of Lecture Notes in Computer Science, pages 3–21. 2017. Springer. DOI: https://doi.org/10.1007/978-3-319-76620-1_1
[KPG99]
Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced Oil and Vinegar Signature Schemes. In Jacques Stern, editor, Advances in Cryptology — EUROCRYPT '99, pages 206–222, Berlin, Heidelberg. 1999. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/3-540-48910-X_15
[KY24]
Momonari Kudo and Kazuhiro Yokoyama. The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences. https://arxiv.org/abs/2404.03530. 2024.
[KZ20]
Daniel Kales and Greg Zaverucha. An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes. In Stephan Krenn, Haya Shulman, and Serge Vaudenay, editors, Cryptology and Network Security - 19th International Conference, CANS 2020, Proceedings, pages 3–22. 2020. DOI: https://doi.org/10.1007/978-3-030-65411-5_1
[Laz83]
Daniel Lazard. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In J.A. van Hulzen, editor, EUROCAL 1983, volume 162 of Lecture Notes in Computer Science, pages 146–156. 1983. Springer, Heidelberg. DOI: https://doi.org/10.1007/3-540-12868-9_99
[MI88]
Tsutomu Matsumoto and Hideki Imai. Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. In D. et al. Barstow, editor, Advances in Cryptology — EUROCRYPT '88, pages 419–453. 1988. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/3-540-45961-8_39
[MIS20]
Koksal Mus, Saad Islam, and Berk Sunar. QuantumHammer: A Practical Hybrid Attack on the LUOV Signature Scheme. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1071–1084. 2020. ACM. DOI: https://dl.acm.org/doi/10.1145/3372297.3417272
[Nak24]
Shuhei Nakamura. Admissible Parameter Sets and Complexity Estimation of Crossbred Algorithm. https://eprint.iacr.org/2023/1687.pdf. 2024.
[NNY17]
Ruben Niederhagen, Kai-Chun Ning, and Bo-Yin Yang. https://github.com/kcning/mqsolver. 2017.
[NNY18]
Ruben Niederhagen, Kai-Chun Ning, and Bo-Yin Yang. Implementing Joux-Vitse's Crossbred Algorithm for Solving MQ Systems over GF(2) on GPUs. In Tanja Lange and Rainer Steinwandt, editors, Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings, volume 10786 of Lecture Notes in Computer Science, pages 121–141. 2018. Springer. DOI: https://doi.org/10.1007/978-3-319-79063-3_6
[Pat95]
Jacques Patarin. Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88. In Don Coppersmith, editor, Advances in Cryptology — CRYPT0' 95, pages 248–261. 1995. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/3-540-44750-4_20
[Sed22]
Vladimír Sedláček. mq-comparaison-suite. https://github.com/VladaSedlacek/mq-comparison-suite. 2022.
[TPD21]
Chengdong Tao, Albrecht Petzoldt, and Jintai Ding. Efficient Key Recovery for All HFE Signature Variants. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 70–93, Cham. 2021. Springer International Publishing. DOI: https://doi.org/10.1007/978-3-030-84242-0_4
[TW12]
Enrico Thomae and Christopher Wolf. Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited. In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, Public Key Cryptography – PKC 2012, pages 156–171. 2012. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-642-30057-8_10
[WTKC22]
Lih-Chung Wang, Po-En Tseng, Yen-Liang Kuan, and Chun-Yen Chou. A Simple Noncommutative UOV Scheme. 2022.
[Yas15]
Takanori Yasuda. Fukuoka MQ Challenge. https://www.mqchallenge.org. 2015.
[YDH+15]
Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi, and Kouichi Sakurai. MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems. https://eprint.iacr.org/2015/275. 2015.
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Damien Vidal, Claire Delaplace, and Sorina Ionica, An analysis of the Crossbred Algorithm for the MQ Problem. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ak86cy7qiu.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.