On Some Necessary Conditions of Boolean Functions to Resist Algebraic Attacks
Deepak Kumar Dalai · 2006
In this thesis we discuss certain properties of Boolean functions that are necessary for resistance against algebraic and fast algebraic attacks. A Boolean function f(x1, . . . , xn) on n variables may be described as a multivariate polynomial over GF (2) and it is well known that its algebraic degree d should not be low if it has to be used as a primitive in a well designed cryptosystem. Recently, it has been noted that a necessary condition in resisting algebraic attack is as follows: the function f should not have a relation fg = h, where g, h are nonzero n-variable Boolean functions of low degrees. This condition boils down to the situation that the function f should not have relations like fh1 = 0 or (1 + f)h2 = 0, where h1, h2 are nonzero n-variable Boolean functions of low degrees. The function h1 (respectively h2) is called the annihilator of f (respectively 1 + f). The notation AIn(f) is used to denote the minimum degree of the annihilators of f or 1 + f . This is well known as “Algebraic Immunity” of the function f in literature. There are evidences that algebraic immunity is not a sufficient condition to resist against all kinds of algebraic attacks, but clearly it is one of the most important necessary conditions. The term “Annihilator Immunity” may be a more appropriate notation than “Algebraic Immunity”, but following the frequent use of the term “Algebraic Immunity” in currently available research materials, we use the term Algebraic Immunity in this thesis. It is known that AIn(f) ≤ dn2 e. Good nonlinearity is one of the most important properties of Boolean functions to be used in a cryptosystem. We present a fundamental relationship between the algebraic immunity and the nonlinearity of a Boolean function. We first relate the weight of a function with its algebraic immunity and then extend the result to show that if nl(f) d + 1 then nl(f) ≥ ∑d i=0 ( n i ) . Thus while choosing a function with good algebraic immunity, the nonlinearity of the function is lower bounded. The main idea (in proving these results) is based on solutions to a set of homogeneous linear equations. Using similar approach, given a Boolean function, we have also studied the number of linearly independent annihilators at the lowest possible degree. Further we have studied some existing constructions of cryptographically significant Boolean functions in terms of their algebraic immunity. As there was no known construction of Boolean function with maximum possible algebraic immunity, next we concentrate on that problem. So far, the attempt in designing Boolean functions with required algebraic immunity was only ad-hoc, i.e., the functions were designed keeping in mind the other cryptographic criteria, and then it has been checked whether the function can provide good algebraic immunity too. For the first time, we present a construction method to generate Boolean functions on n variables with highest possible