On Algebraic Immunity And Extended Algebraic Immunity Of Boolean Functions

Boolean functions are important components of block ciphers, stream ciphers and Hash functions. The cryptographic criteria of Boolean functions are crucial to the security of cryptographic algorithms. The algebraic attack on stream ciphers has become a standard attack, although which has been proposed only a few years. The research on algebraic attacks provides a new necessary cryptographic property: algebraic immunity, for Boolean functions to be used in keystream generators. Possessing optimum algebraic immunity is a necessary criteria for Boolean functions used in stream ciphers against algebraic attacks. Extended algebraic immunity extends the concept of algebraic immunity, which enhances the request of abilitities of Boolean functions against algebraic attacks.In this thesis, the recent constructions of Boolean functions with maximum algebraic immunity (MAI) are reviewed at first, and those constructions are classified into several different classes by the construction idea. Further, some results and developments of these methods are also presented. Then, the enumeration of Boolean functions with MAI is investigated, and a new lower bound on the number of even-variable Boolean functions with MAI is provided, this lower bound is better than all the previous ones. At last, extend algebraic immunity of Boolean functions are investigated, and some results are gained. Firstly, a sufficient and necessary condition is presented that algebraic immunity of a Boolean function equals to its extended algebraic immunity. Secondly, it is proved that two classes of Boolean functions with maximum algebraic immunity also have optimal extended algebraic immunity. Finally, the structure of the annihilators of Boolean functions is analyzed with the algebraic complement.