Some lower bounds on the algebraic immunity of functions given by their trace forms
Vladimir Bayev · Problems of Information Transmission · 2008
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 ⌊2√n + 4⌋ − 4, which is close enough to the previously obtained upper bound ⌊√n⌋ + ⌈n/⌊√n⌋⌉ − 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.