Rotation symmetric Boolean functions which are invariant under the action of cyclic group have been used in many different cryptosystems. This paper presents a new construction of balanced odd-variable rotation symmetric Boolean functions with optimum algebraic immunity. It is checked that, at least for some small variables, such functions have very good behavior against fast algebraic attacks. Compared with some known rotation symmetric Boolean functions with optimum algebraic immunity, the new construction has really better nonlinearity. Further, the algebraic degree of the constructed functions is also high enough.

To resist algebraic and fast algebraic attacks, Boolean functions used in stream ciphers should have optimal algebraic immunity and good fast algebraic immunity. One challenge of cryptographic Boolean functions is to determine their ability to resist fast algebraic attacks, which can be measured by their fast algebraic immunities. In this letter, we determine the exact values of fast algebraic immunity of the majority function of 2m and 2m+1 variables. This is the first time that the exact values of the fast algebraic immunity of an infinite class of symmetric Boolean functions with optimal algebraic immunity are determined.