Methods to solve algebraic equations in cryptanalysis

[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_52Search 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-8Search 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.321034Search 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.368557Search 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-5Search 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.780516Search 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-8Search 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_12Search 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_23Search 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_99Search 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.769433Search 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.1066101Search 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_11Search 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-7Search 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/070700371Search 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-xSearch 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.1057137Search 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