On the efficiency of solving Boolean polynomial systems with the characteristic set method. (English) Zbl 1468.68337

Summary: An improved characteristic set algorithm for solving Boolean polynomial systems is proposed. This algorithm is based on the idea of converting all the polynomials into monic ones by zero decomposition, and using additions to obtain pseudo-remainders. Three important techniques are applied in the algorithm. The first one is eliminating variables by new generated linear polynomials. The second one is optimizing the strategy of choosing polynomial for zero decomposition. The third one is to compute add-remainders to eliminate the leading variable of new generated monic polynomials. By analyzing the depth of the zero decomposition tree, we present some complexity bounds of this algorithm, which are lower than the complexity bounds of previous characteristic set algorithms. Extensive experimental results show that this new algorithm is more efficient than previous characteristic set algorithms for solving Boolean polynomial systems.


68W30 Symbolic computation and algebraic computation
13P15 Solving polynomial systems; resultants
68W40 Analysis of algorithms
Full Text: DOI arXiv


[1] Albrecht, M. R.; Cid, C., Cold boot key recovery by solving polynomial systems with noise, (ACNS (2011)), 57-72
[2] Aubry, P.; Lazard, D.; Maza, M. M., On the theory of triangular sets, J. Symb. Comput., 25, 105-124 (1999) · Zbl 0943.12003
[3] Bard, G. V.; Courtois, N. T.; Jefferson, C., Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF (2) via SAT-solvers (2007), IACR Cryptology ePrint Archive 24
[4] Bardet, M.; Faugere, J. C.; Salvy, B., Complexity of Gröbner Basis Computation for Semi-Regular Overdetermined Sequences over F2 with Solutions in F2 (2003), INRIA report RR-5049
[5] Bardet, M.; Faugère, J. C.; Salvy, B., On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, (Proc. ICPSS’04 (International Conference on Polynomial System Solving) (2004)), 71-75
[6] Bardet, M., Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie (2004), Université Paris VI, Decomber, Phd Thesis
[7] Bardet, M.; Faugère, J.-C.; Salvy, B.; Yang, B.-Y., Asymptotic behaviour of the degree of regularity of semi-regular quadratic polynomial systems, (Eighth International Symposium on Effective Methods in Algebraic Geometry. Eighth International Symposium on Effective Methods in Algebraic Geometry, MEGA 2005 (2005))
[8] Bardet, M.; Faugère, J. C.; Salvy, B.; Spaenlehauer, P. J., On the complexity of solving quadratic boolean systems, J. Complex., 29, 1, 53-75 (2013) · Zbl 1255.65090
[9] Bettale, L.; Faugere, J. C.; Perret, L., Hybrid approach for solving multivariate systems over finite fields, J. Math. Cryptol., 3, 3, 177-197 (2009) · Zbl 1183.94021
[10] Biere, A., Linear algebra, Boolean rings and resolution, (ACA’08. ACA’08, July, Austria (2008))
[11] Bogdanov, A.; Knudsen, L. R.; Leander, G.; Paar, C.; Poschmann, A.; Robshaw, M. J.; Seurin, Y.; Vikkelsoe, C., PRESENT: an ultra-lightweight block cipher, (Cryptographic Hardware and Embedded Systems - CHES 2007 (2007), Springer: Springer Berlin, Heidelberg), 450-466 · Zbl 1142.94334
[12] Borghoff, J.; Knudsen, L. R.; Stolpe, M., Bivium as a mixed-integer linear programming problem, (IMA International Conference on Cryptography and Coding (2009), Springer: Springer Berlin, Heidelberg), 133-152 · Zbl 1234.94031
[13] Borghoff, J.; Knudsen, L. R.; Leander, G.; Tomsen, S. S., Slender-set differential cryptanalysis, J. Cryptol., 26, 1, 11-38 (2013) · Zbl 1291.94060
[14] Bouillaguet, C.; Chen, H.-C.; Cheng, C.-M.; Chou, T.; Niederhagen, R.; Shamir, A.; Yang, B.-Y., Fast exhaustive search for polynomial systems in \(\mathbb{F}_2\), (CHES 2010. CHES 2010, LNCS, vol. 6225 (2010), Springer: Springer Heidelberg), 203-218 · Zbl 1297.94055
[15] Boulier, F.; Lazard, D.; Ollivier, F.; Petitiot, M., Representation for the radical of a finitely generated differential ideal, (Proc. of ISSAC’95 (1995), ACM Press: ACM Press New York), 158-166 · Zbl 0911.13011
[16] Bouziane, D.; Kandri Rody, A.; Maârouf, H., Unmixed-dimensional decomposition of a finitely generated perfect differential ideal, J. Symb. Comput., 31, 631-649 (2001) · Zbl 1038.12005
[17] Brickenstein, M.; Dreyer, A., PolyBoRi: a framework for Gröbner-basis computations with Boolean polynomials, J. Symb. Comput., 44, 9, 1326-1345 (2009) · Zbl 1186.68571
[18] Canteaut, A.; Filiol, E., Ciphertext only reconstruction of stream ciphers based on combination generators, (Fast Software Encryption. Fast Software Encryption, LNCS, vol. 1978 (2000), Springer), 165-180 · Zbl 0999.94543
[19] Chai, F.; Gao, X. S.; Yuan, C., A characteristic set method for solving Boolean equations and applications in cryptanalysis of stream ciphers, J. Syst. Sci. Complex., 21, 2, 191-208 (2008) · Zbl 1201.94080
[20] Chou, S. C., Mechanical Geometry Theorem Proving (1988), D. Reidel: D. Reidel Dordrecht · Zbl 0661.14037
[21] Chou, S. C.; Gao, X. S., Ritt-Wu’s decomposition algorithm and geometry theorem proving, (Proc. of CADE-10. Proc. of CADE-10, LNAI, vol. 449 (1990), Springer), 207-220 · Zbl 0708.68062
[22] Courtois, N.; Klimov, A.; Patarin, J.; Shamir, A., Efficient algorithms for solving over-determined systems of multivariate polynomial equations, (EUROCRYPT 2000. EUROCRYPT 2000, LNCS, vol. 1807 (2000)), 392-407 · Zbl 1082.94514
[23] Courtois, N., Higher order correlation attacks, XL algorithm, and cryptanalysis of toyocrypt, (ICISC. ICISC, LNCS, vol. 2587 (2002), Springer), 182-199 · Zbl 1031.94515
[24] Cook, S., 2004. From satisfiability to proof complexity and bounded arithmetic. In: SAT 2004, Invited Talk, Vancouver, Canada, 10-13 May.
[25] Cook, S.; Nguyen, P., Logical Foundations of Proof Complexity (2010), Cambridge University Press · Zbl 1206.03051
[26] Cox, D.; Little, J.; O’shea, D., Ideals, Varieties, and Algorithms (1992), Springer: Springer New York
[27] Dahan, X.; Maza, M. M.; Schost, E.; Wu, W.; Xie, Y., Lifting techniques for triangular decompositions, (Proc. ISSAC’05 (2005), ACM Press: ACM Press New York), 108-115 · Zbl 1360.14146
[28] Eibach, T.; Pilz, E.; Völkel, G., Attacking bivium using SAT solvers, (Büning, H. K.; Zhao, X., Theory and Applications of Satisfiability Testing (SAT ’08). Theory and Applications of Satisfiability Testing (SAT ’08), Lecture Notes in Computer Science, vol. 4996 (2008), Springer-Verlag), 63-76 · Zbl 1138.68536
[29] Eibach, T.; Völkel, G., Optimising Gröbner bases on bivium, Math. Comput. Sci., 3, 2, 159-172 (2010) · Zbl 1205.94081
[30] Faugère, J. C., A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139, 1-3, 61-88 (1999) · Zbl 0930.68174
[31] Faugère, J. C., A new efficient algorithm for computing Gröbner bases without reduction to zero F5, (Proc. ISSAC 2002 (2002)), 75-83 · Zbl 1072.68664
[32] Faugère, J. C.; Ars, G., An Algebraic Cryptanalysis of Nonlinear Filter Generators Using Gröbner Bases (2003), INRIA, TR No. 4739
[33] Faugère, J. C.; Joux, A., Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases, (Boneh, Dan, Advances in Cryptology-CRYPTO 2003. Advances in Cryptology-CRYPTO 2003, LNCS, vol. 2729 (2003), Springer), 44-60 · Zbl 1122.94371
[34] Gallo, G.; Mishra, B., Efficient algorithms and bounds for Wu-Ritt characteristic sets, (Effective Methods in Algebraic Geometry (1991), Birkhäuser: Birkhäuser Boston), 119-142 · Zbl 0747.13019
[35] Gao, X. S.; van der Hoeven, J.; Yuan, C.; Zhang, G., Characteristic set method for differential-difference polynomial systems, J. Symb. Comput., 44, 9, 1137-1163 (2009) · Zbl 1169.13019
[36] Gao, X. S.; Huang, Z., Characteristic set algorithms for equation solving in finite fields, J. Symb. Comput., 47, 6, 655-679 (2012) · Zbl 1273.11176
[37] Gerdt, V.; Zinin, M., A pommaret division algorithm for computing Gröbner bases in Boolean rings, (Proc. ISSAC 2008 (2008), ACM Press) · Zbl 1185.68868
[38] Huang, Z.; Lin, D., Attacking bivium and trivium with the characteristic set method, (Progress in Cryptology-AFRICACRYPT 2011. Progress in Cryptology-AFRICACRYPT 2011, LNCS, vol. 6737 (2011)), 77-91 · Zbl 1280.94070
[39] Huang, Z., Parametric equation solving and quantifier elimination in finite fields with the characteristic set method, J. Syst. Sci. Complex., 25, 4, 778-791 (2012) · Zbl 1292.93047
[40] Huang, Z.; Lin, D., A new method for solving polynomial systems with noise over \(\mathbb{F}_2\) and its applications in cold boot key recovery, (Selected Areas in Cryptography. Selected Areas in Cryptography, Windsor, Canada. Selected Areas in Cryptography. Selected Areas in Cryptography, Windsor, Canada, LNCS, vol. 7707 (2013)), 16-33 · Zbl 1327.94051
[41] Huang, Z.; Lin, D., Solving polynomial systems with noise over F2: revisited, Theor. Comput. Sci., 676, 52-68 (2017) · Zbl 1370.68337
[42] Hubert, E., Factorization-free decomposition algorithms in differential algebra, J. Symb. Comput., 29, 641-662 (2000) · Zbl 0984.12004
[43] Joux, A.; Vanessa, V., A crossbred algorithm for solving Boolean polynomial systems, (International Conference on Number-Theoretic Methods in Cryptology (2017), Springer: Springer Cham)
[44] Kalkbrener, M., A generalized euclidean algorithm for computing triangular representations of algebraic varieties, J. Symb. Comput., 15, 143-167 (1993) · Zbl 0783.14039
[45] Kapur, D.; Wan, H. K., Refutational proofs of geometry theorems via characteristic sets, (Proc. ISSAC’90 (1990), ACM Press: ACM Press New York), 277-284
[46] Lazard, D., A new method for solving algebraic systems of positive dimension, Discrete Appl. Math., 33, 147-160 (1991) · Zbl 0753.13013
[47] Li, X.; Mou, C.; Wang, D., Decomposing polynomial sets into simple sets over finite fields: the zero-dimensional case, Comput. Math. Appl., 60, 11, 2983-2997 (2010) · Zbl 1207.13017
[48] Lin, D.; Liu, Z., Some results on theorem proving in geometry over finite fields, (Proc. ISSAC’93 (1993), ACM Press: ACM Press New York), 292-300 · Zbl 0922.03017
[49] Liu, G. Q.; Jin, C. H., Differential cryptanalysis of PRESENT-like cipher, Des. Codes Cryptogr., 76, 3, 385-408 (2015) · Zbl 1359.94613
[50] Minto, S., Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems, (Proc. ACM/IEEE Design Automation (1993), ACM Press), 272-277
[51] Möller, H. M., On decomposing systems of polynomial equations with finitely many solutions, Appl. Algebra Eng. Commun. Comput., 4, 217-230 (1993) · Zbl 0793.13013
[52] Raddum, H., Cryptanalytic Results on TRIVIUM, eSTREAM, ECRYPT Stream Cipher Project (2006), Report 2006/039
[53] Simonetti, I.; Faugère, J. C.; Perret, L., Algebraic attack against trivium, (First International Conference on Symbolic Computation and Cryptography, SCC 2008 (2008), LMIB: LMIB Beijing, China), 95-102
[54] Soos, M.; Nohl, K.; Castelluccia, C., Extending SAT solvers to cryptographic problems, (Kullmann, O., Theory and Applications of Satisfiability Testing - SAT 2009. SAT 2009. Theory and Applications of Satisfiability Testing - SAT 2009. SAT 2009, Lecture Notes in Computer Science, vol. 5584 (2009), Springer: Springer Berlin, Heidelberg)
[55] Sun, Y.; Huang, Z.; Lin, D.; Wang, D., On implementing the symbolic preprocessing function over Boolean polynomial rings in Gröbner basis algorithms using linear algebra, J. Syst. Sci. Complex., 29, 3, 789-804 (2016) · Zbl 1388.13057
[56] Szanto, A., Computation with Polynomial Systems (1999), Cornell University, Ph.D. Thesis
[57] Wang, D., An elimination method for polynomial systems, J. Symb. Comput., 16, 83-114 (1993) · Zbl 0803.13016
[58] Wu, W. T., Basic principles of mechanical theorem-proving in elementary geometries, J. Autom. Reason., 2, 221-252 (1986) · Zbl 0642.68163
[59] Zhao, J.; Song, J.; Zhu, M.; Li, J.; Huang, Z.; Li, X.; Ren, X., PBCS: an efficient parallel characteristic set method for solving Boolean polynomial systems, (Proceedings of the 47th International Conference on Parallel Processing (2018), ACM), 23
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.