Balanced 2p-variable rotation symmetric Boolean functions with optimal algebraic immunity

Rotation symmetric Boolean functions have been used as components of different cryptosystems. In this paper, based on the knowledge of compositions of an integer, a new construction of balanced 2p-variable rotation symmetric Boolean functions with optimal algebraic immunity is provided, where p is an odd prime. The nonlinearity of our new functions is significantly higher than all previously obtained balanced even-variable rotation symmetric Boolean functions with optimal algebraic immunity, and is higher than the best nonlinearity of even-variable rotation symmetric Boolean functions with optimal algebraic immunity in most cases. We also show that our new functions have high algebraic degree and a good behavior against fast algebraic attacks.