Arithmetic Correlations and Walsh Transforms

Authors: Andrew Klapper and Mark Goresky
Andrew Klapper, 307 Marksbury, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0633, klapper at

Appeared in IEEE Transactions on Information Theory.
Abstract In this paper the authors continue a program to find arithmetic, or "with-carry," analogs of polynomial based phenomena that appear in the design and analysis of cryptosystems and other branches of digital computation and communications. They construct arithmetic analogs of the Walsh-Hadamard transform and correlation functions of Boolean functions. These play central roles in the cryptographic analysis of block ciphers and stream ciphers. After making basic definitions and constructing various algebraic tools they: (1) show how to realize arithmetic correlations as cardinalities of intersections of hypersurfaces; (2) show that the arithmetic Walsh spectrum characterizes a Boolean function; (3) study the average behavior of arithmetic Walsh transforms; (4) find the arithmetic Walsh transforms of linear and affine functions.

Index Terms -- Walsh-Hadamard transform, correlation functions, p-adic numbers