Abstract
The multivariate public key cryptosystem (MPKC) is a potential post-quantum cryptosystem. Its safety depends on the hardness of solving systems of algebraic equations over finite fields. In particular, the multivariate quadratic (MQ) problem is that of solving such a system consisting of quadratic polynomials and is regarded as an important research subject in cryptography. In the Fukuoka MQ challenge project, the hardness of the MQ problem is discussed, and the algorithms used for the MQ problem and the computational results obtained by these algorithms are reported. The algorithms to compute Gröbner basis for the polynomial set given by the MQ problem are for solving the MQ problem. For example, the \(F_4\) algorithm and M4GB algorithm have succeeded in solving several MQ problems provided by the project. In this paper, based on the \(F_4\)-style algorithm, we present an efficient algorithm to solve the MQ problems with dense polynomials generated in the Fukuoka MQ challenge project. We experimentally show that our algorithm requires less computational time and memory for these MQ problems than the \(F_4\) algorithm and M4GB algorithm. We succeeded in solving Type II problems using our algorithm when the numbers of variables are 36 and 37.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Becker, T., Weispfenning, V.: Gröbner Bases, a Computational Approach to Commutative Algebra. Graduate Texts in Mathematics. Springer, New York (1993). https://doi.org/10.1007/978-1-4612-0913-3
Faugère, J.C.: A new efficient algorithm for computing Gröbner bases \((F_4)\). J. Pure Appl. Algebra 139(1–3), 61–88 (1999)
Faugère, J., Gianni, P.M., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993)
Makarim, R.H., Stevens, M.: M4GB: an efficient Gröbner-basis algorithm. In: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, Kaiserslautern, Germany, 25–28 July 2017, pp. 293–300 (2017)
Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Barstow, D., et al. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-45961-8_39
Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_4
Sakumoto, K., Shirai, T., Hiwatari, H.: Public-key identification schemes based on multivariate quadratic polynomials. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 706–723. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_40
Yasuda, T., Dahan, X., Huang, Y., Takagi, T., Sakurai, K.: MQ challenge: Hardness evaluation of solving multivariate quadratic problems. IACR Cryptology ePrint Archive 2015, 275 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Ito, T., Shinohara, N., Uchiyama, S. (2019). An Efficient \(F_4\)-style Based Algorithm to Solve MQ Problems. In: Attrapadung, N., Yagi, T. (eds) Advances in Information and Computer Security. IWSEC 2019. Lecture Notes in Computer Science(), vol 11689. Springer, Cham. https://doi.org/10.1007/978-3-030-26834-3_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-26834-3_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26833-6
Online ISBN: 978-3-030-26834-3
eBook Packages: Computer ScienceComputer Science (R0)