Paper 2019/999

On the Fast Algebraic Immunity of Majority Functions

Pierrick Méaux

Abstract

In different contexts such as filtered LFSR, Goldreich's PRG, and FLIP stream ciphers, the security of a cryptographic primitive mostly depends on the algebraic properties of one Boolean function. Since the Seventies, more and more efficient attacks have been exhibited in this context, related to more and more general algebraic properties, such as the degree, the algebraic immunity, and finally, the fast algebraic immunity. Once the properties to estimate the attack complexities are identified, it remains to determine the exact parameters of interesting families of functions with these properties. Then, these functions can be combined in secondary constructions to guarantee the good algebraic properties of a main function. In particular, the family of symmetric functions, and more precisely the subclass of majority functions, has been intensively studied in the area of cryptography, because of their practical advantages and good properties. The degree of all these functions is known, and they have been proven to reach the optimal algebraic immunity, but still very few is known about its fast algebraic immunity. For a function in $n=2^m+j$ variables, an upper bound is known for all $m$ and $j$, proving that these functions do not reach the optimal fast algebraic immunity. However, the exact fast algebraic immunity is known only for very few families indexed by $j$, where the parameter is exhibited for all members of the family since $m$ is big enough. Recent works gave exact values for $j=0$ and $j=1$ (in the first case), and for $j=2$ and $j=3$ with $m\geq2$ (in the second case). In this work, we determine the exact fast algebraic immunity for all possible values of $j$, for all member of the family assuming $m\geq 1+\log_2(j+1)$.