Abstract

W. Millan, L. Burnett and G. Carter

The design of boolean functions with optimum combinations of cryptographic properties is considered from the perspective of direct construction in the Walsh-Hadamard domain. This approach, based upon internal analysis of the Discrete Fast Fourier Transform, is shown to provide transparent proofs of several significant results in the theory of boolean functions and, in addition, verifies the conformance of all boolean functions to Parseval's Theorem. Using a direct approach to the problem of constructing highly nonlinear functions, we are able to easily and quickly construct boolean functions possessing properties in some of the optimum combinations known to exist today. Moreover, it is shown how the direct Walsh Hadamard Transform approach, exploiting the computational butterfly structure, can be used in the pseudo-random generation of high quality boolean functions (in particular those combining highly nonlinear and correlation immune properties) and the potential application of this in symmetric cipher design is discussed. Finally, this paper presents our generic algorithm for direct generation of optimal boolean functions and demonstrates the effectiveness of our method.