Constructing Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity on an Odd Number of Variables
It is well known that Boolean functions used in stream and block ciphers should have high algebraic immunity to resist algebraic attacks. Up to now, there have been many constructions of Boolean functions achieving the maximum algebraic immunity. In this paper, we present several constructions of rotation symmetric Boolean functions with maximum algebraic immunity on an odd number of variables which are not symmetric, via a study of invertible cyclic matrices over the binary field. In particular, we generalize the existing results and introduce a new method to construct all the rotation symmetric Boolean functions that differ from the majority function on two orbits. Moreover, we prove that their nonlinearities are upper bounded by 2(n-1) - ((n-1)(left perpendicularn/2right perpendicular)) + 2(n - 6).
rotation symmetric boolean function algebraic immunity algebraic attack nonlinearity invertible cyclic matrix