Two Constructions Of Boolean Functions With Optimal Algebraic Immunity

Boolean functions play an important role in cryptographic systems and the cryptographic properties of the Boolean functions used in LFSR of stream ciphers determine the security of the systems. To resist various known attacks, the Boolean functions used in cryptographic systems should satisfy some cryptog-raphic criteria such as balance, high nonlinearity, high algebraic degree and proper correlation immunity.In recent years, the algebraic attacks and fast algebraic attacks attract much attention for many cryptographers. The idea is that the initial key bits can be characterized as the solutions of a system of multivariate equations and then by solving the system of nonlinear multivariate equations to get the initial key bits. A necessary condition to resist algebraic attacks is that the Boolean functions should have a high algebraic immunity. The optimum algebraic immunity of an n-variable Boolean function is [n/2]. A high algebraic immunity is a nec-essary but not sufficient condition for resistance against all kinds of alge-braic attacks. If one can find g of low degree and h≠0of reasonable degree such that f*g=h, then a fast algebraic attack(FAA) is feasible.In the present paper, two constructions of Boolean functions with optimal algebraic immunity are proposed. Our idea is to further apply the method deve-loped in previous papers and propose two constructions of Boolean functions. These functions are balanced and have optimal algebraic degree, maximal alge-braic immunity, high nonlinearity and good behavior against fast algebraic att-acks. The constructions also generalize previous ones respectively given by Rizomiliotis and Zeng et al.