Research On Resistance Of Boolean Functions To Algebraic Attacks

It is considered for a long time to use nonlinear Boolean functions as thefilter functions (or combiner functions) in LFSR-based (Linear Feedback ShifterRegister-based) keystream generators. Nonlinear Boolean functions as the filterfunctions should have good cryptographic properties to resist all kinds of existedattacks. Therefore, to study cryptographic properties of Boolean functions isvery necessary and also interesting.In recent years, algebraic attacks (and fast algebraic attacks) on LFSR-based stream ciphers have been received widespread and profound attention. Theresearch on algebraic attacks provides a new necessary cryptographic properties:algebraic immunity, for Boolean functions to be used in keystream generators.Boolean functions as ?lter functions should have large algebraic immunity toresist algebraic attacks. Moreover, the existence of fast algebraic attacks makesmore strict demand on Boolean functions.This paper focuses on the resistance of Boolean functions to algebraic attacksand fast algebraic attacks. Firstly an existed construction of Boolean functionswith the maximum algebraic immunity is further studied. Then a method ofconcatenation construction of Boolean functions with the maximum algebraicimmunity is introduced. Some other cryptographic properties of some Booleanfunctions with the maximum algebraic immunity is analyzed. Finally the re-sistance of Boolean functions to fast algebraic attacks is discussed. The mainresults in this paper are as follows.The method of constructing odd variables Boolean functions with the max-imum algebraic immunity via finding invertible submatrixes in a given matrix,which is introduced by N.Li et al. , is further studied. It solves the problem toa certain degree that how to find invertible submatrixes more effectively in thegiven matrix.A concatenation property of Boolean functions with the maximum algebraicimmunity is observed. Then a method of concatenation construction is intro- duced, i.e. for even n, an (n + 1)-variable Boolean function with the maximumalgebraic immunity can be obtained from two n-variable Boolean functions withthe maximum algebraic immunity satisfying a given condition, furthermore an(n + 2)-variable Boolean function with the maximum algebraic immunity canbe also obtained from the same two n-variable Boolean functions as well as anyother two Boolean functions with the maximum algebraic immunity.The nonlinearity of Boolean functions with the maximum algebraic immu-nity and the maximum (or minimum) Hamming weight is determined.Boolean functions with a large number of independent annihilators helpbetter algebraic attack. The number of independent annihilators at lowest al-gebraic degree of Boolean functions with the maximum algebraic immunity isdetermined. In all Boolean functions with the maximum algebraic immunity,using even n-variable balanced functions can relatively negate the advantage foralgebraic attacks coming from a larger number of independent annihilators.An e?ective method of describing the resistance to fast algebraic attacks ofn-Boolean functions: e-fast algebraic immunity is introduced for the ?rst time,where 1≤e < ?n2?. e-fast algebraic immunity contains some properties ofalgebraic immunity. The su?cient and necessary condition of e-fast algebraicimmunity is given. With e-fast algebraic immunity the resistance of Booleanfunctions to fast algebraic attacks can be described more explicitly.An algorithm for determining e-fast algebraic immunity of Boolean func-tions is provided. Compared with the algorithm given by Armknecht et al. , insome specific cases, using this algorithm to decide the resistance to fast algebraicattacks of Boolean functions has better computation complexity, especially whendetermining whether a given Boolean function has the optimal resistance to fastalgebraic attacks.