Research On Algebraic Immunity Of Boolean Functions

In recent years, algebraic attack is considered as the most important breach of cryptoanalysis. The main characteristic of algebraic attack is that it reduces the safety problem of cryptographic algorithm to the problem of solving an over-defined equations system with high degrees (There are more equations than variants in the system). People make some works on how to generate and solve an over-defined equations system and achieve some results on it. Algebraic attack has turned into an important and mature analysis method. Due to its generality, algebraic attack poses potential threats upon public-key cipher, block cipher and stream cipher. This is especially true for stream ciphers based on LFSR. Algebraic attack has made significant effect on the analysis of a cipher system.The non-linear parts of both block cipher and stream cipher can be realized by Boolean function. The cryptography properties of Boolean fuctions affect the security of a cipher derectly. As a new important cryptanalysis method, algebraic attack brings forth a new requirement for the design of Boolean functions, algebraic immunity. Alebraic attack makes the cipher analysis techmology diversiform. It is quite different from former analytical methods which were mostly based on the idea of probability. At present, the research to algebraic immunity of Boolean functions main include three aspects: the methods of determining the existence of the low-degree annihilator and calculating the algebraic immunity of a Boolean function, the construction of Optimal Algebraic Immunity Boolean Function and some of its cryptographic properties.The main object of this dissertation is to study the algebraic immunity of Boolean functions, the main results are as follows:1. By using the algebraic structure of a Boolean function's character matrix, obtain the interdependent relation between the normality and algebraic immunity of Boolean functions, a relatively high normality of Boolean function guarantees the existence of a low-degree annihilator, thus, the algebraic immunity of Boolean function can be determined by figuring out its normality, get the equivalent criteria when the algebraic immunity is 1 and 2.2. By making use of the relation between the algebraic degree and Hamming Weights of Boolean function and the fact that Boolean function, find that if we let the offset of a n-variables Boolean function 0/ limits on a sequence of affine subspaces, we always have new Boolean functions with degree >k, we determine the function/has no annihilator with degree