Research On The Algebraic Immune Properties Of Boolean Function

Since algebraic attack method was proposed by Gallo cryptographist N.Courtois in 2003, it had been extensively used to analyze various cryptogram algorithms. The algebraic immune capability of Boolean function in cryptogram algorithm has already become an important criteria to judge the cryptographic capability of Boolean function.At present, the most successful examples of using algebraic attack on cryptogram algorithms are the attacks on stream ciphers Toyocrypt and LILI-128. Paper [4] has successfully broken out the two algorithms by building up some low-degree equations concerning inputs, outputs and keywords, using the low-degree annihilators of the nonlinear Boolean functions in the two algorithms. The same amount of low-degree annihilators are also found in the complementary functions of the nonlinear functions in the two algorithms. Consequently, double equations as paper[4] can be built up to reduce half the quantity of pairs of plain-ciphertext used to attack the two algorithms.To break out the cryptogram algorithms whose parameter of safety lies on the nonlinearity Boolean function using algebraic attack, what is the most important factor of attack efficiency is to find out the low-degree annihilators of the nonlinear Boolean functions. Making a good use of the relation between the logic border elements in the support set and the algebraic degree of the Boolean function, we got a new method to work out the low-degree annihilators of the Boolean function, called Karnargh Graphics Method. Its dissimilarity and affiliation to some typical methods used currently are expounded in the paper.The algebraic immunity (AI) of Boolean function is the significant index for Boolean function's capacity to resist algebraic attack. This thesis gives the change of the AI of new function, when it is combined by two Boolean functions adding mutually, and the change of the AI of new function, when it is combined by some Boolean functions concatenating together. Meanwhile, we analyze how the two function-combining modes work on proportioning the other cryptographic properties. In addition, this paper shows the relationship between AI and other cryptographic properties, such as Hamming Weight, nonlinearity, correlation immunity etc.Boolean function with maximum AI is one of the most effective Boolean functions to resist algebraic attack. This paper proves that the annihilators with algebraic degree at AI exist both in the balance Boolean function with maximum AI and its complementary function. We have also talked about a sort of Boolean function with maximum AI called select-more function, and studied its balance, symmetry, Walsh transform, self-correlation, nonlinearity and correlation immunity etc. Three methods of construction of Boolean function with maximum AI are mentioned in this paper, and some other cryptographic properties of the three construction functions are unfolded as emphases.