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\geq 5$, the algebraic immunity of the function $\mathrm{Tr}_n(x^{-1})$ has a lower bound $\lfloor 2\sqrt{n+4}\rfloor-4$, which is close enough to the previously obtained upper bound $\lfloor\sqrt{n}+\lceil n/\lfloor\sqrt{n}\rfloor\rceil-2$. We obtain a polynomial algorithm which, given a trace form of a Boolean function $f$, computes generating sets of functions of degree $leq 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.