🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

This paper surveys fundamental results and recent advances in the design and analysis of Boolean bent functions, specifically focusing on their relationship with the completed Maiorana-McFarland class.

Original authors: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the hidden architecture of modern digital security, there exists a special kind of mathematical object known as a bent function. These are not physical devices or biological entities, but rather complex rules for processing binary data—strings of ones and zeros that form the basis of all computer communication. Imagine a vast landscape of possible rules, where most are predictable and easy to analyze. Bent functions sit at the very peak of unpredictability, standing as far away as possible from any simple, straight-line pattern. Because of this extreme irregularity, they are invaluable tools for protecting data in cryptography and error-correcting codes, acting as the chaotic noise that keeps eavesdroppers from finding a signal. For decades, mathematicians have known how to build a specific, well-understood family of these functions, a group named after the researchers who first described them. This family, often called the Maiorana-McFarland class, has served as the primary blueprint for creating bent functions, much like a standard architectural plan for building a house. However, a lingering question has haunted the field: are these standard blueprints the only way to build such functions, or do other, stranger designs exist that we have yet to discover?

A team of researchers has now taken a comprehensive look at this question, surveying the entire landscape of bent functions to see how they relate to that standard family. Their work confirms that the known blueprints, while useful, represent only a tiny fraction of the total possibilities. In the specific case of functions with eight variables, computer searches have revealed that the total number of bent functions is astronomically large, roughly two to the power of one hundred and six. In stark contrast, the number of functions that can be built using the standard Maiorana-McFarland blueprint is estimated to be at most two to the power of eighty-one. This massive gap suggests that the vast majority of bent functions are fundamentally different from the ones we have been able to construct explicitly. The researchers' goal was to map out the territory between these two extremes, identifying new methods for building bent functions that definitely do not fit the old mold and understanding the structural reasons why they are so different.

The paper begins by examining two specific families of bent functions, known as the C and D classes, which were designed to modify the standard blueprint. These families introduce small, deliberate changes to the standard formula, adding specific patterns to the output. The researchers investigated whether these modifications were enough to push the resulting functions out of the standard family. They found that under certain conditions, these modified functions are indeed distinct. For instance, if the underlying permutation used in the construction has specific algebraic properties—essentially, if it lacks certain hidden symmetries—the resulting bent function cannot be transformed back into the standard form. The authors provided clear, testable rules to determine when a function belongs to these new, exotic families and when it remains trapped within the old one. They also explored "superclasses," which combine different types of modifications, finding that while some combinations work, others fail to produce bent functions at all, revealing the delicate balance required to maintain the necessary level of unpredictability.

Beyond these specific families, the researchers looked at functions built using the multiplicative structure of finite fields, often described using trace terms. These are functions where the output depends on the sum of a number raised to a specific power. The study highlights that many of these functions, particularly those based on certain exponents, are provably outside the standard family. The researchers used a specific mathematical test involving second-order derivatives—a way of measuring how the function's rate of change itself changes—to prove that these functions lack the structural regularity found in the standard class. They also examined functions that act as indicators for other important mathematical objects, such as almost perfect nonlinear functions, showing that these indicators often possess the unique, non-standard properties of bent functions that lie outside the known families.

A central theme of the research is the concept of a "linearity index," which can be thought of as a measure of how much a function resembles a simple, linear pattern. The standard Maiorana-McFarland functions have a high linearity index, meaning they can be broken down into large, simple affine pieces. The researchers identified a new category of functions with the minimal possible linearity index, which they call "optimal." These functions are the opposite of the standard ones; they are so irregular that they cannot be simplified into large affine blocks at all. The paper details how to construct these optimal functions and proves that they are fundamentally different from the standard class. By studying the "M-subspaces"—special geometric substructures within the function's domain that reveal its underlying symmetry—the authors showed that these optimal functions have a unique, minimal structure that the standard functions simply do not possess.

The survey also delves into a broader, more flexible framework called the generalized Maiorana-McFarland class. This framework allows for functions that are built from affine pieces of varying sizes, rather than just the fixed size used in the standard class. The researchers characterized exactly when a function in this broader class remains within the standard family and when it steps outside. They found that by carefully choosing the building blocks, one can create functions that are "almost" standard but still distinct, as well as functions that are completely alien to the standard family. The paper concludes by listing several open problems, acknowledging that while they have mapped out significant portions of this mathematical territory, the full enumeration of all bent functions remains a mystery. They challenge future researchers to find more infinite families of these exotic functions and to understand the precise algebraic structures that make them unique, ensuring that the field continues to evolve beyond the limitations of the original blueprints.

Technical Summary: Bent Functions and the Completed Maiorana-McFarland Class

Problem Statement
Boolean bent functions, introduced by Rothaus, represent a fundamental class of functions in an even number of variables that achieve maximum nonlinearity (maximum distance from affine functions). While the Maiorana-McFarland (M) class and its completed version ( $M^\#$ ) constitute the most thoroughly understood explicit family of bent functions, recent computational evidence indicates a significant discrepancy between the total number of bent functions and those belonging to $M^\#$ . Specifically, in dimension 8, the total number of bent functions is approximately $2^{106}$ , whereas the number of functions equivalent to Maiorana-McFarland is estimated to be at most $2^{81}$ . This observation motivates the central problem of this survey: characterizing bent functions that lie outside the completed Maiorana-McFarland class ( $M^\#$ ), understanding their algebraic structures, and developing explicit construction methods for such functions. The paper focuses on the "exclusion problem"—determining the intersection of various bent function classes with $M^\#$ and identifying conditions under which functions are provably outside this class.

Methodology
The paper employs a comprehensive survey methodology, synthesizing fundamental results and recent advances in the design and analysis of Boolean bent functions. The technical approach relies heavily on:

Algebraic Characterization: Utilizing the second-order derivative criterion (Lemma 1.2) to characterize membership in $M^\#$ . A function belongs to $M^\#$ if and only if there exists an $m$ -dimensional subspace $U$ such that all second-order derivatives $D_a D_b f$ vanish for $a, b \in U$ .
Linearity Index and M-Subspaces: Analyzing the "linearity index" ($ind(f)$), defined as the maximal dimension of an M-subspace (a subspace where second-order derivatives vanish). Functions with $ind(f) = n/2$ belong to $M^\#$ , while those with minimal indices ($ind(f)=1$) are termed $\ell$ -optimal.
Secondary Constructions: Investigating how operations such as direct/indirect sums, concatenations (2- and 4-concatenation), and the addition of trace terms or indicators of subspaces affect membership in $M^\#$ .
Generalized Frameworks: Extending the analysis from the classical $M$ class ( $r=s=n/2$ ) to the Generalized Maiorana-McFarland (GMM) class ( $Mr,s$ ), where $f(x,y) = x \cdot \phi(y) + h(y)$ with $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s$ and $r \neq s$ .

Key Contributions and Results

Carlet's C and D Classes: The paper details the C and D classes, which modify the Maiorana-McFarland form by adding indicators of vector subspaces.
- Class C: Functions of the form $x \cdot \pi(y) + 1_{L^\perp}(x)$ . The authors summarize sufficient conditions on the permutation $\pi$ and subspace $L$ (specifically property (C)) that guarantee the function is bent and outside $M^\#$ . A key result involves permutations whose components lack nonzero linear structures.
- Class D and $D_0$ : Functions of the form $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ and the subclass $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ ). The paper provides a complete characterization of $D_0 \cap M^\#$ , showing that for quadratic permutations, membership depends on whether the permutation is affine on an affine hyperplane. For higher degrees, functions are often outside $M^\#$ .
- Superclasses: The survey examines superclasses (SC, CD, SD) formed by combining indicators. It identifies that while some combinations (like SC) yield bent functions outside $M^\#$ , others (like SD) fail to produce bent functions entirely.
Trace Terms and the $P_\tau$ Property:
- The paper reviews monomial, binomial, and related bent functions defined via trace terms (e.g., Dillon and Kasami exponents). It confirms that many of these, particularly those with specific Niho exponents, lie outside $M^\#$ .
- A significant portion is dedicated to the $P_\tau$ property, which involves adding polynomial combinations of trace terms to a bent function. The paper details how the $P_\tau$ property, characterized by vanishing second-order derivatives of the dual function, allows for the construction of infinite families of bent functions outside $M^\#$ that are not covered by C or D classes.
Generalized Maiorana-McFarland (GMM) Class:
- The paper introduces the GMM class ( $Mr,s$ ) and its completed version. It characterizes bentness in this class using "bent sets" and "partially defined bent functions."
- Almost Maiorana-McFarland ( $k=1$ ): Functions with linearity index $n/2 - 1$ are analyzed. The paper distinguishes between "trivial," "non-proper," and "proper" partitions of the domain, showing that specific proper partitions yield bent functions outside $M^\#$ .
- $\ell$ -optimal Functions: The survey discusses functions with minimal linearity index ($ind(f)=1$), noting that these are the "opposite" of Maiorana-McFarland functions. Constructions involving permutations with property (P1) (non-vanishing second-order derivatives) are highlighted as a method to generate such functions.
M-Subspaces and Secondary Constructions:
- The paper provides a deep algebraic and combinatorial analysis of M-subspaces. It establishes bounds on the number of maximal M-subspaces and links them to the classification of bent functions.
- It presents necessary and sufficient conditions for secondary constructions (direct sum, indirect sum, 2- and 4-concatenation) to result in functions outside $M^\#$ . Notably, it proves that the 4-concatenation of a bent function outside $M^\#$ with an arbitrary bent function yields a new bent function outside $M^\#$ .

Significance
The paper positions itself as a comprehensive survey that bridges the gap between the well-understood Maiorana-McFarland class and the vast, largely unclassified space of bent functions. Its primary significance lies in:

Systematizing Exclusion: Providing a unified framework for determining when bent functions fall outside $M^\#$ , moving beyond ad-hoc examples to structural characterizations based on linearity indices and M-subspaces.
Expanding Construction Methods: Detailing explicit methods (C, D, $P_\tau$ , GMM) to generate infinite families of bent functions outside $M^\#$ , addressing the scarcity of known examples in fixed dimensions.
Clarifying Algebraic Structure: Introducing and refining concepts like the linearity index and M-subspaces as fundamental tools for understanding the algebraic properties of bent functions and their relation to the generalized Maiorana-McFarland hierarchy.
Identifying Open Problems: The paper concludes by listing numerous open problems, including the exact enumeration of EA-equivalence classes in $M^\#$ , the extension of these theories to $p$ -ary bent functions, and the construction of difference sets outside the McFarland class.

The authors maintain a modest tone, acknowledging that while significant progress has been made in identifying functions outside $M^\#$ , the total enumeration of bent functions and a complete classification of their algebraic structures remain open challenges. The work serves as a foundational reference for researchers aiming to design cryptographically significant Boolean functions with specific nonlinearity properties that cannot be captured by the standard Maiorana-McFarland construction.

More like this