Construction And Analysis Of Boolean Funtions Resistant To Algebraic Attacks

Recently, algebraic attacks have appeared as a powerful tool for cryptanalysis certainencryption schemes and particularly stream ciphers based on LFSRs. To measure the resistanceto algebraic attacks, a new cryptographic property of Boolean functions called algebraicimmunity has been proposed. To resist algebraic attacks, the Boolean functions must possessalgebraic immunity as high as possible. It is known that the algebraic immunity of an n-variableBoolean function is upper bounded by 「n/2」. If the algebraic immunity of an n-variable Booleanfunction arrives 「n/2」, then this Boolean function is called a Boolean function with optimalalgebraic immunity. Moreover, the existence of other improved algebraic attacks makes morestrict demand on Boolean functions.In this dissertation, we study the propertied of Boolean functions resistant to algebraicattacks and construct new Boolean functions with optimal algebraic immunity. The main resultsare as follows:1. We put forward a new method to construct n-variable Boolean functions with optimalalgebraic immunity based on the factorization of n. In particular, the trivial factorization n=n·1is also allowable. Besides, for a fix positive integer n, more factorizations of n are provided,more n-variable Boolean functions with optimal algebraic immunity can be obtained. Thealgebraic degree and the nonlinearity of a class of balanced Boolean functions constructed by thenew method are discussed, and computer investigations for small values of n indicate that theirnonlinearities are quite large and their behavior against fast algebraic attacks are good.2. For two kinds of Boolean functions, the relation between the minimum degree of allnonzero annihilators of a Boolean function and that of its complement is studied. For a Booleanfunction with optimal algebraic immunity, it is shown that the distance of the minimum degree ofitself and that of its complement is no more than one and whether its algebraic immunity equalsto the former or latter is merely related to the Hamming weight. For a decomposable function,the above relation is determined by the algebraic immunity of two subfunctions. From the aboveresults, lots of balanced Boolean functions satisfies the minimum degree of its all nonzeroannihilators equals to that of its complement have been attained.3. Recently, two classes of Boolean functions with optimal algebraic immunity have beenproposed by Carlet et al. and Wang et al., respectively. Although it appears that their methods arevery different, it is proved in this dissertation that the two classes of Boolean functions are in factaffine equivalent. Moreover, the number of affine equivalence classes of these functions is alsostudied, and an upper bound is given.4. The R njom-Helleseth attack and higher order algebraic attacks are two kind of improved algebraic attacks. We investigate the resistance of Boolean functions against the two improvedattacks and give properties Boolean functions should possess to resist these attacks. Besides, thealgebraic immunity of a special kind of Boolean functions is studies, and a lower bound is given.