{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T14:09:16Z","timestamp":1771942156427,"version":"3.50.1"},"reference-count":51,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ministry of Internal Affairs and Communications","award":["JPJ000254"],"award-info":[{"award-number":["JPJ000254"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Multivariate public-key cryptosystems are potential candidates for post-quantum cryptography. The security of multivariate public-key cryptosystems relies on the hardness of solving a system of multivariate quadratic polynomial equations. Faug\u00e8re\u2019s F4 algorithm is one of the solution techniques based on the theory of Gr\u00f6bner bases and selects critical pairs to compose the Macaulay matrix. Reducing the matrix size is essential. Previous research has not fully examined how many critical pairs it takes to reduce to zero when echelonizing the Macaulay matrix in rows. Ito et al. (2021) proposed a new critical-pair selection strategy for solving multivariate quadratic problems associated with encryption schemes. Instead, this paper extends their selection strategy for solving the problems associated with digital signature schemes. Using the OpenF4 library, we compare the software performance between the integrated F4-style algorithm of the proposed methods and the original F4-style algorithm. Our experimental results demonstrate that the proposed methods can reduce the processing time of the F4-style algorithm by up to a factor of about seven under certain specific parameters. Moreover, we compute the minimum number of critical pairs to reduce to zero and propose their extrapolation outside our experimental scope for further research.<\/jats:p>","DOI":"10.3390\/cryptography7010010","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T03:02:32Z","timestamp":1678071752000},"page":"10","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Selection Strategy of F4-Style Algorithm to Solve MQ Problems Related to MPKC"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4309-8533","authenticated-orcid":false,"given":"Takashi","family":"Kurokawa","sequence":"first","affiliation":[{"name":"Cybersecurity Research Institute, National Institute of Information and Communications Technology, Nukui-Kitamachi, Koganei City 184-8795, Japan"},{"name":"Graduate School of Engineering Science, Akita University, Tegatagakuen-machi, Akita City 010-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takuma","family":"Ito","sequence":"additional","affiliation":[{"name":"Cybersecurity Research Institute, National Institute of Information and Communications Technology, Nukui-Kitamachi, Koganei City 184-8795, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naoyuki","family":"Shinohara","sequence":"additional","affiliation":[{"name":"Cybersecurity Research Institute, National Institute of Information and Communications Technology, Nukui-Kitamachi, Koganei City 184-8795, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3602-3231","authenticated-orcid":false,"given":"Akihiro","family":"Yamamura","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering Science, Akita University, Tegatagakuen-machi, Akita City 010-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigenori","family":"Uchiyama","sequence":"additional","affiliation":[{"name":"Graduate School of Science, Tokyo Metropolitan University, Minami-Osawa, Hachioji City 192-0397, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0036144598347011","article-title":"Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer","volume":"41","author":"Shor","year":"1999","journal-title":"SIAM Rev."},{"key":"ref_2","unstructured":"National Institute of Standards and Technology (2022, December 01). Post-Quantum Cryptography: Proposed Requirements and Evaluation Criteria, Available online: https:\/\/csrc.nist.gov\/News\/2016\/Post-Quantum-Cryptography-Proposed-Requirements."},{"key":"ref_3","unstructured":"National Institute of Standards and Technology (2022, December 01). New Call for Proposals: Call for Additional: Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process, Available online: https:\/\/csrc.nist.gov\/projects\/pqc-dig-sig\/standardization\/call-for-proposals."},{"key":"ref_4","unstructured":"(2023, February 05). CRYSTALS, Cryptographic Suite for Algebraic Lattices. Available online: https:\/\/pq-crystals.org."},{"key":"ref_5","unstructured":"(2023, February 05). FALCON, Fast-Fourier Lattice-Based Compact Signatures over NTRU. Available online: https:\/\/pq-crystals.org."},{"key":"ref_6","unstructured":"(2023, February 05). SPHINCS+, Stateless Hash-Based Signatures. Available online: https:\/\/sphincs.org."},{"key":"ref_7","unstructured":"Aragon, N., Barreto, P.S.L.M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Ghosh, S., Gueron, S., and G\u00fcneysu, T. (2023, February 05). BIKE\u2014Bit Flipping Key Encapsulation. Available online: https:\/\/bikesuite.org."},{"key":"ref_8","unstructured":"Bernstein, D.J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., Niederhagen, R., and Persichetti, E. (2023, February 05). Classic McEliece. Available online: https:\/\/classic.mceliece.org."},{"key":"ref_9","unstructured":"Melchor, C.A., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Bos, J., Deneuville, J.C., Dion, A., Gaborit, P., and Lacan, J. (2023, February 05). Hamming Quasi-Cyclic (HQC). Available online: http:\/\/pqc-hqc.org."},{"key":"ref_10","unstructured":"Castryck, W., and Decru, T. (2023, February 05). An Efficient Key Recovery Attack on SIDH (Preliminary Version); Paper 2022\/975; Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2022\/975."},{"key":"ref_11","unstructured":"(2023, February 05). The SIKE Team, SIKE and SIDH Are Insecure and Should Not Be Used, Available online: https:\/\/csrc.nist.gov\/csrc\/media\/Projects\/post-quantum-cryptography\/documents\/round-4\/submissions\/sike-team-note-insecure.pdf."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Barstow, D., Brauer, W., Brinch Hansen, P., Gries, D., Luckham, D., Moler, C., Pnueli, A., Seegm\u00fcller, G., Stoer, J., and Wirth, N. (1988, January 25\u201327). Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. Proceedings of the Advances in Cryptology\u2014EUROCRYPT \u201988, Davos, Switzerland.","DOI":"10.1007\/3-540-45961-8"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Coppersmith, D. (1995, January 27\u201331). Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt\u201988. Proceedings of the Advances in Cryptology\u2014CRYPT0\u2019 95, Santa Barbara, CA, USA.","DOI":"10.1007\/3-540-44750-4"},{"key":"ref_14","unstructured":"Maurer, U. (1996, January 12\u201316). Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. Proceedings of the Advances in Cryptology\u2014EUROCRYPT \u201996, Saragossa, Spain."},{"key":"ref_15","unstructured":"Patarin, J. (1997, January 22\u201326). The Oil and Vinegar Signature Scheme. Presented at the Dagstuhl Workshop on Cryptography, Dagstuhl, Germany. Transparencies."},{"key":"ref_16","unstructured":"Stern, J. (1999, January 2\u20136). Unbalanced Oil and Vinegar Signature Schemes. Proceedings of the Advances in Cryptology\u2014EUROCRYPT \u201999, Prague, Czech Republic."},{"key":"ref_17","unstructured":"National Institute of Standards and Technology (2022, December 01). Post-Quantum Cryptography, Available online: https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography."},{"key":"ref_18","unstructured":"Casanova, A., Faug\u00e8re, J., Macario-Rat, G., Patarin, J., Perret, L., and Ryckeghem, J. (2023, February 05). GeMSS: A Great Multivariate Short Signature. Available online: https:\/\/www-polsys.lip6.fr\/Links\/NIST\/GeMSS_specification.pdf."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Beullens, W., and Preneel, B. (2017, January 10\u201313). Field Lifting for Smaller UOV Public Keys. Proceedings of the Progress in Cryptology-INDOCRYPT 2017\u201418th International Conference on Cryptology in India, Chennai, India.","DOI":"10.1007\/978-3-319-71667-1_12"},{"key":"ref_20","unstructured":"Cheon, J.H., and Takagi, T. (2016, January 4\u20138). From 5-Pass MQ-Based Identification to MQ-Based Signatures. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2016, Hanoi, Vietnam."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ding, J., and Schmidt, D. (2005, January 7\u201310). Rainbow, a New Multivariable Polynomial Signature Scheme. Proceedings of the Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA.","DOI":"10.1007\/11496137_12"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Ristenpart, T. (2020, January 17\u201321). Cryptanalysis of the Lifted Unbalanced Oil Vinegar Signature Scheme. Proceedings of the Advances in Cryptology\u2014CRYPTO 2020, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-030-56880-1"},{"key":"ref_23","unstructured":"Kales, D., and Zaverucha, G. (2023, February 05). Forgery Attacks on MQDSSv2.0, Available online: https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Post-Quantum-Cryptography\/documents\/round-2\/official-comments\/MQDSS-round2-official-comment.pdf."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Moody, D., Alagic, G., Apon, D., Cooper, D., Dang, Q., Kelsey, J., Liu, Y., Miller, C., Peralta, R., and Perlner, R. (2020). Status Report  on the Second Round of the NIST Post-Quantum Cryptography Standardization Process, National Institute of Standards and Technology. NIST Interagency\/Internal Report (NISTIR).","DOI":"10.6028\/NIST.IR.8309"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Wiener, M. (1999, January 15\u201319). Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. Proceedings of the Advances in Cryptology\u2014CRYPTO\u2019 99, Santa Barbara, CA, USA.","DOI":"10.1007\/3-540-48405-1_2"},{"key":"ref_26","first-page":"257","article-title":"Computing Loci of Rank Defects of Linear Matrices Using Gr\u00f6Bner Bases and Applications to Cryptology","volume":"Volume ISSAC \u201910","author":"Spaenlehauer","year":"2010","journal-title":"Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation"},{"key":"ref_27","unstructured":"Moriai, S., and Wang, H. (2020, January 7\u201311). Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2020, Daejeon, Republic of Korea."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Malkin, T., and Peikert, C. (2021, January 16\u201320). Efficient Key Recovery for All HFE Signature Variants. Proceedings of the Advances in Cryptology\u2014CRYPTO 2021, Virtual Event.","DOI":"10.1007\/978-3-030-84245-1"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Canteaut, A., and Standaert, F.X. (2021, January 17\u201321). Improved Cryptanalysis of UOV and Rainbow. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2021, Zagreb, Croatia.","DOI":"10.1007\/978-3-030-77870-5"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Dodis, Y., and Shrimpton, T. (2022, January 15\u201318). Breaking Rainbow Takes a Weekend on a Laptop. Proceedings of the Advances in Cryptology\u2014CRYPTO 2022, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-031-15979-4"},{"key":"ref_31","unstructured":"Alagic, G., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y., Miller, C., Moody, D., and Peralta, R. (2022). Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, National Institute of Standards and Technology. NIST Interagency\/Internal Report (NISTIR)."},{"key":"ref_32","unstructured":"Beullens, W., Chen, M.S., Hung, S.H., Kannwischer, M.J., Peng, B.Y., Shih, C.J., and Yang, B.Y. (2023, February 05). Oil and Vinegar: Modern Parameters and Implementations; Paper 2023\/059; Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2023\/059."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Courtois, N., Klimov, A., Patarin, J., and Shamir, A. (2000, January 14\u201318). Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium.","DOI":"10.1007\/3-540-45539-6_27"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","article-title":"A New Efficient Algorithm for Computing Gr\u00f6bner Bases (F4)","volume":"139","year":"1999","journal-title":"J. Pure Appl. Algebra"},{"key":"ref_35","unstructured":"Faug\u00e8re, J.C. (2002, January 7\u201310). A New Efficient Algorithm for Computing Gr\u00f6bner Bases without Reduction to Zero (F5). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201902, Lille, France."},{"key":"ref_36","unstructured":"(2022, November 18). The RSA Challenge Numbers. Available online: https:\/\/web.archive.org\/web\/20010805210445\/http:\/\/www.rsa.com\/rsalabs\/challenges\/factoring\/numbers.html."},{"key":"ref_37","unstructured":"(2022, November 18). The Certicom ECC Challenge. Available online: https:\/\/www.certicom.com\/content\/dam\/certicom\/images\/pdfs\/challenge-2009.pdf."},{"key":"ref_38","unstructured":"(2022, November 18). TU Darmstadt Lattice Challenge. Available online: https:\/\/www.latticechallenge.org."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/2850449.2850462","article-title":"A multivariate quadratic challenge toward post-quantum generation cryptography","volume":"49","author":"Yasuda","year":"2015","journal-title":"ACM Commun. Comput. Algebra"},{"key":"ref_40","unstructured":"Yasuda, T., Dahan, X., Huang, Y., Takagi, T., and Sakurai, K. (2022, December 01). MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems; Paper 2015\/275; Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2015\/275."},{"key":"ref_41","first-page":"19","article-title":"A Theoretical Basis for the Reduction of Polynomials to Canonical Forms","volume":"10","author":"Buchberger","year":"1976","journal-title":"SIGSAM Bull."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Becker, T., and Weispfenning, V. (1993). Gr\u00f6ebner Bases, a Computationnal Approach to Commutative Algebra, Springer. Graduate Texts in Mathematics.","DOI":"10.1007\/978-1-4612-0913-3"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Kiayias, A. (2011, January 14\u201318). A Variant of the F4 Algorithm. Proceedings of the Topics in Cryptology\u2014CT-RSA 2011, San Francisco, CA, USA.","DOI":"10.1007\/978-3-642-19074-2"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Makarim, R.H., and Stevens, M. (2017, January 25\u201328). M4GB: An Efficient Gr\u00f6bner-Basis Algorithm. Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, Kaiserslautern, Germany.","DOI":"10.1145\/3087604.3087638"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1587\/transfun.2020CIP0025","article-title":"Solving the MQ Problem Using Gr\u00f6bner Basis Techniques","volume":"E104.A","author":"Ito","year":"2021","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1515\/JMC.2009.009","article-title":"Hybrid approach for solving multivariate systems over finite fields","volume":"3","author":"Bettale","year":"2009","journal-title":"J. Math. Cryptol."},{"key":"ref_47","unstructured":"Joux, A., Vitse, V., and Coladon, T. (2021, May 17). OpenF4: F4 Algorithm C++ Library (Gr\u00f6bner Basis Computations over Finite Fields). Available online: https:\/\/github.com\/nauotit\/openf4."},{"key":"ref_48","unstructured":"Fischlin, M., and Katzenbeisser, S. (2013). Number Theory and Cryptography: Papers in Honor of Johannes Buchmann on the Occasion of His 60th Birthday, Springer."},{"key":"ref_49","first-page":"3","article-title":"A criterion for detecting unnecessary reductions in the construction of Gr\u00f6bner bases","volume":"Volume 72","author":"Ng","year":"1979","journal-title":"Proceedings of the Symbolic and Algebraic Computation, EUROSAM \u201979, An International Symposium on Symbolic and Algebraic Manipulation"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1006\/jsco.1993.1051","article-title":"Efficient Computation of Zero-Dimensional Gr\u00f6bner Bases by Change of Ordering","volume":"16","author":"Gianni","year":"1993","journal-title":"J. Symb. Comput."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0747-7171(88)80048-8","article-title":"On an installation of Buchberger\u2019s algorithm","volume":"6","author":"Gebauer","year":"1988","journal-title":"J. Symb. Comput."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/1\/10\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:44:03Z","timestamp":1760121843000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/1\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,27]]},"references-count":51,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["cryptography7010010"],"URL":"https:\/\/doi.org\/10.3390\/cryptography7010010","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,27]]}}}