On the relation between the MXL family of algorithms and Gröbner basis algorithms.(English)Zbl 1237.13051

Summary: The computation of Gröbner bases remains one of the most powerful methods for tackling the Polynomial System Solving (PoSSo) problem. The most efficient known algorithms reduce the Gröbner basis computation to Gaussian eliminations on several matrices. However, several degrees of freedom are available to generate these matrices. It is well known that the particular strategies used can drastically affect the efficiency of the computations. In this work, we investigate a recently-proposed strategy, the so-called “Mutant strategy”, on which a new family of algorithms is based (MXL, MXL$$_{2}$$ and MXL$$_{3})$$. By studying and describing the algorithms based on Gröbner basis concepts, we demonstrate that the Mutant strategy can be understood to be equivalent to the classical Normal Selection Strategy currently used in Gröbner basis algorithms. Furthermore, we show that the ”partial enlargement” technique can be understood as a strategy for restricting the number of S-polynomials considered in an iteration of the $$F_{4}$$ Gröbner basis algorithm, while the new termination criterion used in MXL$$_{3}$$ does not lead to termination at a lower degree than the classical Gebauer-Möller installation of Buchberger’s criteria. We claim that our results map all novel concepts from the MXL family of algorithms to their well-known Gröbner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and $$F_{4}$$, we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of $$F_{4}$$.

MSC:

 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Software:

MXL3; FGb; MutantXL; PolyBoRi; Magma
Full Text:

References:

 [1] Albrecht, M.; Cid, C., Algebraic techniques in differential cryptanalysis, (), 193-208 · Zbl 1291.94043 [2] Albrecht, M.; Cid, C.; Dullien, T.; Faugère, J.-C.; Perret, L., Algebraic precomputations in differential cryptanalysis, (), 1-18 [3] Ars, G.; Faugère, J.-C.; Imai, H.; Kawazoe, M.; Sugita, M., Comparison between XL and Gröbner basis algorithms, (), 338-353 · Zbl 1094.94024 [4] Becker, T.; Weispfenning, V., Gröbner bases — A computational approach to commutative algebra, (1991), Springer, Verlag Berlin, Heidelberg, New York [5] Bosma, W.; Cannon, J.; Playoust, C., The MAGMA algebra system I: the user language, Journal of symbolic computation, 24, 235-265, (1997) · Zbl 0898.68039 [6] Bouillaguet, C.; Faugère, J.-C.; Fouque, P.-A.; Perret, L., Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem, () · Zbl 1291.94062 [7] Brickenstein, M.; Dreyer, A., Polybori: A framework for Gröbner-basis computations with Boolean polynomials, Journal of symbolic computation, 44, 9, 1326-1345, (2009) · Zbl 1186.68571 [8] Buchberger, B., 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. Ph.D. thesis, Universität Innsbruck. · Zbl 1245.13020 [9] Buchberger, B., Bruno buchberger’s phd thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, Journal of symbolic computation, 41, 3-4, 475-511, (2006) · Zbl 1158.01307 [10] Buchmann, J.; Cabarcas, D.; Ding, J.; Mohamed, M., Flexible partial enlargement to accelerate gröner basis computation over F2, (), 69-81 · Zbl 1284.94058 [11] Buchmann, J.A.; Ding, J.; Mohamed, M.S.E.; Mohamed, W.S.A.E., Mutantxl: solving multivariate polynomial equations for cryptanalysis, () [12] Cid, C.; Leurent, G., An analysis of the XSL algorithm, (), 333-352 · Zbl 1154.94384 [13] Courtois, N.; Meier, W., Algebraic attacks on stream ciphers with linear feedback, (), 345-359 · Zbl 1038.94525 [14] Courtois, N.T., Algebraic attacks over GF(2**k), application to HFE challenge 2 and sflash-v2, (), 201-217 · Zbl 1198.94089 [15] Courtois, N.T.; Klimov, A.; Patarin, J.; Shamir, A., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, (), 392-407 · Zbl 1082.94514 [16] Courtois, N.T.; Patarin, J., About the XL algorithm over GF(2), (), 141-157 · Zbl 1039.94511 [17] Courtois, N.T.; Pieprzyk, J., Cryptanalysis of block ciphers with overdefined systems of equations, (), 267-287 · Zbl 1065.94543 [18] Cox, D.; Little, J.; O’Shea, D., Ideals, varieties, and algorithms, (1992), Springer, Verlag Berlin, Heidelberg, New York [19] Diem, C., The XL-algorithm and a conjecture from commutative algebra, (), 323-337 · Zbl 1094.94029 [20] Faugère, J.-C., A new efficient algorithm for computing Gröbner basis (F4), Journal of pure and applied algebra, 139, 1-3, 61-88, (1999) · Zbl 0930.68174 [21] Faugère, J.-C.; dit Vehel, F.L.; Perret, L., Cryptanalysis of minrank, (), 280-296 · Zbl 1183.94033 [22] Faugère, J.-C.; Gianni, P.M.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of symbolic computation, 16, 329-344, (1993) · Zbl 0805.13007 [23] Faugère, J.-C.; Joux, A., Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases, (), 44-60 · Zbl 1122.94371 [24] Faugère, J.-C.; Lachartre, S., Parallel Gaussian elimination for Gröbner bases computations in finite fields, (), 89-97 [25] Faugère, J.-C.; Perret, L., Cryptanalysis of 2R^{−} schemes, (), 357-372 · Zbl 1161.94397 [26] Faugère, J.-C.; Perret, L., Algebraic cryptanalysis of curry and flurry using correlated messages, (), 266-277 · Zbl 1281.94023 [27] Lazard, D., Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, (), 146-156 [28] Lim, C.-W.; Khoo, K., An analysis of XSL applied to BES, (), 242-253 · Zbl 1186.94459 [29] Mandache, A.M., The Gröbner basis algorithm and subresultant theory, (), 123-128 · Zbl 0917.13009 [30] Mandache, A.M., 1995. Gröbner bases computation and Gaussian elimination. Ph.D. thesis, RISC, Johannes Kepler University Linz. [31] Mandache, A.M., 1996. On the relationship between Involutive basis and Gröbner basis algorithms. RISC-Report 96-24. [32] Mohamed, M.S.E., 2011. Private communication. [33] Mohamed, M.S.E., Mohamed, W.S.A.E., Ding, J., Buchmann, J., 2008. MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy. In: PQCrypto. pp. 203-215. · Zbl 1177.11094 [34] Mohamed, M.S.E., Cabarcas, D., Ding, J., Buchmann, J., Bulygin, S., 2009a. MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals. In: 12th International Conference on Information Security and Cryptology, ICISC. [35] Mohamed, M.S.E.; Werner, F.; Ding, J.; Buchmann, J., Algebraic attack on the MQQ public key cryptosystem, (), 392-401 · Zbl 1287.94087 [36] Patarin, J., Hidden fields equations (hfe) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms, (), 33-48 · Zbl 1301.94125 [37] Thomae, E., Wolf, C., 2010. Unravel XL and its variants. Cryptology ePrint Archive, Report 2010/596, http://eprint.iacr.org/.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.