Computing border bases using mutant strategies

E. Ullah   ; S. A. Khan

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 54 (2014) no. 1

Résumé

Border bases, a generalization of Gröbner bases, have actively been addressed during recent years due to their applicability to industrial problems. In cryptography and coding theory a useful application of border based is to solve zero-dimensional systems of polynomial equations over finite fields, which motivates us for developing optimizations of the algorithms that compute border bases. In 2006, Kehrein and Kreuzer formulated the Border Basis Algorithm (BBA), an algorithm which allows the computation of border bases that relate to a degree compatible term ordering. In 2007, J. Ding et al. introduced mutant strategies bases on finding special lower degree polynomials in the ideal. The mutant strategies aim to distinguish special lower degree polynomials (mutants) from the other polynomials and give them priority in the process of generating new polynomials in the ideal. In this paper we develop hybrid algorithms that use the ideas of J. Ding et al. involving the concept of mutants to optimize the Border Basis Algorithm for solving systems of polynomial equations over finite fields. In particular, we recall a version of the Border Basis Algorithm which is actually called the Improved Border Basis Algorithm and propose two hybrid algorithms, called MBBA and IMBBA. The new mutants variants provide us space efficiency as well as time efficiency. The efficiency of these newly developed hybrid algorithms is discussed using standard cryptographic examples.

Bibliographie

[1] B. Buchberger, Ph. D. Thesis, Univ. of Innsbruck, Innsbruck, 1965 | Zbl

[2] J.-C. Faugère, “A new efficient algorithm for computing Gröbner basis (F4)”, J. Pure Appl. Alg., 139 (1999), 61–88 | DOI | MR | Zbl

[3] J.-C. Faugère, “A new efficient algorithm for computing Gröbner basis without reduction to zero (F5)”, Proceedings of International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, ACM, New York, 2002 | MR | Zbl

[4] N. T. Courtois, A. Klimov, J. Patarin, A. Shamir, “Efficient algorithms for solving overdefined systems of multivariate polynomial equations”, Advances in Cryptography, EUROCRYPT 2000, LNCS, 1807, ed. B. Preneel, Springer-Verlag, Berlin, 2000, 392–407 | MR | Zbl

[5] M. Sugita, M. Kawazoe, H. Imai, Relation between XL algorithm and Gröbner bases algorithms, Cryptol., Report 2004/112, , 2004 http://eprint.iacr.org/

[6] J. Ding, Mutants and its impact on polynomial solving strategies and algorithms, Privately distributed research note, Univ. of Cincinnati and Technical Univ., Darmstadt, 2006

[7] M. S. E. Mohamed, W. S. A. Mohamed, J. Ding, J. Buchmann, “MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy”, Proceeding of the Second International Workshop on Post-Quantum Cryptography, PQCrypto08 (Cincinnati, USA), LNCS, Springer-Verlag, Berlin, 2008, 203–215 | MR | Zbl

[8] J. Ding, J. Buchmann, M. S. E. Mohamed, W. S. A. Mohamed, R.-P. Weinmann, “MutantXL”, Proceedings of Conference on Symbolic Computation and Cryptography (Beijing, 2008), eds. J.-C. Faugère, L. Perret, Birkhäuser, 2009

[9] M. S. E. Mohamed, J. Ding, J. Buchmann, Algebraic cryptanalysis of MQQ public key cryptosystem by MutantXL, Technical Report 2008/451, Cryptology ePrint Archive, 2008

[10] M. S. E. Mohamed, D. Cabarcas, J. Ding, J. Buchmann, S. Bulygin, “MXL3: An efficient algorithm for computing Gröbner bases of zero dimensional ideals”, Proceedings of the 12th International Conference on Information Security and Cryptology, ICISC 2009, LNCS, 5984, Springer-Verlag, Berlin, 2010, 87–100 | MR

[11] M. Albrecht, C. Cid, J.-C. Faugère, L. Perret, “On the relation between the MXL family of algorithms and Gröbner basis algorithms”, J. Symbolic Comput., 47 (2012), 926–941 | DOI | MR | Zbl

[12] M. Kreuzer, Algebraic attacks galore!, Groups Complexity Cryptol., 1 (2009), 231–259 | MR | Zbl

[13] W. Auzinger, H. J. Stetter, “An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations”, Proceedings of the International Conference on Numerical Mathematics (National University of Singapore, May 31–June 4, 1988), Birkhäuser, 1988, 11–30 | MR

[14] B. Mourrain, “A new criterion for normal form algorithms”, Proceedings of the AAECC13 Conference (Honolulu, 1999), LNCS, 1719, eds. M. Fossorier, H. Imai, S. Lin, A. Poli, Springer-Verlag, Heidelberg, 1999, 440–443 | MR

[15] A. Kehrein, M. Kreuzer, “Computing border bases”, J. Pure Appl. Alg., 205 (2005), 279–295 | DOI | MR

[16] M. Borges-Quintana, M. A. Borges-Trenard, E. Martinez-Moro, “An application of Moller's algorithm to coding theory”, Gröbner Bases, Coding, and Cryptography, eds. M. Sala, T. Mora, L. Perret, S. Sakata, C. Traverso, Springer, Berlin, 2009, 379–384 | Zbl

[17] J. Abbott, C. Fassino, M. L. Torrente, “Stable border basis for ideals of points”, J. Symbolic Comput., 43 (2008), 883–894 | DOI | MR | Zbl

[18] D. Heldt, M. Kreuzer, S. Pokutta, H. Poulisse, “Approximate computation of zero-dimensional polynomial ideals”, J. Symbolic Comput., 44 (2009), 1566–1599 | DOI | MR

[19] M. Kreuzer, H. Poulisse, Subideal border bases, Preprint, 2009 | MR

[20] G. Braun, S. Pokutta, A polyhedral approach to computing border bases, 2010, arXiv: math.AG/0911.0859v3

[21] S. Kaspar, “Computing border bases without using a term ordering”, Beitrage zur Algebra und Geometrie, Contributions to Algebra and Geometry, 54:1 (2013), 211–223 | DOI | MR | Zbl

[22] B. Mourrain, P. Trebuchet, “Border basis representation of a general quotient algebra”, International Conference on Symbolic and Algebraic Computation, ISSAC (Grenoble, France, 2012), ACM, 2012

[23] N. Courtois, L. Goubin, W. Meier, J.-D. Tacier, “Solving underdefined systems of multivariate quadratic equations”, Public Key Cryptography, PKC 2002, LNCS, 2274, eds. D. Naccache, D. Paillier, Springer, Berlin, 2002, 211–227 | Zbl

[24] J. Patarin, “Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms”, EUROCRVPT, 1996, 33–48 http://www.minrank.org/hfe.pdf

[25] J. Buchmann, D. Cabarcas, J. Ding, M. S. E. Mohamed, “Flexible partial enlargement to accelerate Gröbner basis computation over $\mathrm{F}_2$”, Progress in Cryptology, AFRICACRYPT 2010: Proceedings of the 3rd International Conference on Cryptology, LNCS, 6055, Springer, Berlin, 2010, 69–81 | MR | Zbl

[26] M. Kreuzer, L. Robbiano, Computational Commutative Algebra, v. 1, Springer, Berlin, 2000 | MR | Zbl

[27] M. Kreuzer, L. Robbiano, Computational Commutative Algebra, v. 2, Springer, Berlin, 2000 | MR | Zbl

[28] A. Kehrein, M. Kreuzer, “Characterizations of border bases”, J. Pure Appl. Alg., 196 (2005), 251–270 | DOI | MR | Zbl

[29] A. Kehrein, M. Kreuzer, L. Robbiano, “An algebraist's view on border bases”, Solving Polynomial Equations: Foundations, Algorithms, and Applications, Springer, Berlin, 2005, 169–202 | DOI | MR | Zbl

[30] The ApCoCoA Team http://www.apcocoa.org

[31] J. Limbeck, Implementation und optimierung algebraischer angriffe, Diploma Thesis, Univ. Passau, 2008

[32] M. Albrecht, G. Bard, M4RI: Linear algebra over GF(2), , 2008 http://m4ri.sagemath.org/index.html

[33] W. Bosma, J. Cannon, C. Playoust, “The Magma algebra system. I: The user language”, J. Symbolic Comput., 24 (1997), 235–265 | DOI | MR | Zbl

[34] J. Buchmann, J. Ding, M. S. E. Mohamed, W. S. A. Mohamed, “MutantXL: Solving Multivariate Polynomial Equations for Cryptanalysis”, Symmetric Cryptography, Dagstuhl Seminar Proceedings, eds. H. Handschuh, S. Lucks, B. Preneel, P. Rogaway, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Germany, 2009

[35] M. S. E. Mohamed, W. S. A. Mohamed, J. Ding, J. Buchmann, The complexity analysis of the MutantXL family, Preprint, 2010