More Balanced Boolean Functions With Optimal Algebraic Immunity and Good Nonlinearity and Resistance to Fast Algebraic Attacks

Abstract

In this paper, three constructions of balanced Boolean functions with optimal algebraic immunity are proposed. It is checked that, at least for small numbers of input variables, these functions have good behavior against fast algebraic attacks as well. Other cryptographic properties such as algebraic degree and nonlinearity of the constructed functions are also analyzed. Lower bounds on the nonlinearity are proved, which are similar to the best bounds obtained for known Boolean functions resisting algebraic attacks and fast algebraic attacks. Moreover, it is checked that for the number <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> of variables with 5 ≤ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ≤ 19, the proposed <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> -variable Boolean functions have in fact very good nonlinearity.