Methods to solve algebraic equations in cryptanalysis

Semaev, Igor; Mikuš, Michal

doi:10.2478/v10127-010-0009-6

Abstract

The goal of the present paper is a survey of methods to solve equation systems common in cryptanalysis. The methods depend on the equation representation and fall into three categories: Gröbner basis algorithms, SAT-solving methods and Agreeing-Gluing algorithms.

References

[1] ARS, G.-FAUGÈRE, J. C.-IMAI, H.-KAWAZOE, M.-SUGITA, M.: Comparisonbetween XL and Gröbner basis algorithms, in: Advances in Cryptology-ASIACRYPT ’04 (P. J. Lee, ed.), Lecture Notes in Comput. Sci., Vol. 3329, Springer-Verlag, Berlin, 2004, pp. 338-353.
Search in Google Scholar
[2] BARDET, M.-FAUGÉRE, J.-C.-SALVY, B.: Complexity of Gröbner basis computationfor semi-regular overdetermined sequences over F2 with solutions in F2, Research report 5049, INRIA, 2003.
Search in Google Scholar
[3] BARDET, M.-FAUGÈRE, J. C.-SALVY, B.-YANG, B. Y.: Asymptotic behaviourof the degree of regularity of semiregular polynomial systems, in: Proc. of MEGA ’05, 8th International Symposium on Effective Methods in Algebraic Geometry Porto Conte, Alghero, Sardinia, Italy, May 27-June 1, 2005.
Search in Google Scholar
[4] BUCHBERGER, B.: An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal. PhD. Thesis, Univ. of Innsbruck, Math. Inst., Innsbruck, 1965.
Search in Google Scholar
[5] BUCHBERGER, B.: A theoretical basis for the reduction of polynomials to canonicalforms, ACM SIGSAM Bull. 10 (1976), no. 3, 19-29.
Search in Google Scholar
[6] BUCHBERGER, B.: Some properties of Gröbner-bases for polynomial ideals, in: ACM SIGSAM Bull. 10 (1976), no. 4, 19-24.
Search in Google Scholar
[7] BUCHBERGER, B.: A criterion for detecting unnecessary reductions in the constructionof Gröbner bases, in: Proc. of EUROSAM ’79, An International Symposiumon Symbolic and Algebraic Computation (W. Ng. Edward, ed.), Lecture Notes in Comput. Sci., Vol. 72, Springer-Verlag, Berlin, 1979, pp. 3-21.10.1007/3-540-09519-5_52
Search in Google Scholar
[8] DE CANNIERE, C.-PRENEEL, B.: Trivium specifications, http://www.ecrypt.eu.org/stream/.
Search in Google Scholar
[9] CHEON, J. H.-LEE, D. H.: Resistance of S-Boxes against Algebraic Attacks, in: Fast Software Encryption-FSE ’04, 11th Internat. Workshop (B. Roy et al., eds.), Lecture Notes in Comput. Sci., Vol. 3017, Springer-Verlag, Berlin, 2004, pp. 83-94.
Search in Google Scholar
[10] CID, C.-MURPHY, S.-ROBSHAW, M.: Small Scale variants of the AES, in: Fast Software Encryption-FSE ’05, 12th Internat. Workshop (H. Glibert et al., eds.), Lecture Notes in Comput. Sci., Vol. 3557, Springer-Verlag, Berlin, 2005, pp. 145-162.
Search in Google Scholar
[11] COURTOIS, N.-PIEPRZYK, J. : Cryptanalysis of block ciphers with overdefined systemsof equations, in: Advances in Cryptology-ASIACRYPT ’02, 8th Internat. Conference on the Theory and Application of Cryptology and Information Security (Y. Zheng, ed.), Lecture Notes in Comput. Sci., Vol. 2501, Springer-Verlag, Berlin, 2002, pp. 267-287.
Search in Google Scholar
[12] COURTOIS, N.-KLIMOV, A.-PATARIN, J.-SHAMIR, A.: Efficient algorithms forsolving overdefined systems of multivariate equations, in: Advances in Cryptology- -EUROCRYPT ’00, Internat. Conference on the Theory and Application of Cryptographic Techniques (B. Preneel, ed.), Lecture Notes in Comput. Sci., Vol. 1807, Springer-Verlag, Berlin, 2000, pp. 392-407.
Search in Google Scholar
[13] BARD, G. V.-COURTOIS, N. T.-JEFFERSON, C.: Efficients methods for conversionand solution of sparse systems of low-degree multivariate polynomials over GF(2) viaSAT-solvers, http://eprint.iacr.org/2007/024.
Search in Google Scholar
[14] BARD, G. V.-COURTOIS, N. T.: Algebraic cryptanalysis of the data encryption standard, in: Cryptography and Coding, 11th IMA Internat. Conference (S. Galbraith, (ed.), Lecture Notes in Comput. Sci., Vol. 4887, Springer-Verlag, Berlin, 2007, pp. 152-169, http://eprint.iacr.org/2006/402.
Search in Google Scholar
[15] DANTSIN, E.-GOERDT, A.-HIRSCH, E. A.-KANNAN, R.- KLEINBERG, J.- -PAPADIMITRIOU, C. H.-RAGHAVAN, P.-SCH¨ONING, U.: A deterministic (2− 2 k+1)n algorithm for k-SAT based on local search, Theoret. Comput. Sci. 289 (2002), 69-83.10.1016/S0304-3975(01)00174-8
Search in Google Scholar
[16] DAVIS, M.-PUTNAM, H.: A computing procedure for quantification theory, J. Assoc. Comput. Mach. 7 (1960), 201-215.10.1145/321033.321034
Search in Google Scholar
[17] DAVIS, M.-LOGEMANN, G.-LOVELAND, D.: A machine program for theorem proving, Commun. ACM 5 (1962), 394-397.10.1145/368273.368557
Search in Google Scholar
[18] FAUGÈRE, J. C.: A new efficient algorithm for computing Gröbner bases(F4), J. Pure Appl. Algebra 139 (1999), 61-88.10.1016/S0022-4049(99)00005-5
Search in Google Scholar
[19] FAUGÈRE, J. C.: A new efficient algorithm for computing Gröbner basis without reductionto zero (F5), in: Symbolic and Algebraic Computation-ISSAC ’02, Internat. Symposium (T. Mora, ed.), ACM Press, New York, NY, 2002, pp. 75-83.10.1145/780506.780516
Search in Google Scholar
[20] FAUGÈRE, J. C.-JOUX, A.: Algebraic cryptanalysis of hidden field equation (HFE)cryptosystems using Gröbner bases, in: Advances in Cryptology-CRYPTO ’03, 23rd Annual Internat. Cryptology Conference (D. Boneh, ed.), Lecture Notes in Comput. Sci., Vol. 2729, Springer-Verlag, Berlin, 2003, pp. 44-60.
Search in Google Scholar
[21] GEBAUER, R.-MÖLLER, H. M.: On an installation of Buchberger’s algorithm, J. Symbolic Comput. 6 (1988), 275-286.10.1016/S0747-7171(88)80048-8
Search in Google Scholar
[22] GEISELMANN, W.-MATHEIS, K.-STEINWANDT, R.: PET SNAKE: A special purposearchitecture to implement an algebraic attack in hardware, http://eprint.iacr.org/2009/222.10.1007/978-3-642-17499-5_12
Search in Google Scholar
[23] IWAMA, K.: Worst-case upper bounds for kSAT, Bull. EATCS 82 (2004), 61-71.
Search in Google Scholar
[24] JOUX, A.-VITSE, V.: A variant of the F4 algorithm, http://eprint.iacr.org/2010/158.10.1007/978-3-642-19074-2_23
Search in Google Scholar
[25] KUMAR, S.-PAAR, C.-PELZL, J.-PFEIER, G.-SCHIMMLER, M.: Breaking cipherswith Copacobana-a cost-optimized parallel code breaker, Lecture Notes in Comput. Sci., Vol. 4249, Springer-Verlag, Berlin, 2006, pp. 101-118.
Search in Google Scholar
[26] KWAN, M.: Reducing the gate count of bitslice DES, http://eprint.iacr.org/2000/051.
Search in Google Scholar
[27] LAZARD, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraicequations, in: Computer Algebra-EUROCAL ’83, Proc. Conf., London 1983, Lect. Notes Comput. Sci., Vol. 162, Springer-Verlag, Berlin, 1983, pp. 146-156.10.1007/3-540-12868-9_99
Search in Google Scholar
[28] MARQUES-SILVA, J. P.-SAKALLAH, K. A.: GRASP: a search algorithm for propositionalsatisfiability, IEEE Trans. Comput. 48 (1999), 506-521.10.1109/12.769433
Search in Google Scholar
[29] PAPADIMITRIOU, C. H.: On selecting a satisfying truth assignment, in: Proc. of FOCS ’91, 32nd Annual Symposium of Foundations of Computer Science, IEEE Comput. Soc., Washington, DC, USA, 1991, pp. 163-169.
Search in Google Scholar
[30] PATURI, R.-PUDLÁK, P.-SAKS, M. E.-ZANE, F.: An improved exponential-timealgorithm for k-SAT, J. ACM 52 (2005), 337-364.10.1145/1066100.1066101
Search in Google Scholar
[31] RADDUM, H.: Solving non-linear sparse equation systems over GF(2) using graphs, University of Bergen, 2004 (preprint).
Search in Google Scholar
[32] RADDUM, H.-SEMAEV, I.: New technique for solving sparse equation systems, http://eprint.iacr.org/2006/475.
Search in Google Scholar
[33] RADDUM, H.-SEMAEV, I.: Solving multiple right hand sides linear equations, Des. Codes Cryptogr. 49 (2008), 147-160, extended abstract in: Proc. of WCC ’07, Versailles, France, INRIA, 2007.
Search in Google Scholar
[34] RADDUM, H.: MRHS equation systems, in: Selected Areas in Cryptography-SAC ’07, 14th Internat. Workshop (C. Adams et al., eds.), Lecture Notes in Comput. Sci., Vol. 4876, Springer-Verlag, Berlin, 2007, pp. 232-245.
Search in Google Scholar
[35] SCHILLING, T. E.-RADDUM, H.: Solving equation systems by agreeing and learning, in: WAIFI ’10, 2010 (to appear).10.1007/978-3-642-13797-6_11
Search in Google Scholar
[36] SCHOONEN, A. C. C.: Multiple Right-Hand Side Equations. A New Tool for Cryptanalysis. Master’s Thesis, Eindhoven Univ. of Technology, Eindhoven, 2008.
Search in Google Scholar
[37] SCHÖNING, U.: A probabilistic algorithm for k-Sat based on limited local search andrestart, Algorithmica 32 (2002), 615-623.10.1007/s00453-001-0094-7
Search in Google Scholar
[38] SEMAEV, I.: On solving sparse algebraic equations over finite fields, Des. Codes Cryptogr. 49 (2008), pp. 47-60.
Search in Google Scholar
[39] SEMAEV, I.: Sparse algebraic equations over finite fields, SIAM J. Comput. 39 (2009), 388-409.10.1137/070700371
Search in Google Scholar
[40] SEMAEV, I.: Multiple side linear equations and circuit lattices, http://conf.fme.vutbr.cz/cecc09/lectures/semaev.pdf.
Search in Google Scholar
[41] SEMAEV, I.: Sparse Boolean equations and circuit lattices, Des. Codes Cryptogr., 2010 (to appear).10.1007/s10623-010-9465-x
Search in Google Scholar
[42] SEMAEV, I.: Improved Agreeing-Gluing algorithm, http://eprint.iacr.org/2010/140.
Search in Google Scholar
[43] YANG, B.-Y.-CHEN, J-M.-COURTOIS, N.: On asymptotic security estimates in XLand Gr¨obner bases-related algebraic cryptanalysis, in: Information and Communications Security-ICICS ’04, 6th Internat. Conference (J. Lopez et al., eds.), Lecture Notes in Comput. Sci., Vol. 3269, Springer-Verlag, Berlin, 2004, pp. 401-413.
Search in Google Scholar
[44] WANGDUE, R.:Multiple Side Linear Equations: A New Tool for Solving Sparse AlgebraicEquations in Finite Field, Master Thesis, University of Bergen, Bergen, 2010.
Search in Google Scholar
[45] WIEDEMANN, D. H.: Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), 54-62.10.1109/TIT.1986.1057137
Search in Google Scholar
[46] ZAKREVSKIJ, A.-VASILKOVA, I.: Reducing large systems of Boolean equations, in: 4th Internat. Workshop on Boolean Problems, Freiberg University of Mining and Technology, Freiberg, 2000, pp. 21-28.
Search in Google Scholar
[47] ZHANG, L.-MALIK, S.: The quest for efficient Boolean satisfiability solvers, Lecture Notes in Comput. Sci., Vol. 2404, Springer-Verlag, Berlin, 2002, pp. 17-36.
Search in Google Scholar

Methods to solve algebraic equations in cryptanalysis

Abstract

Paradigm

My account