🔢 mathematics

On the Walsh spectra of quadratic APN functions

This paper establishes novel connections between the Walsh spectra of quadratic APN functions and vector space partitions or blocking sets in projective spaces, enabling the derivation of strong spectral conditions such as a limit on high-amplitude component functions, a nontrivial upper bound on bent components, and criteria for CCZ-equivalence to permutations.

Original authors: Sophie Hannah Bénéteau, Nicolas Goluboff, Lukas Kölsch, Divyesh Vaghasiya

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Sophie Hannah Bénéteau, Nicolas Goluboff, Lukas Kölsch, Divyesh Vaghasiya

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 designing a high-security vault (a block cipher) to protect digital secrets. To make this vault unbreakable, you need to install a special kind of "lock" inside it. In the world of cryptography, these locks are mathematical functions called APN functions.

Think of an APN function as a master key that scrambles data so perfectly that even if a thief tries to guess how the lock works by comparing two slightly different keys (a "differential attack"), they get absolutely no useful information. These functions are the gold standard for security.

However, not all locks are created equal. Some are "quadratic" (mathematically simpler and easier to study), and the researchers in this paper are trying to understand the internal "fingerprint" of these specific locks.

Here is what the paper discovers, explained through everyday analogies:

1. The Fingerprint: The Walsh Spectrum

Every lock has a unique "fingerprint" called the Walsh spectrum. You can think of this as a report card that measures how "linear" or predictable the lock is.

The Goal: We want the lock to be as unpredictable as possible.
The Metric: The paper looks at the "amplitude" of different parts of the lock. Imagine the lock is made of many smaller gears (component functions). Some gears spin smoothly (low amplitude), while others are jerky and loud (high amplitude). The researchers want to know: How many loud gears can a secure lock have before it becomes weak?

2. The First Discovery: The "Room Partition" Analogy

The authors found a surprising connection between these mathematical locks and dividing a room.

Imagine the space where the lock operates is a giant room filled with points (vectors). The researchers proved that the "loud gears" (the parts of the lock with high amplitude) force the room to be divided into specific, non-overlapping sub-rooms (vector spaces).

The Rule: Every point in the room must belong to exactly one sub-room, and no two sub-rooms can share any space except the center point.
The Insight: This isn't just a random division. The size of these sub-rooms is directly tied to how "loud" (high amplitude) the gears are. If you know how the room is partitioned, you know the fingerprint of the lock.

What this means: They proved that a secure lock can have at most one extremely "loud" gear (amplitude larger than a certain threshold). If it had two, the room couldn't be partitioned correctly, and the lock would fail the security test.

3. The Second Discovery: The "Traffic Jam" Analogy

The paper also looked at the "quiet gears" (bent components) versus the "loud gears." They discovered that the loud gears form a special kind of traffic jam (a "blocking set") in a geometric landscape.

The Analogy: Imagine a city grid where certain intersections are blocked. A "blocking set" is a collection of blocked intersections such that every possible straight road you try to drive down hits at least one blocked intersection.
The Discovery: The researchers found that for these quadratic locks, the "loud gears" create a traffic jam that is very specific. It's not just any jam; it's a jam where the number of blocked intersections on any road is always an odd number.
The Result: This "odd-number rule" allows them to set a strict limit on how many quiet gears (bent components) a lock can have. It's the first time a general "ceiling" has been placed on this number for these types of locks.

4. Putting It All Together: The "Blueprint" Check

By combining the "Room Partition" and the "Traffic Jam" rules, the authors created a powerful checklist.

They took locks of specific sizes (dimensions 6, 8, and 10) and listed every possible "blueprint" (amplitude distribution) that could theoretically exist.
Then, they applied their new rules to cross out the impossible blueprints.
Example: For a lock of size 8, there were many theoretical ways to arrange the gears. Their math showed that many of these arrangements are impossible because they would break the "Room Partition" or "Traffic Jam" rules. This narrowed down the list of possible secure locks significantly.

5. The "Permutation" Mystery

Finally, the paper touches on a famous unsolved mystery: Can these locks be rearranged to become a perfect "permutation" (a one-to-one mapping where every input has a unique output, like a perfect shuffle of a deck of cards)?

The authors found that if a lock is CCZ-equivalent (a specific type of mathematical similarity) to a perfect shuffle, it cannot have "few" loud gears. It must have a specific, large number of them. This gives cryptographers a new way to test if a lock can ever be a perfect shuffle.

Summary of the "Open Problems"

The paper ends by admitting that while they have built a better fence around the possible locks, they haven't found all the locks yet.

They have a list of theoretical blueprints for size-8 locks, but they haven't found physical examples for all of them.
They are asking the math community: "Can you build a lock that fits these specific, rare blueprints we found?"

In a nutshell: This paper didn't invent a new lock, but it built a much better blueprint scanner. It uses geometry (room partitions and traffic jams) to instantly tell you which mathematical designs for secure locks are impossible, narrowing the search for the perfect, unbreakable digital vault.

Technical Summary: On the Walsh Spectra of Quadratic APN Functions

Problem Statement
Almost Perfect Nonlinear (APN) functions are critical components in symmetric cryptosystems, providing optimal resistance against differential attacks. A fundamental property of these functions is their linearity, which is determined by their Walsh spectrum. While the amplitude distribution (and thus the Walsh spectrum) of quadratic APN functions is fully characterized for odd dimensions $n$ , the case for even $n$ remains largely open. The only known general constraint for even $n$ is derived from the fourth moment of the Walsh transform. This paper addresses the gap in understanding the possible Walsh spectra of quadratic APN functions $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ where $n$ is even, specifically seeking to derive stronger conditions on their amplitude distributions.

Methodology
The authors establish two novel geometric connections between quadratic APN functions and finite geometry:

Vector Space Partitions: The paper demonstrates that the amplitude distribution of a quadratic APN function uniquely corresponds to a vector space partition of the ambient space $\mathbb{F}_2^n$ . Specifically, the non-trivial non-bent component functions of $F$ are associated with subspaces in a partition where the dimension of each subspace is directly linked to the amplitude of the corresponding component function.
Blocking Sets: The set of non-trivial non-bent components, denoted $N_F$ , is shown to form a specific type of blocking set in the projective space $PG(n-1, 2)$. Crucially, the authors prove that the intersection of $N_F$ with any subspace of dimension $n/2$ must contain an odd number of points.

By leveraging established theorems on vector space partitions and blocking sets (specifically results regarding "tails" of partitions and minimal blocking sets), the authors translate these geometric constraints into algebraic bounds on the amplitude distributions of quadratic APN functions.

Key Contributions and Results

Connection to Vector Space Partitions (Section II):
- Theorem II.4 establishes that if a component function $F_b$ has amplitude $2^{(n+k)/2}$ , it corresponds to a subspace of dimension $k$ in a vector space partition of $\mathbb{F}_2^n$ .
- This connection allows the application of packing conditions and dimension bounds from partition theory.
- Theorem II.10: A quadratic APN function can have at most one component function with amplitude larger than $2^{3n/4}$ . If such a component exists, all others must have amplitude at most $2^{(2n-l)/2}$ , where $l$ is the exponent of the maximal amplitude.
- Propositions II.14–II.16: New lower bounds on the number of non-bent components ( $|N_F|$ ) are derived based on the linearity and the presence of specific amplitudes.
Connection to Blocking Sets (Section III):
- Corollary III.3: The set $N_F$ is a blocking set in $PG(n-1, 2)$ with respect to $(n/2)$ -spaces, with the additional property that every such space intersects $N_F$ in an odd number of points.
- Theorem III.9: This is the first non-trivial, general upper bound on the number of bent component functions for a quadratic APN function. Specifically, for $n \ge 6$ , the number of non-bent components satisfies $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ . Equality is possible only if $n=8$ . Consequently, the number of bent components is at most $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$ .
Synthesis and Dimensional Analysis (Section IV):
- By combining the partition and blocking set constraints, the authors eliminate several theoretically possible amplitude distributions.
- Theorem IV.1: Vector space partitions of type $[(n/2)^{2^{n/2+1}}]$ (an $(n/2)$ -spread) do not correspond to any quadratic APN function.
- Theorem IV.5: For $n=8$ , the paper narrows the possible amplitude distributions to a specific list (excluding the trivial partition and the 4-spread), reducing the number of potential extended Walsh spectra to at most 18 distinct types.
- Proposition IV.4: The paper compares the strength of the derived lower bounds on $|N_F|$ across different parameter ranges, identifying which bound is dominant depending on the linearity of the function.
Equivalence and Permutations (Section V):
- The paper analyzes how these structures behave under EA-equivalence and CCZ-equivalence.
- Corollary V.6: If a quadratic APN function is CCZ-equivalent to a permutation, it cannot have few non-bent components; specifically, $|N_F| \ge 3(2^{n/2}-1)$ , and $N_F$ must be a 3-fold blocking set.

Significance and Claims
The paper claims to provide the first general conditions on the Walsh spectra of quadratic APN functions beyond the well-known fourth-moment bound. By linking the algebraic properties of these functions to the combinatorial structures of vector space partitions and blocking sets, the authors derive strong constraints on the possible amplitude distributions.

The authors explicitly state that their results:

Prove that a quadratic APN function can have at most one component with amplitude greater than $2^{3n/4}$ .
Provide the first non-trivial upper bound on the number of bent components.
Offer conditions to determine if a function is CCZ-equivalent to a permutation based on its number of bent components.
Systematically list all possible amplitude distributions for small even dimensions (specifically $n=6, 8, 10$ ), highlighting which are realized and which remain open problems.

The paper concludes by listing open problems, including the existence of APN functions with specific amplitude distributions in dimension 8 and the search for infinite families of quadratic APN functions with non-classical Walsh spectra. The authors maintain a modest tone, noting that while they have excluded many possibilities, the complete classification of Walsh spectra for quadratic APN functions remains an open challenge.