Analysis Of Algebraic Immunity On Boolean Function And Construction Of MAI Function

Boolean function is an important tool in implementing cipher systems.The studyof Boolean functions attributes to its safety index analysis.The emergence of algebraicattacks proposed a new security requirement for Boolean functions. In order to resistalgebraic attack, Meier etc proposed the concept of algebraic immunity.Algebraicimmunity had made a new task for the analysis and construction of booleanfunctions.Algebraic immunity is a new security standard which used to measure theability of boolean functions against algebraic attacks.The greater the algebraicimmunity,the stronger the Boolean function against algebraic attacks.Sincethen,Courtois and Meier prove the optimum algebraic immunity of n-variable booleanfunction is [n/2].Said optimum algebraic immunity function as MAI function.Recently,the study of the algebraic immunity of Boolean functions and the construction of MAIfunction has been the focus of research.In this paper, Firstly,based on algebraic immunity of boolean functions,we starteda full discussion of the relationship between algebraic immunity and its annihilator,therelations of algebraic immunity with other characteristics of boolean function.Thencomparing two construction algorithms of annihilator,we integrated analysis results,gota better conclusion;Secondly,we comparatively analyzed two construction methods ofoptimum algebraic immunity function and proved the equivalence consistency of thetwo construction algorithm; Thirdly,based on rotation symmetric functions and even-variable symmetric functions,we respectively gave a construction method of MAIfunction,then showed the constructed function had good balance,algebraic degree andnonlinearity.Finally,using the properties of concatenation,two calsses of booleanfunctions with optimal algebraic immunity were presented.we also showed the relationof algebraic immunity between the constructed function and its element functions.Moreover,some other cryptographic properties,such as algebraic degree,balance,andnonlinearity of the constructed function were ascertained.Finally, under concatenation,we concluded that the algebraic immunity of ith-constructed function has improvedsignificantly compared that of first order construction function.