A Matter of Representation: Evolving Partial Spreads for Bent Functions

Claude Carlet, Marko Đurasevic, Domagoj Jakobovic, Luca Manzoni, Luca Mariot, Stjepan PicekarXiv 2026 · arXiv

TL;DR

Instead of searching for "bent" (highly nonlinear) Boolean functions by blindly tweaking truth tables, this paper evolves the underlying combinatorial structures—called partial spreads—used to build them. By switching to a "spread-set" representation and using a "ruin-and-rebuild" strategy, the authors successfully evolved complex bent functions for up to 10 variables, discovering functions with structural properties that traditional genetic programming misses.

What Problem Does This Paper Address?

In cryptography and coding theory, bent functions are the "gold standard" for Boolean functions because they are as far from linear functions as mathematically possible. This maximum nonlinearity makes them highly resistant to linear cryptanalysis.

However, finding them is a nightmare. As the number of variables ($n$) increases, the search space of possible Boolean functions grows at a rate of $2^{2^n}$. For $n=10$, the space is so vast that exhaustive search is impossible.

While researchers have used Evolutionary Algorithms (EAs) to find these functions before, they usually search the space of truth tables or symbolic trees. This is often "blind" to the underlying mathematical requirements. This paper takes a different tack: it targets a specific algebraic construction called the Partial Spread ($\mathcal{PS}$) class. To find a $\mathcal{PS}$ bent function, you must find a collection of subspaces that only intersect at the zero vector. This turns a functional search into a hard combinatorial optimization problem.

Methods

The authors designed an Evolution Strategy (ES) to find these families of non-intersecting subspaces. The core of their contribution lies in how they represented the problem:

  1. Encodings: They compared two ways to represent subspaces:
  2. Subspace Encoding: Representing each subspace by its generator matrix.
  3. Spread-set Encoding: A more sophisticated approach from finite geometry. By fixing two subspaces ($E_0$ and $E_\infty$), every other subspace can be represented as a matrix. Crucially, two subspaces have a "trivial intersection" (the goal) if and only if the difference of their matrices is invertible.
  4. Ruin-and-Rebuild: When the ES hits a conflict (subspaces intersecting too much), it doesn't just flip bits. It uses a "ruin-and-rebuild" operator that removes conflicting members and attempts to rebuild them using an exact insertion search algorithm.
  5. Quality-Diversity (MAP-Elites): To find functions that aren't just bent but also have a low algebraic degree (another desirable cryptographic property), they used a quality-diversity approach to maintain a map of the best solutions found for different degrees.

Datasets

The paper does not use external datasets. Instead, it evaluates the algorithms on the mathematical search spaces for $n = 8, 10, \text{and } 12$ variables. They compare their results against:

  • Random Greedy Heuristics: Adding subspaces one by one randomly.
  • Look-ahead Greedy Heuristics: A smarter greedy approach that picks the "best" next subspace.
  • Genetic Programming (GP): A baseline from previous literature that evolves Boolean functions as symbolic trees.

Key Insights and Ideas

  • Representation is Everything: The "spread-set" encoding was the game-changer. While the subspace encoding failed completely at $n=10$, the spread-set encoding (which leverages the "invertible difference" property) succeeded.
  • The "Hardness" of $\mathcal{PS}^+$: The authors found that $\mathcal{PS}^+$ functions (which require one more subspace than $\mathcal{PS}^-$) are significantly harder to evolve. Landscape analysis showed that stagnation points for $\mathcal{PS}^+$ are much further away from a valid solution than for $\mathcal{PS}^-$.
  • Greedy can be Good: Surprisingly, a restarted "look-ahead" greedy heuristic outperformed the ES on the hardest $n=10$ instances. This suggests the fitness landscape is extremely "pointy" or discrete, where local search struggles compared to smart construction.
  • Structural Uniqueness: The bent functions found via partial spreads have a high 2-rank, a measure of structural complexity. Functions evolved by standard Genetic Programming usually have low 2-ranks. This means the two methods are exploring entirely different "neighborhoods" of the bent function universe.

Key Results

  • Success at $n=10$: The ES with spread-set encoding and ruin-and-rebuild achieved a 100% success rate for $\mathcal{PS}^-$ targets and a 74% success rate for the harder $\mathcal{PS}^+$ targets.
  • The $n=12$ Wall: Neither the ES nor the greedy heuristics could find a solution for $n=12$ within a 24-hour window, marking the current limit of this approach.
  • Low Degree Discovery: For $n=8$, the Quality-Diversity ES reliably found bent functions with an algebraic degree of 2 or 3 (lower than the standard $n/2$), which are rare and useful.

Limitations and Future Work

The primary limitation is scalability. The jump from $n=10$ to $n=12$ increases the search space exponentially, and the "exact insertion" step becomes a bottleneck.

The authors suggest two main paths forward:

  1. Stronger Insertion Heuristics: Improving the backtracking search used during the "rebuild" phase to handle larger matrices.
  2. Symmetry-Restricted Encodings: Constraining the search to subspaces that follow certain symmetries (like rotation-symmetry) to drastically prune the search space for $n=12$ and beyond.

Summary updated

Abstract

Partial spread ($\mathcal{PS}$) bent functions are Boolean functions of maximum nonlinearity built from families of subspaces that pairwise intersect only in the null vector. We design an Evolution Strategy (ES) to construct such partial spread families, comparing two encodings: one based on generator matrices of the subspaces, and one based on spread sets. With the latter, combined with a ruin-and-rebuild operator, the ES finds $\mathcal{PS}$ functions up to $n=10$ variables. An ablation study shows that mutation is necessary, while the population size is not, and that a restarted look-ahead greedy heuristic outperforms the ES on the hardest instance. We investigate this finding with a landscape analysis of the stagnation points, and we also introduce a quality-diversity variant of the ES which finds $\mathcal{PS}$ functions of low algebraic degree for 8 variables. Interestingly, the bent functions evolved by the ES have higher 2-ranks and mostly higher degrees than those obtained by a baseline Genetic Programming optimizer.
BibTeX
@misc{carlet2026matter,
  author = {Claude Carlet and Marko Đurasevic and Domagoj Jakobovic and Luca Manzoni and Luca Mariot and Stjepan Picek},
  title = {{A Matter of Representation: Evolving Partial Spreads for Bent Functions}},
  year = {2026},
  eprint = {2611.26011},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.26011},
}
Figure