Efficient Search for Symmetric Boolean Functions under Constraints on Walsh Spectrum Values*

In this paper we present an efficient exhaustive search strategy on symmetric Boolean functions having the Walsh spectrum values constrained in a range at certain points. Exploiting the structure in Walsh spectrum of a symmetric Boolean function and its relationship with Krawtchouk matrix, we extend the concept of folded vectors and pruning introduced by Gathen and Roche in 1997. The strategy is applied to search for highly nonlinear symmetric Boolean functions and nonlinear symmetric resilient and correlation immune functions. We also experimentally justify that our method provides further efficiency than the search strategy presented by Gathen and Roche.