On Boolean Functions to Resist Algebraic Attacks

Certain properties of Boolean functions that are necessary to resist algebraic attacks are discussed. A necessary condition to resist algebraic attacks is that the function f should not have relations like fg=0 or (1+f)h=0, where g, h are nonzero functions of low degrees. The function g (resp. h) is called the annihilator of f (resp 1+f). "Algebraic Immunity(AI) of f" or, "AI(f)" is used to denote the minimum degree of the annihilators of f or 1+f. However, AI is not a sufficient condition to resist all kinds of algebraic attacks, but it is one of the most important necessary conditions. Some fundamental results like relationship between the AI and nonlinearity, the number of LI annihilators at certain degree, AI of some existing cryptographically significant functions are discussed. The first construction method to generate Boolean functions on n variables with highest possible AI is presented. Then a basic theory to generate a function with high AI is presented and is applied to construct. Other properties of these functions are studied. How the number of homogeneous linear equations, which by solving, the existence of d-degree annihilator is decided, can be reduced is analyzed.