On the linear structure of symmetric Boolean functions.
Ed Dawson, Chuan-Kun Wu · 1997
It is shown in this paper that nonlinear symmetric Boolean functions have no other linear structures other than the all-zero and the all-one vectors. For such functions with n variables, it is shown that when n is odd, every such symmetric Boolean function is either a function with the all-one vector as an invariant linear structure or can be written as the product of two symmetric functions of which one has the all-one vector as an invariant linear structure and the other has the all-one vector as a complementary linear structure. In the case when n is even, it is shown that only 2 n 2 +1 of the symmetric Boolean functions have the all-one vector as an invariant linear structure and none has the all-one vector as a complementary linear structure. Key words: Symmetric Boolean function, Linear structure, Cryptology 1