A New Transform Related to Distance From a Boolean Function
Andrew Klapper · IEEE Transactions on Information Theory · 2016
We introduce a new transform on Boolean functions generalizing the Walsh–Hadamard transform. For Boolean functions$q$and$f$, the$q$-transform of$f$measures the proximity of$f$to the set of functions obtained from$q$by change of basis. This has implications for security against certain algebraic attacks. In this paper, we derive the expected value and second moment (Parseval’s equation) of the$q$-transform, leading to a notion of$q$-bentness. We also develop a Poisson summation formula, which leads to a proof that the$q$-transform is invertible.