Welcome to the resource topic for 2025/1651
Title:
On the Cardinality of the Walsh Support of a Boolean Function
Authors: Maxence Jauberty, Pierrick Méaux
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.
ePrint: https://eprint.iacr.org/2025/1651
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .