Constructing Boolean Functions With Potential Optimal Algebraic Immunity Based on Additive Decompositions of Finite Fields
This work addresses the need for secure cryptographic primitives by developing Boolean functions with enhanced algebraic properties, though it is incremental as it builds on existing conjectures and methods.
The authors tackled the problem of constructing Boolean functions with optimal algebraic immunity for cryptographic applications, proposing a method based on additive decompositions of finite fields that yields balanced functions with optimal algebraic degree, high nonlinearity, and potential optimal algebraic immunity under a generalized conjecture, with computer tests showing good resistance to fast algebraic attacks for small variable counts.
We propose a general approach to construct cryptographic significant Boolean functions of $(r+1)m$ variables based on the additive decomposition $\mathbb{F}_{2^{rm}}\times\mathbb{F}_{2^m}$ of the finite field $\mathbb{F}_{2^{(r+1)m}}$, where $r$ is odd and $m\geq3$. A class of unbalanced functions are constructed first via this approach, which coincides with a variant of the unbalanced class of generalized Tu-Deng functions in the case $r=1$. This class of functions have high algebraic degree, but their algebraic immunity does not exceeds $m$, which is impossible to be optimal when $r>1$. By modifying these unbalanced functions, we obtain a class of balanced functions which have optimal algebraic degree and high nonlinearity (shown by a lower bound we prove). These functions have optimal algebraic immunity provided a combinatorial conjecture on binary strings which generalizes the Tu-Deng conjecture is true. Computer investigations show that, at least for small values of number of variables, functions from this class also behave well against fast algebraic attacks.