Cross-Correlation Analysis of Cryptographically Useful Boolean Functions and S-Boxes

We use the cross-correlation function as a fundamental tool to study cryptographic properties of Boolean functions. This provides a unified treatment of a large section of Boolean function literature. In the process we generalize old results and obtain new characterizations of cryptographic properties. In particular, new characterizations of bent functions and functions satisfying propagation characteristics are obtained in terms of the cross-correlation and auto-correlation properties of subfunctions. The exact relationship between the algebraic structure of the non-zeros of the spectrum and the auto-correlation values is obtained for a cryptographically important class of functions. Finally we study the suitability of S-boxes in stream ciphers and conclude that currently known constructions for S-boxes may not be adequate for such applications. Received April 27, 2001, and in revised form October 30, 2001. Online publication February 20, 2002.