CS Paper Radar

Bent Functions and the Completed Maiorana-McFarland Class

Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

cs.IT math.HOmath.CO ·submitted 2026-08-20 17:24 UTC · v1
surveyunusual

Abstract

In this article, we survey some fundamental results and recent advances in the design and analysis of Boolean bent functions from the perspective of their relation to the completed Maiorana-McFarland class.

Closest papers

Nearest neighbours by meaning across the whole index.

General constructions of normal bent partitions related to vectorial dual-bent functions

cs.DM math.CO ·2026-10-02 ·Alexander Kholosha, Mohit Pal
theory similarity 0.60
Abstract

Bent partitions were introduced as a generalization of partial spread construction of bent functions and they became a hot research topic recently. In this paper, we prove two general constructions of normal bent partitions that are related to vectorial dual-bent functions. They cover many of the currently known bent partitions of this type as partial cases. These constructions also provide a large number of new bent partitions. Relevant properties of bent functions obtained from such partitions are proven.

0.23

Generalized $p$-ary $\cPS$ Bent Functions

cs.IT cs.DM ·2026-09-16 ·Alexander Kholosha, Mohit Pal
similarity 0.59
Abstract

We use $m$-dimensional partial spreads of $\fp^{2n}$, where $p$ is an odd prime, $n$ is a positive integer and $m$ divides $n$, to construct two classes of bent functions from $\fp^{2n}$ to $\fp$. Our construction generalizes the classes of $p$-ary $\cPS^{-}$ and $\cPS^{+}$ bent functions proposed by P. Lison\v ek and H. Y. Lu (Des. Codes Cryptogr. 73 (2014), 209--216).

0.28

A counterexample to Tokareva's conjecture on sums of two bent functions

cs.IT math.CO ·2026-10-23 ·Yansong Feng, Hao Jiang, Guancheng Li, Tianyi Li, Lili Tang
similarity 0.54
Abstract · The counterexamples and proofs in this paper were obtained through large-scale automated reasoning with LLM agents while solving Problem~10 …

It is well known that the sum of two bent functions on $\mathbb{F}^n$ has algebraic degree at most $n/2$ for even $n\ge 4$. Tokareva conjectured that the converse holds: every Boolean function with degree at most $n/2$ can be written as a sum of two bent functions. The conjecture has been verified for even $n\leq 6$ and for several special classes of Boolean functions. We disprove this conjecture by showing that $x_1x_2(x_3x_4+x_5x_6+x_7x_8)$ is not a sum of two bent functions on $\mathbb{F}^8$. We extend this construction to obtain counterexamples in every even dimension $n\ge 8$. Using Shaporenko's reduction, we also obtain explicit counterexamples to Tokareva's derivative conjecture in every even dimension $n\ge 10$.

0.47

The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116

cs.IT cs.CR ·2026-10-13 ·Yueying Lou, Youle Xu, Qichun Wang
similarity 0.54
Abstract

Does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions. In this paper, we give a negative answer to this open problem, and prove that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116, establishing the 8-variable instance of Dobbertin's conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed--Muller code RM(1,8) in 0-resilient Boolean functions is 116. We deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6.

0.30

Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports

cs.IT ·2026-09-18 ·Chen Wang, Xiaoyan Zhang, Chunming Tang, Zhengchun Zhou
hot direction similarity 0.49
Abstract

Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general construction attaining both properties is spectral (Hodžić et al., IEEE Trans. Inf. Theory 65(9): 5865--5879, 2019). In that work, explicit algebraic normal forms are not generally provided, and no general method is established for prescribing a common algebraic degree for all family members. In this paper, we present two new explicit algebraic constructions within a unified framework, one based on linear functions and the other on partially linear functions with bent components. Let $p\geq 2$ and $q\geq 0$ satisfy $q<2^p-p-1$, and set $m=p+q$. Both constructions yield maximum-cardinality families of $2^{q+1}$ $(q+1)$-plateaued Boolean functions with pairwise disjoint Walsh supports. No member admits a nonzero linear structure, and every member has an explicit generalized Maiorana--McFarland representation. The first construction produces functions in $m+p+1$ variables and realizes any prescribed common algebraic degree $3\leq d\leq p+1$, provided that $q<\sum_{i=2}^{d-1}\binom{p}{i}$; its maximum attainable degree $p+1$ is optimal. The second construction produces functions in $n+p+1$ variables, where $n>m$ and $n-m$ is even, and realizes any prescribed common algebraic degree $3\leq d\leq p+(n-m)/2$, provided that $q<\sum_{i=2}^{\min\{d-1,p\}}\binom{p}{i}$; its maximum attainable degree $p+(n-m)/2$ is next-to-optimal.

0.34

On the Fourier Entropy-Influence Conjecture for Boolean Plateaued Functions

cs.IT math.CO ·2026-09-18 ·Vladimir N. Potapov
theoryhot direction similarity 0.49
Abstract · 8 papes, the paper was written with the assistance of ChatGPT

We prove the following inequality for Boolean functions: $2\sum_{x\in F_2^n}f(x)wt(x)\geq wt(f)(n-deg(f))$. Using this inequality, we establish the Fourier Entropy-Influence (FEI) conjecture for Boolean plateaued functions. In particular, we show that the sharp FEI constant for the class of plateaued functions is 4. We also prove the FEI conjecture for partially bent functions and show that the corresponding sharp constant is 2. Finally, we derive several estimates for the p-biased distribution on the Boolean hypercube. Keywords: Fourier entropy, total influence, average sensitivity, plateaued function, algebraic degree, Reed-Muller code, p-biased distribution.

0.53

Characterizations and MacWilliams-Like Identities of Weakly Regular Bent Partitions

cs.IT ·2026-10-30 ·Jiaxin Wang, Yadi Wei, Fang-Wei Fu, Jin Li, Fulin Li
theory similarity 0.47
Abstract

Bent partitions play a significant role in the theory of bent functions. In this paper, we study weakly regular bent partitions, that is, all generated bent functions are weakly regular (called in class $\mathcal{WRBP}$). Let $Γ=\{A_{i}, i \in V_{m}\}$ be a bent partition of $V_{n}$ in class $\mathcal{WRBP}$, where $V_{n}$ denotes an $n$-dimensional vector space over the prime field $\mathbb{F}_{p}$, $n$ is even, $m \leq \frac{n}{2}$, and $m \geq 2$ if $p=2$. We first characterize bent partition $Γ$ in terms of the duals of component functions of vectorial bent functions. In particular, we prove that if $p \neq 3$, then all bent functions generated by $Γ$ are regular. Building on the above result, we give characterizations of bent partition $Γ$ in terms of two classes of linear codes. When $n \geq 4$ and $m=\frac{n}{2}$, except for the case where $(p, n)=(2, 4)$ and $|A_{i_{0}}|=1$ for some $i_{0}$, we show that $Γ$ is obtained from a spread (after a shift). Particularly, any normal bent partition of $V_{n}$ of depth $p^{\frac{n}{2}}$ in class $\mathcal{WRBP}$ must be obtained from a spread (after a shift), where $n \geq 4$. We establish the Macwilliams-like identities for bent partitions in class $\mathcal{WRBP}$. Furthermore, if $p$ is odd, we present some nonexistence results on bent partitions in class $\mathcal{WRBP}$.

0.13

Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

cs.CC math.COcs.DM ·2026-10-12 ·Yuan Li, Jing Zhang
theory similarity 0.46
Abstract · Version 2, 44 pages

We investigate block sensitivity and certificate complexity of monomial rotation-symmetric Boolean functions, obtaining exact formulas and structural classifications for several families. For odd-degree monomial rotation-symmetric functions, the equality $s(f)=n$ established in our earlier work yields $bs(f)=C(f)=n$. For quadratic monomial rotation-symmetric functions, we determine both measures completely and prove that block sensitivity equals certificate complexity. For consecutive quartic monomials, we determine sensitivity, block sensitivity, and certificate complexity in every residue class of the number of variables. Our principal result is an exact global block-sensitivity formula for consecutive monomials of every even degree $d\ge4$. Writing $n=q(d+2)+ρ$, where $0\leρ<d+2$ and $q\ge\max\{2,d/2-1\}$, we prove \[ bs(F_{d,n})=n-\min\left\{\left\lceil\fracρ{2}\right\rceil,d+2-ρ\right\}. \] We also establish the corresponding sensitivity formula by a self-contained argument, yielding arbitrarily large gaps between sensitivity and block sensitivity as the degree varies. For certificate complexity, we obtain exact pointwise formulas for structured run-and-gap configurations and establish additional global equalities, including $C(F_{6,8q+5})=bs(F_{6,8q+5})=8q+2$ for $q\ge2$. Our methods combine cyclic run decomposition, parity arguments, explicit sensitive-block constructions, and constant-subcube certificates. The exact global certificate complexity for arbitrary even degrees remains open.

0.43