Arithmetic Correlations and Walsh Transforms

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; and 4) find the arithmetic Walsh transforms of linear and affine functions.