Efficient search for symmetric Boolean functions under constraints on Walsh spectra values

摘要: In this paper we present an efficient search strategy on symmetric Boolean functions having the Walsh spectra values constrained in a range at certain points. Exploiting the structure in Walsh spectra of a symmetric Boolean function, we extend the concept of folded vectors of a symmetric Boolean function introduced by von zur Gathen and Roche in 1997. We consider separate folding strategy at odd and even weight points and then use these folded vectors to get the exact functions. In application towards enumerating symmetric correlation immune functions (either balanced or unbalanced), we show that our method is more efficient than what had been proposed by von zur Gathen and Roche. We could experimentally check that there is no nonlinear symmetric 3 (or more) resilient function up to 256 variables and we could also enumerate all the nonlinear symmetric unbalanced 3rd order correlation immune functions up to 128 variables.