An Infinite Class of Balanced Functions with Optimal Algebraic Immunity, Good Immunity to Fast Algebraic Attacks and Good Nonlinearity

After the improvement by Courtois and Meier of the algebraic attacks on stream ciphers and the introduction of the related notion of algebraic immunity, several constructions of infinite classes of Boolean functions with optimum algebraic immunity have been proposed. All of them gave functions whose algebraic degrees are high enough for resisting the Berlekamp-Massey attack and the recent Rønjom-Helleseth attack, but whose nonlinearities either achieve the worst possible value (given by Lobanov’s bound) or are slightly superior to it. Hence, these functions do not allow resistance to fast correlation attacks. Moreover, they do not behave well with respect to fast algebraic attacks. In this paper, we study an infinite class of functions which achieve an optimum algebraic immunity. We prove that they have an optimum algebraic degree and a much better nonlinearity than all the previously obtained infinite classes of functions. We check that, at least for small values of the number of variables, the functions of this class have in fact a very good nonlinearity and also a good behavior against fast algebraic attacks.