Abstract:

Complementary symmetric Boolean functions are a special class of symmetric Boolean functions. A high proportion of symmetric Boolean functions with optimum algebraic immunity are complementary symmetric Boolean functions. Especially for the case of 2〖WTBX〗m〖WTBZ〗 variables, it reaches a high proportion of 2/3. By the relationship between the nonlinearity and the Walsh spectrum of the Boolean functions, and that between the Walsh spectrum of the Boolean functions and the Krawtchouk polynomial, the nonlinearity of complementary symmetric Boolean functions is determined. As a result, the nonlinearity of all complementary symmetric Boolean functions with n variables is2n－1－ 1/2(nn/2)。

Key words: nonlinearity;algebraic immunity;complementary symmetric Boolean function;symmetric Boolean function