🔢 mathematics

Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

This paper presents a hybrid computational search combining random sampling and Gröbner basis enumeration within a specific 40-dimensional self-equivalence subspace to discover 566 quadratic APN functions in dimension 8, including three previously unknown CCZ-equivalence classes that were missed by prior exhaustive databases.

Original authors: Oleksandr Kuznetsov

Published 2026-06-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Oleksandr Kuznetsov

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 trying to find a specific, incredibly rare type of lockpick (called an APN function) inside a massive, dark warehouse. This warehouse represents all possible mathematical functions of a certain size. The problem is that the warehouse is so huge (containing more possibilities than there are atoms in the universe) that if you just started walking around randomly, you would likely never find a single lockpick in your entire lifetime.

This paper describes a clever new strategy to find these rare lockpicks by using a "flashlight" and a "magnet" to navigate a specific, smaller section of the warehouse that was previously thought to be empty.

Here is the breakdown of their discovery using simple analogies:

1. The Problem: The Needle in the Cosmic Haystack

In the world of cryptography (the science of secret codes), these "lockpicks" are special mathematical tools used to scramble data so it can't be cracked by hackers. For a long time, mathematicians have been trying to find new, better lockpicks for a specific size of data (8 bits).

The Old Way: Previous researchers tried to find these by building a giant tree of possibilities, checking branch by branch. They looked at a specific, organized section of the warehouse (a "self-equivalence subspace") and concluded, "There is nothing here." They stopped looking.
The Reality: The authors of this paper say, "Wait a minute. That section isn't empty. You just missed the items because your tree-climbing method was too rigid."

2. The New Strategy: The Flashlight and the Magnet

The authors developed a two-step process to find these hidden lockpicks:

Step 1: The Flashlight (Random Sampling in a Structured Zone)
Instead of searching the whole universe, they focused on a specific, organized 40-dimensional "room" within the warehouse. They realized that while this room is tiny compared to the whole warehouse, the "lockpicks" are actually much more common inside this specific room than anywhere else.
They used a special map (called an RREF parameterization) to walk through this room randomly. They found hundreds of "center" lockpicks that were sitting right there, waiting to be discovered.
Step 2: The Magnet (The Gröbner Basis Search)
This is the magic trick. Once they found a "center" lockpick, they didn't just stop. They used a powerful mathematical tool called a Gröbner basis (think of it as a super-magnet) to scan the immediate neighborhood around that center.

Here is the surprising part: The magnet didn't just find more lockpicks in the same room. It pulled out new lockpicks that were hiding in the adjacent rooms, outside the organized section they started in.
- Analogy: Imagine you find a rare coin in a specific drawer. You use a magnet to scan the drawer, and suddenly, the magnet pulls out three other rare coins that were stuck to the bottom of the drawer, even though those coins technically belong to a different drawer entirely.

3. The Discovery: New Treasure Classes

Using this method, the team found 566 new lockpicks. They sorted them into six groups (classes):

Two groups were "known" types (like the famous Gold functions). These acted as gateways. When the authors used these known types as their starting point, the "magnet" pulled out the new, unknown types.
Four groups were completely new. These had never been seen before.
- One group (Class A) was found directly inside the organized room.
- Three groups (Classes B, C, and D) were found outside the room, but they were only discoverable because the "magnet" was attached to the known "gateway" lockpicks inside the room.

4. The Proof: Why It Matters

The authors didn't just guess these were new. They used a "fingerprint" system (called the ortho-derivative invariant) to check their findings against the world's largest databases, which contain millions of known lockpicks.

Result: Their four new groups did not match any of the millions of existing entries. They are genuinely new.
The "Empty Room" Myth: They proved that the previous researchers were wrong about the room being empty. The room wasn't empty; the previous search method just couldn't see the items because it was looking at them one by one, whereas this new method looks at the whole neighborhood at once.

5. The Big Lesson: The "Gateway" Phenomenon

The most important takeaway isn't just the new lockpicks, but how they were found.
The authors discovered that you can't just pick any random lockpick and hope to find new ones nearby. You have to start with a very specific, structured type (the "Gold" functions inside the organized room).

The Analogy: If you try to use a magnet on a random piece of junk in the warehouse, nothing happens. But if you use the magnet on a specific "gateway" object, it reveals a whole hidden world of new objects that were previously invisible.

Summary

This paper is about finding hidden mathematical treasures in a place everyone thought was empty. By using a smarter map to find a starting point and a powerful mathematical "magnet" to scan the surroundings, the authors found 566 new cryptographic tools, including four entirely new families that no one had ever seen before. They proved that sometimes, to find the new, you have to stand on the shoulders of the known, but you need the right tools to see what's hiding just beyond the edge.

Technical Summary: Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

Problem Statement
The classification of Almost Perfect Nonlinear (APN) functions over $\mathbb{F}_{2^n}$ up to CCZ-equivalence is a central problem in cryptography, particularly for $n=8$ . While the classification is complete for $n \leq 6$ , it remains partial for $n=8$ . The search space for quadratic APN functions is vast ( $2^{224}$ possible coefficient vectors), making global random search infeasible due to an estimated APN density of $\approx 2^{-n}$ . Previous systematic efforts, such as the recursive tree search by Beierle, Brinkmann, and Leander (BBL2021), explored structured algebraic subspaces defined by self-equivalence constraints. Specifically, BBL2021 reported finding zero APN functions within the 40-dimensional self-equivalence subspace $V_A$ associated with a linear automorphism $A$ of order 5 (class index 22). This paper investigates whether this subspace truly contains no APN functions or if the previous search method failed to locate them.

Methodology
The authors propose a two-phase computational pipeline that combines random sampling with algebraic enumeration to explore $V_A$ more effectively than the previous tree search.

Phase 1: Random Sampling via RREF Parameterization
The authors construct an explicit Reduced Row Echelon Form (RREF) parameterization of the 40-dimensional subspace $V_A = \{F : F \circ A = A \circ F\}$ . This reduces the search space from $2^{224}$ to $2^{40}$ . Within this subspace, the empirical density of APN functions is found to be approximately $10^{-4}$ (roughly 1 APN function per 11,000 random samples), making targeted sampling feasible. The authors perform random sampling to identify "APN centers" (functions in $V_A$ that are APN).
Phase 2: Gröbner Basis Slice Computation
For each APN center found in Phase 1, the authors define a 24-dimensional affine hyperplane (an "NL=4 slice") passing through that center. This is achieved by fixing 200 of the 224 Algebraic Normal Form (ANF) coefficients (specifically those corresponding to pairs with indices $p \leq 4$ ) to the values of the center, leaving 24 coefficients as unknowns.
The APN condition for the 255 non-zero differences is encoded as a system of polynomial equations over the Boolean ring. The authors use the Magma computer algebra system to compute a Gröbner basis for this system.
- If the system is infeasible, the slice contains no other APN functions.
- If the system has solutions, the Gröbner basis enumeration finds all APN functions within that specific 24-dimensional hyperplane.
  Crucially, while the center is guaranteed to be in $V_A$ , the solutions found by the Gröbner basis step are not constrained to $V_A$ ; they may lie outside the self-equivalence subspace.
Classification and Verification
Found functions are classified using the ortho-derivative invariant $\sigma(F)$ , which is proven to be a complete CCZ-invariant for quadratic APN functions (by Yoshiara's theorem and results from Canteaut et al.). The authors perform streaming comparisons of these signatures against three major databases: the BBL2021 pre-2020 compilation, the Beierle et al. 2025 database (containing $\approx 3.8$ million functions), and the classical Gold functions.

Key Results
The authors executed the pipeline on 428 distinct 24-dimensional slices (0.65% of the total $2^{16}$ possible slices in $V_A$ ).

Discovery of New Classes: The search yielded 566 unique quadratic APN functions falling into six CCZ-equivalence classes.
- Four New Classes (A, B, C, D): These 500 functions (362 in Class A, 72 in B, 36 in C, 30 in D) are not present in the Beierle 2025 database, the BBL2021 pre-2020 database, or the classical Gold families.
- Two Known Classes (E, F): These correspond to the Gold functions $x^3$ and $x^9$ (and their Frobenius orbits), serving as controls to validate the pipeline.
Structural Findings:
- Subspace Membership: A membership test ( $F \circ A = A \circ F$ ) revealed that Class A, E, and F lie entirely within $V_A$ . However, Classes B, C, and D lie entirely outside $V_A$ .
- The "Gateway" Phenomenon: The 138 functions in the new external classes (B, C, D) were found exclusively in slices centered on Gold functions (Classes E and F) that reside within $V_A$ . Slices centered on Class A functions yielded no neighbors outside $V_A$ .
- Failure of Alternative Seeds: Comparative experiments using 532 APN functions from the Beierle 2025 database (which are outside $V_A$ ) as slice centers resulted in zero APN neighbors found. This suggests that the "gateway" capability to discover new classes via Gröbner basis slicing is specific to functions within the self-equivalence subspace, not a generic property of all APN functions.

Significance and Claims
The paper claims several significant contributions to the field of APN function classification:

Correction of Previous Results: The authors demonstrate that the self-equivalence subspace $V_A$ (class index 22), previously reported by BBL2021 as containing no APN functions, actually contains at least four CCZ-classes of quadratic APN functions. The failure of the BBL2021 tree search is attributed to its branch-pruning strategy, which may have eliminated valid solutions in this structured subspace, whereas the Gröbner basis approach performs a complete enumeration within each slice.
Discovery of New Functions: The paper provides rigorous proof (via the ortho-derivative invariant) that four new CCZ-classes of quadratic APN functions exist for $n=8$ , distinct from the $\approx 3.8$ million functions in the largest known database.
Methodological Innovation: The paper introduces a "GB-navigation" mechanism. It posits that while global search is impossible, one can exploit structured subspaces with higher APN density to find "seed" functions. The Gröbner basis step then acts as a local enumerator, capable of stepping outside the subspace to find new classes. The authors emphasize that this mechanism is not generic; it relies on the specific algebraic structure of the self-equivalence subspace, as evidenced by the failure of non-subspace functions to act as productive seeds.
Completeness of the Ortho-Derivative: The work reinforces the utility of the ortho-derivative signature as an exact CCZ-invariant for quadratic functions, allowing for rigorous classification without exhaustive pairwise testing.

The authors conclude that their approach offers a systematic program for extending the classification of quadratic APN functions by exploring other BBL2021 class indices and utilizing the Gröbner basis slicing technique to navigate the APN landscape.