A spectral characterization of correlation-immune combining functions

Abstract

It is shown that a Boolean combining function f(x) of n variables is mth-order correlation-immune if and only if its Walsh transform F( omega ) vanishes for all omega with Hamming weight between 1 and m, inclusive. This result is used to extend slightly Siegenthaler's (IEEE Trans. Comput., vol. C-34, pp. 81-85, Jan. 1985) characterization of the algebraic normal form of correlation-immune combining functions.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>