Algorithm To Solve System Of Low-Degree Multivariate Polynomial Equations And Its Cryptographic Application

Algebraic attack is proposed recently as a new cryptanalysis method, which adds a new criterion for the safety of many cryptosystems .And also, the execution of algebraic attack depends on the algorithm of solving systems of low-degree multivariate polynomial equations. This makes the study on solving systems of low-degree multivariate polynomial equations a hot topic in cryptography.XL (extended linearization) is a equation-solving algorithm proposed by Courtois and Pieprzyk, which is used as direct attacks against multivariate Public-Key Cryptosystems and used in the attacks on stream cipher lately .XL produce lots excrescent equations in solving process, which increase the complexity of computation. In this paper, the XL algorithm on solving the low-degree multivariate polynomial equations in GF(2) is discussed and improved. Based on our simulation, to solve same problem, the complexity of improved XL is decreased greatly.XSL algorithm is introduced for the cryptanalysis of block ciphers by Nicolas Courtois and Josef Pieprzyk, derived from XL. In this paper, the algorithm XSL is discussed and further reduced, is used for the cryptanalysis of ten rounds of Camellia-192 and Camellia-256 by two measures using 4-round distinguishes or not. The Complexity of the attack is 2^177.81 and 2^165.42 operations on GF(2) respectively.With the appearance of algebraic attack, some new criterions for design of cryptstems are added. The Boolean function is a very important composition of stream ciphers, whose properties affect straightly the safety of cryptosystems. So, it is very important to study the algebraic immunity. In this paper, the relation between the algebraic immunity and other properties of Boolean is discussed, and a sufficient condition judging a Boolean function has low algebraic immunity is proposed. Then the algebraic immunity of Boolean function obtained from several classical constructions is discussed.