Algebraic Immunity in Boolean Functions (Methods)

Abstract

Boolean functions play an important role in designing any modern symmetric cipher. They can be utilized either as lter/combiner functions in LFSR based stream ciphers, or as s-box component functions in block ciphers. In order to design strong crypto-systems, cryptographers over the years have identi ed some basic cryptographic criteria for Boolean functions, which are required to be ful lled before applying them in practical systems. These basic cryptographic criteria include balanced-ness, algebraic degree, non-linearity, correlation immunity and algebraic immunity. Therefore, constructing Boolean functions, along with ful lling basic cryptographic criteria, has become a vital task for cryptographers. Considerable work has been achieved over the last few years for constructing Boolean functions, mainly focused on achieving optimal algebraic immunity. However, all existing methods lacks in ful lling all the cryptographic criteria other than algebraic immunity, due to some essential trade o s among various cryptographic criteria. Mostly construction methods are iterative in nature, which require more number of existing Boolean functions with at least optimal algebraic immunity, as their initial functions. Moreover, only theoretical constructions are found in literature, with very less or no implementation results. In this thesis, we have carried out comparative analysis of four existing ii iii methods for constructing Boolean functions with maximum algebraic immunity. These methods are not only e ciently implemented to construct Boolean functions, but are also analyzed in terms of ful lling basic cryptographic criteria. Additionally, these methods are evaluated in terms of higher order non-linearity up to n=5 variables. We have also presented a method to extend existing construction methods and construct 2n more number of Boolean functions with maximum algebraic immunity by using existing single Boolean function. We got successful results for two existing constructions, which include construction of Boolean functions using majority functions and construction through primitive polynomials. We have proved our results through experiments, up to n=12 variables; however no mathematical proof has been given and is left as future work.