Some Lower Bounds on the Algebraic Immunity of Functions Given by Their Trace Forms

The algebraic immunity of a Boolean function is a parameter that characterizes the possibility to bound this function from above or below by a nonconstant Boolean function of a low algebraic degree. We obtain lower bounds on the algebraic immunity for a class of functions expressed through the inversion operation in the field GF(2(n)), as well as for larger classes of functions defined by their trace forms. In particular, for n >= 5, the algebraic immunity of the function Tr-n (x(-1)) has a lower bound left perpendicular 2 root n + 4 right perpendicular - 4, which is close enough to the previously obtained upper bound left perpendicular root n right perpendicular + inverted right perpendicular root n/ left perpendicular root n right perpendicular inverted left perpendicular - 2. We obtain a polynomial algorithm which, give a trace form of a Boolean function f, computes generating sets of functions of degree <= d for the following pair of spaces. Each function of the first (linear) space bounds f from below, and each function of the second (affine) space bounds f from above. Moreover, at the output of the algorithm, each function of a generating set is represented both as its trace form and as a polynomial of Boolean variables.