Paper 2026/386 Original: eprint.iacr.org/2026/386 ↗

Determining those Boolean functions whose restrictions to affine spaces are plateaued

Abstract

Quadratic Boolean functions (that is, Boolean functions of algebraic degree at most 2), bent Boolean functions (i.e. maximally nonlinear Boolean functions in even numbers of variables) and, as we observe in this paper, partially-bent Boolean functions (i.e. affine extensions of bent functions to linear super-spaces), share a strong property: all their restrictions to affine hyperplanes are plateaued (i.e. have a Walsh transform valued in a set of the form $\{0,\pm \lambda\}$, where $\lambda$ is a positive integer called the amplitude). In this paper we determine for any $n$ and $k<n$ the class $C^n_k$ of those $n$-variable Boolean functions whose restrictions to all $k$-dimensional affine subspaces of $\F_2^n$ are plateaued (of any amplitude). We show that, for any $n\geq 4$, $C^n_{n-1}$ equals the class of partially-bent functions, and for $3 \leq k \leq n-2$, $C^n_k$ equals the class of quadratic functions (while for $0\leq k\leq 2$, it equals of course the class of all Boolean functions). This provides a new characterization (after almost 20 years) of partially-bent functions and a hierarchy among $n$-variable Boolean functions by six nested classes, each of which happens to be, for any $n\geq 5$, strictly included in the next one: quadratic functions, partially-bent functions, the restrictions of $(n+1)$-variable partially-bent functions to $\F_2^n$, plateaued functions, the restrictions of $(n+1)$-variable plateaued functions to $\F_2^n$, and all Boolean functions. We leave open the two problems of determining exactly what are the third and fifth of these classes, but we begin the study of the first of these two classes by characterizing the situation where a plateaued function $g$ has a restriction $f$ to an affine hyperplane $H$ that is plateaued. We also characterize when $g$ is partially-bent. Our characterization of partially-bent (resp., quadratic) functions extends to strongly plateaued vectorial functions. We state an open question on vectorial functions that happens to be related to an important one on crooked functions.