🔢 mathematics

On Generalizations of Maiorana-McFarland and $\mathcal{PS}_{ap}$ Functions

This paper introduces generalized Maiorana-McFarland and $\mathcal{PS}_{ap}$ constructions of Boolean bent functions that lie outside their classical completed classes, proves that certain generalized $\mathcal{PS}_{ap}$ functions cannot be decomposed into simpler bent or semibent functions, and presents a new secondary construction based on vectorial generalized $\mathcal{PS}_{ap}$ components.

Original authors: Sezel Alkan, Nurdagül Anbar, Athina Avrantini, Erroxe Etxabarri-Alberdi, Tekgül Kalaycı, Beatrice Toesca

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sezel Alkan, Nurdagül Anbar, Athina Avrantini, Erroxe Etxabarri-Alberdi, Tekgül Kalaycı, Beatrice Toesca

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

Imagine you are a master architect designing a fortress. In the world of cryptography, this fortress is a Boolean function—a complex mathematical rule that takes a string of 0s and 1s and outputs a single 0 or 1. The goal is to make this rule so unpredictable and "bent" (twisted) that no hacker can find a pattern to break the code.

This paper is about discovering new, stronger blueprints for these fortresses that no one has seen before.

Here is the story of the paper, broken down into simple concepts and analogies.

1. The Two Old Blueprints (The "Famous Families")

For decades, cryptographers have relied on two main families of blueprints to build these secure functions:

The Maiorana–McFarland (MM) Family: Think of this as a very popular, well-organized neighborhood. It's easy to build houses here, and we know exactly how they work.
The Partial Spread (PSap) Family: This is a slightly different neighborhood, built on a specific geometric pattern (like spreading out tiles so they don't overlap).

The Problem: Mathematicians realized that if you only use these two neighborhoods, you are limited. In fact, if you look at all possible secure functions in a certain size, the MM family only covers a tiny, tiny fraction of them (like finding one specific grain of sand on a massive beach). We need to find functions that live outside these two neighborhoods to make our codes truly unique and secure.

2. The First Discovery: Building a "Hybrid" House

The authors wanted to build a new type of house that looks like it belongs to the MM family but actually doesn't.

The Analogy: Imagine the MM family is a club where everyone must wear a specific uniform (a specific mathematical structure). The authors decided to take two different groups of people who almost wear the uniform but have a slight twist.
The Trick: They created a "Generalized" version of the MM family. They took a standard MM function and mixed it with another one, but they did it in a way that broke the club's strict rules.
The Result: They proved that these new "Hybrid" functions are secure (bent) but cannot be transformed into the old MM style. They are like a new species of animal that looks like a cat but has the DNA of a tiger. They exist outside the known "completed" classes.

3. The Second Discovery: The "Unbreakable" Puzzle

The second part of the paper looks at the PSap family (the geometric tile pattern).

The Concept of "Decomposition": Usually, if you have a giant, complex puzzle, you can break it down into smaller, simpler puzzles (like taking a big wall apart to see the individual bricks). In math, this is called "decomposition." If you can break a function down, you can often build it back up from known, simpler parts.
The Discovery: The authors looked at a specific type of PSap function where the "degree" (how complex the math is) is small compared to the size of the field (the size of the puzzle).
The Metaphor: Imagine a complex knot. Usually, you can untie it by pulling on the ends. The authors proved that for these specific functions, you cannot untie the knot. No matter how hard you try, you cannot break them down into simpler, known pieces.
Why it matters: This means these functions are "atomic." You can't build them by just gluing together smaller, known secure functions. They are fundamentally new structures that require entirely new construction methods.

4. The Third Discovery: Stitching the Pieces Together

Finally, the paper offers a new way to build these fortresses using a technique called concatenation (stitching).

The Analogy: Imagine you have four different fabrics (four different secure functions). Usually, if you sew them together, the result is a weak, patchwork quilt that hackers can easily tear.
The Innovation: The authors found a specific way to stitch the "components" of their new vectorial functions together. It's like using a special, invisible thread that makes the seams disappear, creating a single, seamless, ultra-strong fabric.
The Result: This creates a new secondary construction method. It allows mathematicians to take these complex, "unbreakable" pieces and combine them to create even larger, more secure functions.

Summary: Why Should You Care?

Think of encryption as a lock.

Old locks (MM and PSap classes) are good, but we know their keys too well.
This paper designs new locks that:
- Look like old locks but have secret mechanisms inside (Generalized MM).
- Are made of materials that can't be taken apart (Generalized PSap).
- Can be assembled in new ways to make bigger, stronger vaults (Concatenation).

By finding these new mathematical structures, the authors are giving cybersecurity experts new tools to build unbreakable codes for the future, ensuring that our digital secrets remain safe even as computers get more powerful. They used advanced tools like "algebraic curves" (think of them as complex maps) to prove that these new locks are real and secure.

1. Problem Statement

The paper addresses the classification and construction of Boolean bent functions, which are functions with optimal nonlinearity and are crucial in cryptography. A central challenge in this field is constructing bent functions that lie outside the completed Maiorana–McFarland (MM#) class.

Context: While all bent functions in dimensions up to 6 belong to the completed MM class, it is known that in dimension 8, the MM# class constitutes only a tiny fraction of all bent functions.
Gap: Existing primary constructions (MM and Partial Spread $PS_{ap}$ ) and secondary constructions (like concatenation) often produce functions that fall back into known classes or admit specific decompositions (e.g., into bent or semibent components).
Objective: The authors aim to:
1. Construct families of Generalized Maiorana–McFarland (GMM) functions that are provably outside the MM# class.
2. Investigate the decomposition of Generalized Partial Spread ( $PS_{ap}$ ) functions, specifically determining if they can be formed by concatenating bent or semibent functions.
3. Develop new secondary constructions based on the components of vectorial generalized $PS_{ap}$ functions.

2. Methodology

The authors employ a combination of algebraic, combinatorial, and geometric techniques:

Dillon's Criterion: They utilize a criterion based on second-order derivatives to characterize membership in the completed MM class. A function belongs to MM# if and only if it possesses an M-subspace of dimension $n/2$ where all second-order derivatives vanish.
Algebraic Curves and Function Fields: To prove that certain derivatives are non-constant (and thus functions do not admit specific decompositions), the authors analyze the number of rational points on Artin-Schreier curves defined over finite fields. They apply the Hasse-Weil bound and the Hurwitz genus formula to establish the existence of points that violate constancy conditions.
Vectorial Function Theory: The study extends to vectorial bent functions, analyzing their component functions and duals.
Concatenation Techniques: The paper investigates the "4-decomposition" of functions, where a function is viewed as the concatenation of four restrictions to cosets of a subspace.

3. Key Contributions and Results

A. Construction of GMM Functions Outside MM#

The authors construct a new family of GMM functions that are not equivalent to any function in the classical MM or $PS_{ap}$ classes.

Mechanism: They define a function $f(x, y, z) = f_{(z)}(x) + \text{Tr}_1^k(yz)$ , where $f_{(z)}$ are MM functions.
Innovation: Unlike previous constructions where $f_{(z)}$ share a common large M-subspace, the authors select MM functions that share only trivial M-subspaces (dimension $\le 1$ ).
Specific Construction: They utilize permutations $\pi$ satisfying Property (P), which ensures the underlying MM function has a unique maximal M-subspace. By swapping the roles of variables based on the trace of $z$ , they create a GMM function where the maximal M-subspace dimension is strictly less than $n/2 + k$ .
Result: Under specific conditions (e.g., $m > k + 2$ ), these functions lie outside the MM# class. Examples include permutations based on inverse functions ( $x^{2^m-2}$ ) and Gold functions ( $x^{2^k+1}$ ).

B. Decomposition of Generalized $PS_{ap}$ Functions

The paper investigates whether generalized $PS_{ap}$ functions can be decomposed into bent or semibent functions via concatenation.

Main Finding: The authors prove that for generalized $PS_{ap}$ functions with sufficiently small algebraic degree relative to the field size, they do not admit a bent or semibent decomposition in general.
Technical Proof:
- They derive the dual function $f^*$ of a generalized $PS_{ap}$ function.
- Using Lemma 10, they show that a bent decomposition exists iff the second-order derivative of the dual is constantly 1, and a semibent decomposition exists iff it is constantly 0.
- They prove that for specific subspaces $S$ , the second-order derivative of the dual is non-constant. This is demonstrated by showing that the associated algebraic curve has rational points for both trace values 0 and 1, using the Hasse-Weil bound.
Implication: These functions cannot be generated by known secondary constructions based on the concatenation of bent or semibent functions, distinguishing them from many other known classes.

C. Secondary Construction via Vectorial Components

The authors present a new secondary construction of Boolean bent functions derived from vectorial generalized $PS_{ap}$ functions.

Mechanism: They exploit the property that for vectorial bent functions arising from bent partitions, the duals of component functions satisfy a specific linear relation: $(F_\alpha)^* + (F_\beta)^* = (F_{\alpha+\beta})^*$ .
Construction: By concatenating components $F_\alpha, F_\beta, F_\gamma, F_{\alpha+\beta+\gamma+1}$ , they construct a new Boolean bent function.
Generalization: They further generalize this by defining a function based on the preimage distribution of the generalized Desarguesian spread, assigning values to partition sets to ensure the resulting function is bent.

4. Significance

Expansion of the Bent Function Landscape: The paper provides explicit, provable examples of bent functions that lie outside the MM# class, addressing a long-standing open problem in the classification of bent functions.
Limitations of Secondary Constructions: By proving that generalized $PS_{ap}$ functions generally do not admit bent/semibent decompositions, the authors demonstrate the limitations of concatenation-based secondary constructions for this specific class. This highlights the need for primary constructions or new secondary methods.
Methodological Advancement: The rigorous application of algebraic geometry (specifically the theory of function fields and rational points on curves) to the study of Boolean function derivatives provides a powerful toolkit for future research in cryptographic function classification.
Cryptographic Relevance: Functions outside the MM# class are highly desirable for cryptographic applications because they offer resistance against certain algebraic attacks that might exploit the structure of MM functions.

Conclusion

This paper significantly advances the theory of Boolean bent functions by constructing new families of GMM functions outside the MM# class and characterizing the structural limitations of generalized $PS_{ap}$ functions regarding decomposition. The work bridges combinatorial design, finite field theory, and algebraic geometry to solve classification problems in cryptography.