Construction of balanced rotation symmetric boolean functions with optimal algebraic immunity

Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents one main result to find balanced rotation symmetric Boolean functions with maximum algebraic immunity. Through swapping the values of two orbits of rotation class of the majority function, a class of 4k+1 variable Boolean functions with maximum algebraic immunity is constructed. The function f(x) we construct always has terms of degree n-2 independence of what ever n is. And the nonlinearity of f(x) is relatively good for large n.