Construction Of Two Classes Of Boolean Functions With Optimal Algebraic Immunity

The algebraic attack is considered as one of the most important attack method in stream ciphers since it was proposed by Courtois and Merier in 2003. In 2004, Meier proposed a new concept of Boolean function against algebraic attacks named as algebraic immunity. Since then, the algebraic immunity of Boolean functions has become one of the most important criteria when constructing cryptographic Boolean functions. Courtois and Meier respectively obtained the upper bound of algebraic immunity, which is ??n2??. A Boolean function with optimal algebraic immunity is called an optimal algebraic immunity function.The optimal algebraic immune functions are studied in the dissertation. Two classes of Boolean functions with optimal algebraic immunity are proposed. The main results in the dissertation are as follows:(1) Su and Tang proposed a construction of rotation symmetric functions with optimal algebraic immunity based on the composition of positive integers. They also showed a linear expression of the given column vectors with respect to a basis of generator matrix of the Reed-Muller code. This expression is an important tool for constructing Boolean functions with optimal algebraic immunity function. This dissertation describes a new method on constructing Boolean functions with optimal algebraic immunity on both even and odd variables. It is proved that these functions also possess good nonlinearity, and the lower bound of nonlinearity is also given.(2) Tu and Deng had proposed a class of 1-resilient Boolean functions with optimal algebraic immunity and good nonlinearity based on finite fields. Combining Tu-Deng construction with the idea of Tang, a new construction of 1-resilient Boolean functions with optimal algebraic immunity is given in this dissertation. This class of functions are 1-resilient and possess optimal algebraic immunity.