On the Arithmetic Walsh Coefficients of Boolean Functions

Authors: Claude Carlet and Andrew Klapper
Andrew Klapper, 307 Marksbury, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0633, klapper at cs.uky.edu. www.cs.uky.edu/~klapper/andy.html

Appeared in: Designs, Codes and Cryptography.
Abstract We generalize to the arithmetic Walsh transform (AWT) some results which were previously known for the Walsh Hadamard transform of Boolean functions. We first generalize the classical Poisson summation formula to the AWT. We then define a generalized notion of resilience with respect to an arbitrary statistical measure of Boolean functions. We apply the Poisson summation formula to obtain a condition equivalent to resilience for one such statistical measure. Last, we show that the AWT of a large class of Boolean functions can be expressed in terms of the AWT of a Boolean function of algebraic degree at most 3 in a larger number of variables.

Index Terms -- Arithmetic Walsh transform; Boolean function; Poisson summation formula; Resilience.