Paper 2026/2900

Modular Walsh rigidity for Boolean functions of degree at most four

Filipe Martins Vono, Centro Universitário de Belo Horizonte (UniBH), Belo Horizonte, Brazil
André Oliveira Naufel de Toledo, Centro Universitário de Belo Horizonte (UniBH), Belo Horizonte, Brazil
Valéria Gonzaga Santos, American Global Tech University (AGTU)
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.