Paper 2025/1651 Original: eprint.iacr.org/2025/1651 ↗

On the Cardinality of the Walsh Support of a Boolean Function

Abstract

We provide a complete characterization of the possible cardinalities of Walsh supports of Boolean functions. Our approach begins with a detailed study of Siegenthaler’s construction and its properties, which allow us to derive relations between admissible support sizes in successive numbers of variables. We then introduce new notions such as Walsh space, reduction, and equivalence on supports, which form the structural framework of our analysis. For $n=6$, we perform an experimental enumeration of affine-equivalence classes, and we analyze the geometric structure of supports of small cardinalities, proving uniqueness for sizes $10$ and $13$ and obtaining partial results for size $16$. By combining these findings with a sieving method, we rule out twelve impossible cardinalities and establish constructive methods that transform a support of size $s$ into one of size $4s+r$ for different values of $r$, sufficient to obtain every admissible cardinality for $n \geq 7$. As a consequence, we provide a complete characterization and resolve several open problems.