Paper 2026/2900
Modular Walsh rigidity for Boolean functions of degree at most four
Abstract
In sixteen variables, a Boolean function of degree at most four is bent as soon as every Walsh coefficient is $4$ or $5$ modulo $9$. More generally, let $m\ge4$ and $M=2^m$. We prove that a function of degree at most four on $4m$ variables is bent if all its Walsh coefficients are congruent to $\pm M^2$ modulo a single odd integer $p\ge9M/16$. The sign may vary with the frequency. This improves the earlier sufficient bound $p>7M/12$ and includes the endpoint $M=16,\ p=9$. The proof uses the degrees of the low binary digits of the normalized spectrum, low-weight Reed-Muller words, and bounds on groups of Fourier coefficients. As an application, a rotation-symmetric bent function of degree at most four in $888$ variables remains bent on the $24$-variable subspace obtained by repeating a block $37$ times.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Boolean functionsbent functionsWalsh transformReed-Muller codesmodular congruencesrotation symmetry
- Contact author(s)
- contatofilipevono @ gmail com
- History
- 2026-11-19: approved
- 2026-11-15: received
- See all versions
- Short URL
- https://ia.cr/2026/2900
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2900,
author = {Filipe Martins Vono and André Oliveira Naufel de Toledo and Valéria Gonzaga Santos},
title = {Modular Walsh rigidity for Boolean functions of degree at most four},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2900},
year = {2026},
url = {https://eprint.iacr.org/2026/2900}
}