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