🔢 mathematics

The combinatorial structure and value distributions of plateaued functions

This paper investigates the combinatorial structure, value distributions, and cryptographic properties of plateaued functions over finite fields, establishing direct connections between their Walsh transforms, linearity, and differential uniformity, while specifically characterizing the existence and constraints of "almost balanced" plateaued functions and plateaued APN functions.

Original authors: Lukas Kölsch, Alexandr Polujan

Published 2026-03-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lukas Kölsch, Alexandr Polujan

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 the ultimate digital fortress. To make this fortress secure, you need to build walls that are incredibly hard to break, yet flexible enough to let authorized users in. In the world of cryptography, these "walls" are mathematical functions.

This paper is like a detailed inspection report on a specific, very special type of wall called a Plateaued Function.

Here is the breakdown of what the authors discovered, explained through simple analogies.

1. The Building Blocks: What is a "Plateaued" Function?

Think of a function as a machine that takes a huge pile of inputs (like a million different keys) and spits out outputs (like a million different locks).

Balanced Functions: Ideally, you want a machine where every single lock gets exactly the same number of keys. If you have 1,000 locks and 1,000 keys, each lock gets exactly one key. This is perfect balance.
The Problem: In the real world, perfect balance is rare. Sometimes, one lock gets 10 keys, and another gets none. This creates "imbalance," which hackers can exploit.
Plateaued Functions: These are the "almost perfect" machines. Instead of a flat, even distribution, imagine a landscape with flat plateaus (hence the name). Most locks get a standard number of keys, but a few might get a slightly different amount. They aren't perfectly flat, but they are "flat enough" to be very secure.

The authors studied these "plateaued" functions because they are the building blocks for many modern encryption systems (like the ones protecting your bank data or the internet).

2. The Detective Tool: The Walsh Transform

How do you know if a machine is balanced or not without counting every single key? You need a special X-ray machine.

In math, this X-ray is called the Walsh Transform.

The Analogy: Imagine you have a noisy room full of people talking. You want to know if everyone is speaking at the same volume (balanced) or if a few people are shouting (imbalanced).
The Walsh Transform is like a sound analyzer that listens to the "frequency" of the machine's output. If the machine is well-designed, the analyzer shows a very specific, predictable pattern. If the machine is messy, the pattern is chaotic.

The authors used this "sound analyzer" to figure out exactly how keys are distributed among locks, without having to count them one by one.

3. The Big Discovery: The "Almost Balanced" Rule

The team focused on a special group of these machines called "Almost Balanced" functions.

The Scenario: Imagine you have a party with 100 guests and 100 chairs. In a perfectly balanced party, everyone sits down. In an "almost balanced" party, 99 chairs have exactly one person, but one chair has 5 people, and another chair is empty. It's almost fair, but not quite.
The Finding: The authors discovered that for these "almost balanced" machines, there are strict rules. You can't just have any number of people on the extra chair. The math forces the numbers to be very specific (like powers of 2 or specific multiples).

They proved that if a machine is "almost balanced," its internal structure (the Walsh Transform) must look a certain way. It's like saying, "If you see a house with a red door, the roof must be blue."

4. The "Monomial" Mystery

One of the most famous types of these machines is built using simple formulas called Monomials (think of them as single-term recipes, like $x^3$ or $x^5$ ).

The Question: Can these simple recipes create "almost balanced" machines?
The Answer: Yes, but only under very strict conditions. The authors found that these simple recipes only work if the "power" (the exponent) follows a very specific pattern related to the size of the system.
The Metaphor: It's like trying to bake a cake using only flour and sugar. You can do it, but only if you use exactly 2 cups of flour and 1 cup of sugar. If you use 3 cups of flour, the cake collapses. The paper tells us exactly which "recipes" (exponents) work and which ones fail.

5. The "Super-Secure" APN Functions

Finally, the authors looked at the "Elite" of these functions: APN functions. These are the gold standard for security, used in the most critical encryption algorithms.

The Challenge: We know these functions exist, but we don't fully understand their shape. Do they have a "perfect" distribution of keys, or are they messy?
The Breakthrough: The authors used their new tools to prove that certain types of "messy" distributions are actually impossible for these elite functions.
- Example: They showed that a specific type of "almost balanced" APN function (where two locks have 2 keys and the rest have 3) cannot exist. It's like proving that a specific type of 4-sided triangle is geometrically impossible.

Why Does This Matter?

Think of cryptography as a game of hide-and-seek between code-makers and code-breakers.

Code-makers want to build functions that are hard to predict (high nonlinearity) and distribute data evenly (balanced).
Code-breakers look for patterns or imbalances to crack the code.

By understanding the "combinatorial structure" (the shape and distribution) of these plateaued functions, the authors are giving code-makers a better blueprint. They are saying:

"Here are the only shapes that work."
"Here are the shapes that are impossible, so don't waste time trying to build them."
"Here is how to check if your design is secure just by looking at its 'sound' (Walsh Transform)."

Summary

This paper is a map for digital architects. It takes a complex, abstract mathematical concept (plateaued functions) and uses a powerful tool (the Walsh Transform) to reveal the hidden rules of how these functions distribute their data. They found that while these functions can be "almost balanced," they are bound by strict mathematical laws, and they ruled out several impossible designs for the most secure encryption systems in the world.

1. Problem Statement

The paper addresses the gap in understanding the value distributions (sizes of image and preimage sets) of plateaued functions, a broad class of cryptographic primitives that generalizes quadratic, bent, and most known Almost Perfect Nonlinear (APN) functions.

While the differential properties and nonlinearity of these functions are well-studied, their combinatorial structure regarding how they map inputs to outputs (specifically, whether they are balanced, almost balanced, or $d$ -to-1) remains less explored. The authors aim to:

Establish a rigorous connection between the Walsh transform (spectral properties) and the value distribution (preimage sizes) of vectorial functions $F: \mathbb{F}_p^n \to \mathbb{F}_p^m$ .
Characterize almost balanced plateaued functions, where all preimages have the same size except for one.
Determine the existence conditions for plateaued $d$ -to-1 functions (including monomials) and derive bounds on their linearity and differential uniformity.
Analyze the specific combinatorial structure of plateaued APN functions, particularly those with minimal image set sizes.

2. Methodology

The authors employ a spectral approach, utilizing the Walsh transform as the primary tool to derive combinatorial properties without relying heavily on differential analysis (which is often difficult when differential properties are unknown).

Key Methodological Steps:

Walsh Transform at Zero: The authors focus on the Walsh transform evaluated at $a=0$ , denoted $W_F(b, 0)$ . They utilize the orthogonality of characters to relate the sum of Walsh coefficients to preimage sizes.
Imbalance Metric ( $N_bF$ ): They define the imbalance $N_bF$ as the normalized sum of squared Walsh coefficients at zero for non-zero $b$ . This metric quantifies the deviation from a balanced function.
Optimization via Cauchy-Schwarz: They apply the Cauchy-Schwarz inequality to the system of equations involving the sum of preimage sizes ( $\sum X_i = p^n$ ) and the sum of squared preimage sizes ( $\sum X_i^2 = p^{2n-m} + p^m N_bF$ ). This allows them to derive tight bounds on individual preimage set sizes.
Spectral Constraints of Plateaued Functions: They leverage the definition of plateaued functions, where Walsh coefficients are restricted to a specific set of values $\{0, \pm p^{(n+t)/2}\}$ . This restriction forces strong constraints on the possible value distributions.
Algebraic Number Theory: For odd primes $p$ , they utilize properties of cyclotomic fields to prove that certain Walsh coefficients must be integers, a crucial step in analyzing $d$ -to-1 functions.

3. Key Contributions and Results

A. General Bounds and Almost Balanced Functions

Theorem 3.3: The authors derive explicit upper and lower bounds for the size of any preimage set $|F^{-1}(\beta)|$ in terms of the image set size and the imbalance $N_bF$ .
Definition 3.7: They generalize the concept of almost balanced functions to non-surjective cases. A function is almost balanced if it achieves the bounds derived in Theorem 3.3 with equality, meaning all preimages have size $A$ except for one preimage of size $B$ .
Theorem 4.1: For a surjective, almost balanced plateaued function, the authors prove that all non-zero Walsh coefficients at zero must have the same magnitude and be integers. This leads to a precise characterization of the preimage sizes.

B. Plateaued $d$ -to-1 Functions and Monomials

Theorem 5.2: A major result establishing that a plateaued $d$ $d$ -to-1 function (where $d > 2$ $d > 2$ ) can only exist if $d = p^t + 1$ for some integer $t$ $t$ , and $n$ must be even.
- The function must have a specific mix of bent components and components with amplitude $p^{n/2+t}$ .
- The linearity is determined as $L(F) = p^{n/2+t}$ .
Corollary 5.4: Applied to monomials $F(x) = x^d$ , this implies that plateaued monomials are either permutations ( $d=1$ ) or $(p^t+1)$ -to-1 mappings.
Theorems 5.5 & 5.6: They derive bounds on differential uniformity. A plateaued $(p^t+1)$ -to-1 function has a differential uniformity of at least $p^t$ . It achieves exactly $p^t$ if and only if it is differentially 2-valued (the equation $F(x+a)-F(x)=b$ has either 0 or $p^t$ solutions).

C. Constructions of Almost Balanced Functions

The paper provides explicit constructions of surjective, almost balanced plateaued functions:

Monomials (Theorem 5.8): Functions of the form $F(x) = \text{Tr}_{n/2}^n(x^{2r+1})$ are shown to be almost balanced under specific conditions on $r$ and $n$ .
Maiorana-McFarland Functions (Propositions 5.9 & 5.10): The authors analyze generalized Maiorana-McFarland constructions, showing how specific choices of the permutation $\pi$ and function $\phi$ yield balanced or almost balanced plateaued functions with predictable value distributions.

D. Plateaued APN Functions

Imbalance Bounds (Proposition 6.3): For plateaued APN functions, the imbalance $N_bF$ $N_{b} F$ is bounded between $(2^{n+1}-2)/3$ $(2^{n + 1} - 2) /3$ and $2^{n+1}-2$ $2^{n + 1} - 2$ .
- The lower bound corresponds to functions with the maximum number of bent components.
- The upper bound corresponds to functions with no balanced components.
Parity of Bent Components (Proposition 6.5): The number of bent components in a plateaued APN function must be congruent to $2 \pmod 4$ .
Exclusion of Value Distributions (Theorem 6.7): The authors prove that plateaued APN functions with the minimum image set size cannot have the second possible value distribution listed in previous literature (specifically, the distribution with two preimages of size 2 and the rest of size 3).
Theorem 6.8: Plateaued APN functions with minimal image set size cannot have any balanced component functions.

4. Significance

Unified Framework: The paper provides a unified spectral framework for analyzing the value distributions of a wide class of cryptographic functions, moving beyond the specific case of bent or APN functions.
Existence Constraints: It imposes strict algebraic constraints on the existence of plateaued $d$ -to-1 functions, ruling out many potential candidates for cryptographic primitives based on their spectral properties.
Cryptographic Implications:
- The results on differential uniformity help in assessing the resistance of plateaued functions against differential cryptanalysis.
- The characterization of almost balanced functions is crucial for understanding the statistical properties of S-boxes and hash functions (e.g., in zero-knowledge proof systems like Poseidon and Rescue-Prime, which use monomial functions).
- The exclusion of specific value distributions for APN functions narrows the search space for the "Big APN" problem (finding APN permutations in even dimensions).
New Constructions: The paper offers new theoretical constructions (via Maiorana-McFarland and trace monomials) that guarantee specific value distributions, aiding in the design of primitives with desired balance and nonlinearity properties.

In summary, this work bridges the gap between spectral theory (Walsh transform) and combinatorial structure (value distribution), providing necessary conditions and explicit constructions for plateaued functions that are vital for modern symmetric cryptography.