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 nonlineari-ties are upper bounded by 2~(n-1) - ((n-1)/「n/2」) + 2(n - 6).