On the immunity of rotation symmetric Boolean functions against fast algebraic attacks

In this paper, an efficient algorithm is proposed to estimate the immunity of rotation symmetric Boolean functions against fast algebraic attacks. The algorithm is true-biased and almost always outputs the correct answer. Besides, it is shown that an n-variable rotation symmetric Boolean function f with n even but not a power of 2 admits a rotation symmetric function g of degree at most e≤n/3 such that the product gf has degree at most n−e−1.