Document Zbl 07778569

Wang, Lih-Chung; Wei, Tzer-Jen; Shih, Jian-Ming; Hu, Yuh-Hua; Hsieh, Chih-Cheng

An algorithm for solving over-determined multivariate quadratic systems over finite fields. (English) Zbl 07778569

Adv. Math. Commun. 18, No. 1, 55-90 (2024).

Summary: An algorithm for solving over-determined multivariate quadratic systems over finite fields is given. It is more efficient than other known algorithms over finite fields of relatively large size in terms of both performance and memory comsumption. It is also simpler for computer programming. The complexity estimate of our algorithm can be used to estimate the security level of multivariate cryptosystems by solving the multivariate quadratic systems induced by the cryptosystems.

MSC:

68W30	Symbolic computation and algebraic computation
13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13P15	Solving polynomial systems; resultants

Keywords:

multivariate quadratic (MQ) problem; multivariate cryptosystem

Software:

Magma

Cite Review PDF

Full Text: DOI

References:

[1]	G. J.-C. H. M. M. Ars Faugère Imai Kawazoe Sugita, Comparison between XL and Gröbner basis algorithms, Advances in Cryptology - ASIACRYPT 2004, 3329, 338-353 (2004) · Zbl 1094.94024 · doi:10.1007/978-3-540-30539-2_24
[2]	L. J.-C. L. Bettale Faugère Perret, Hybrid approach for solving multivariate systems over finite fields, J. Math. Cryptol., 3, 177-197 (2009) · Zbl 1183.94021 · doi:10.1515/JMC.2009.009
[3]	A. Braeken, C. Wolf and B. Preneel, A study of the security of unbalanced oil and vinegar signature schemes, Topics in cryptology-CT-RSA 2005, Lecture Notes in Computer Science, Springer-Verlag, 3376 (2005), 29-43. · Zbl 1079.94536
[4]	N. Courtois, The security of hidden field equations(HFE), Topics in Cryptology-CT-RSA 2001, Lecture Notes in Computer Sci., Springer, Berlin, 2020 (2001), 266-281. · Zbl 0991.94035
[5]	N. Courtois, Higher order correlation attacks, XL algorithm and cryptanalysis of toyocrypt, Information Security and Cryptology-ICISC 2002, Lecture Notes in Computer Science, Springer-Verlag, 2587 (2003), 182-199. · Zbl 1031.94515
[6]	N. Courtois, Algebraic attacks over \(GF(2^k)\), application to HFE challenge 2 and sflash-v2, Public Key Cryptography-PKC 2004, Lecture Notes in Computer Sci., Springer-Verlag, 2947 (2004), 201-217. · Zbl 1198.94089
[7]	N. Courtois, M. Daum and P. Felke, On the security of HFE, HFEv and Quartz, Public Key Cryptography - PKC 2003, Lecture Notes in Computer Science, Springer-Verlag, 2567 (2002), 337-350. · Zbl 1033.94518
[8]	N. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in Cryptology - EUROCRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, 1087 (2000), 392-407. · Zbl 1082.94514
[9]	N. Courtois and J. Patarin, About the XL Algorithm over \(GF(2)\), Topics in Cryptology-CT-RSA 2003, Lecture Notes in Computer Sci., Springer-Verlag, 2612 (2003), 141-157. · Zbl 1039.94511
[10]	D. Cox, J. Little and D. O’Shea, Ideal, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, \(4^{th}\) edition, Undergraduate Texts in Mathematics. Springer, Cham, 2015. · Zbl 1335.13001
[11]	C. Diem, The XL- algorithm and a conjecture from commutative algebra, Advances in Cryptology-ASIACRYPT 2004, Lecture Notes in Computer Sci., Springer-Verlag 3329 (2004), 323-337. · Zbl 1094.94029
[12]	V. Dubois, P.-A. Fouque1, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH, Advances in Cryptology CRYPTO 2007, Lecture Notes in Computer Science, Springer-Verlag, 4622 (2007), 1-12. · Zbl 1215.94043
[13]	J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, Applied Cryptography and Network Security\|ACNS 2005, Lecture Notes in Computer Science, Springer-Verlag 3531 (2005), 164-175. · Zbl 1126.68393
[14]	J.-C. Faugère, A new efficient algorithm for computing Gröbner bases \((F_4)\), J. Pure Appl. Algebra, 139, 61-88 (1999) · Zbl 0930.68174 · doi:10.1016/S0022-4049(99)00005-5
[15]	J.-C. Faugère, A new efficient algorithm for computing Gröbner Bases without reduction to zero \((F_5)\), Symbolic and Algebraic Computation, International Symposium ISSAC, Proceedings. ACM, 2002 (2002), 75-83. · Zbl 1072.68664
[16]	J.-C. Faugère and A. Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using gröbner bases, Advances in Cryptology CRYPTO 2003, Lecture Notes in Computer Science, Springer-Verlag, 2729 (2003), 44-60. · Zbl 1122.94371
[17]	M. R. Garay and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, Calif., 1979. · Zbl 0411.68039
[18]	L. Goubin and N. Courtois, Cryptanalysis of the TTM cryptosystem, Advances in Cryptology-ASIACRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, 1976 (2000), 44-57. · Zbl 0980.94017
[19]	Y.-H. Hu, C.-Y. Chou, L.-C. Wang and F. Lai, Cryptanalysis of variants of UOV, Information Security Conference ISC 2006, Lecture Notes in Computer Science, Springer-Verlag, 4176 (2006), 161-170. · Zbl 1156.94415
[20]	A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, Advances in Cryptology EUROCRYPT’99, Lecture Notes in Computer Science, Springer-Verlag, 1592 (1999), 206-222. · Zbl 0933.94031
[21]	A. Kipnis and A. Shamir, Cryptanalysis of the oil and vinegar signature scheme, Advances in Cryptology CRYPTO’98, Lecture Notes in Computer Science, Springer-Verlag, 1462 (1998), 257-267. · Zbl 0931.94030
[22]	A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in Cryptology CRYPTO’99, Lecture Notes in Computer Sci., Springer-Verlag, 1666 (1999), 19-30. · Zbl 0940.94012
[23]	W. Keith Nicholson, Introduction to Abstract Algebra, \(2^nd\) edition, John Wiley & Sons, Inc., New York, 1999. · Zbl 0929.00001
[24]	Performance of Optimized Implementations of the NESSIE primitives, version 2.0, http://www.cryptonessie.org.
[25]	J. Patarin, Cryptanalysis of the matsumoto and imai public key scheme of Eurocrypt’88, Advances in Cryptology CRYPTO’95, Lecture Notes in Computer Science, Springer-Verlag, 963 (1995), 248-261. · Zbl 0868.94025
[26]	J. Patarin, The Oil and Vinegar Algorithm for Signatures, presented at the Dagstuhl Workshop on Cryptography, 1997.
[27]	J. Patarin and L. Goubin, Improved algorithms for isomorphisms of polynomials, Advances in Cryptology - EUROCRYPT 1998, Lecture Notes in Computer Science, Springer-Verlag, 1403 (1998), 184-200. · Zbl 0919.94030
[28]	J.-M. Shy, Theory of XLT Algorithm and Its Analysis, Master thesis.
[29]	L.-C. Wang, Y.-H. Hu, F. Lai, C.-Y. Chou and B.-Y. Yang, Tractable rational map signature, Public Key Cryptography PKC 2005, Lecture Notes in Computer Science, Springer-Verlag, 3386 (2005), 244-257. · Zbl 1081.94555
[30]	L.-C. Wang, B.-Y. Yang, Y.-H. Hu and F. Lai, A “mdeium- field” multivariate public-key encryption scheme, Topics in cryptology-CT-RSA 2006, Lecture Notes in Computer Science, Springer-Verlag, 3860 (2006), 132-149. · Zbl 1125.94028
[31]	C. Wolf, A. Braeken and B. Preneel, Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC, Security in Communication Networks, 4th International Conference, SCN 2004, Lecture Notes in Computer Science, Springer-Verlag, 3352 (2005), 294-309. · Zbl 1116.94336
[32]	B.-Y. Yang and J.-M. Chen, All in the XL family: Theory and practice, Information Security and Cryptology ICISC 2004, Lecture Notes in Computer Science, Springer-Verlag, 3506 (2005), 67-86. · Zbl 1133.94336
[33]	B.-Y. J.-M. Yang Chen, Theoretical analysis of XL over small fields,, ACISP 2004: Information Security and Privacy, 3108, 277-288 (2004) · Zbl 1098.94032 · doi:10.1007/978-3-540-27800-9_24
[34]	B.-Y. Yang and J.-M. Chen, Building secure tame-like multivariate public-key cryptosystems the new TTS, Information Security and Privacy, 35th Australasian Conference, ACISP 2005, Lecture Notes in Computer Science, Springer-Verlag, 3574 (2005), 518-531. · Zbl 1127.94356
[35]	B.-Y. Yang, J.-M. Chen and N. Courtois, On Asymptotic security estimates in XL and gröbner bases-Related algebraic cryptanalysis, Information and Communications Security, 6th International Conference ICICS 2004, Lecture Notes in Computer Science Springer-Verlag, 3269 (2004), 401-413. · Zbl 1109.94353
[36]	Version V 2: 13 - 14 released on 2007/07/06, in http://magma.maths.usyd. edu.au/magma/, Online, Demo http://magma.maths.usyd.edu.au/calc, CPU: Opteron 2.6G.

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.