Constructions of balanced odd-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity

Rotation symmetric Boolean functions have been used as components of different cryptosystems. In this paper, two classes of balanced rotation symmetric Boolean functions having optimal algebraic immunity on odd number of variables are constructed. We give a lower bound on the algebraic degree of the first class of functions, and prove that the n-variable functions in the second class has optimal algebraic degree if n≠2m+1 for m>2. Moreover, it is shown that both classes of functions have much better nonlinearity than all the previously obtained rotation symmetric Boolean functions with optimal algebraic immunity, and have good behavior against fast algebraic attacks at least for small numbers of input variables.