This article is cited in
4 papers
Information Protection
Some Lower Bounds on the Algebraic Immunity of Functions Given by Their Trace Forms
V. V. Bayev M. V. Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics
Abstract:
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.
UDC:
21.391.1:004.7
Received: 15.12.2006
Revised: 27.03.2008
Fulltext:
PDF file (1388 kB)
