🔢 mathematics

Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$

This paper establishes infinite families of new, mutually CCZ-inequivalent Almost Perfect Nonlinear (APN) permutations over $\mathbb{F}_{2^{3m}}$ by extending two trivariate constructions of Li and Kaleyski, proving that specific scalar parameters yield APN permutations if and only if an associated univariate polynomial has no roots in $\mathbb{F}_{2^m}^*$ , and demonstrating that these new families are distinct from the original and from each other under diagonal and CCZ equivalence.

Original authors: Daniele Bartoli, Pantelimon Stanica

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Daniele Bartoli, Pantelimon Stanica

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 a master locksmith trying to design the perfect lock for a high-security vault. In the world of cryptography, this "lock" is a mathematical function called an APN Permutation.

APN (Almost Perfect Nonlinear): This means the lock is incredibly resistant to "picking" via a specific type of attack called differential cryptanalysis. If a thief tries to wiggle the key slightly to see how the lock reacts, the reaction is so chaotic and unpredictable that they can't figure out the combination.
Permutation: This means the lock is reversible. If you put a key in, you get a unique output, and you can always turn it back to get the original key. No two keys produce the same result, and no result is left empty.

For a long time, finding locks that are both perfectly secure (APN) and perfectly reversible (Permutations) in even-numbered dimensions has been like finding a needle in a haystack. Only a few specific, "lucky" locks were known.

The Story of This Paper

Two researchers, Daniele Bartoli and Pantelimon Stănică, have just discovered two infinite families of these perfect locks. They didn't just find one; they found a whole factory that can produce them.

Here is the breakdown of their discovery using simple analogies:

1. The "Recipe" for the Locks

The authors are working with a specific type of mathematical structure involving three variables (let's call them x, y, and z). Think of these as three dials on a combination lock.

They took two "lucky" locks that were previously discovered by other scientists (Li and Kaleyski) and asked: "What if we tweak the ingredients?"

In the original recipes, the ingredients (coefficients) were fixed numbers (like always using 1). The authors asked, "What if we let the ingredients be any number we want from a specific pool?"

They created two new families of recipes, which they named Family G and Family H.

Family G: A specific mix of the three dials with a "magic number" (let's call it $a$ ) mixed in.
Family H: A slightly different mix, also using the magic number $a$ .

2. The "Magic Number" Test

The big question is: Which values of $a$ actually make a perfect lock?

If you pick the wrong $a$ , the lock might jam (it won't be a permutation) or it might be easy to pick (it won't be APN).

The authors discovered a brilliant shortcut. Instead of testing every single $a$ by trying to break the lock, they found a single, simple test:

They wrote down a specific polynomial equation (a math formula) involving $a$ .
The Rule: If this equation has no solutions (no "roots") in the number system you are using, then $a$ is a good magic number.
If the equation does have a solution, the lock is broken or insecure.

This is like having a metal detector that beeps only if the lock is bad. If it stays silent, you know you have a perfect, secure lock.

3. The "Double-Edged Sword"

Here is the coolest part: The authors proved that for these specific families, being a permutation and being APN are the same thing.

Usually, a lock can be reversible but insecure, or secure but jammed.
In these families, if the lock is reversible, it is automatically secure. If it's secure, it's automatically reversible. You get the best of both worlds with one single test.

4. Are These New Locks or Just Old Ones in Disguise?

In cryptography, two locks are considered "the same" if you can easily transform one into the other (like repainting a car or changing the key shape slightly). This is called equivalence.

The authors asked: "Are these new families just the old Li-Kaleyski locks wearing a mask?"

They proved:

Mostly No: For almost all "good" magic numbers $a$ , these new locks are genuinely new. They are structurally different from the old ones.
The Exception: Only if the magic number $a$ satisfies a very specific, rare condition (mathematically, $a^{q^2+q+1} = 1$ ) does the new lock turn out to be an old lock in disguise.
Family G vs. Family H: They also proved that a lock from Family G can never be transformed into a lock from Family H. They are two completely different species of perfect locks.

5. Why Does This Matter?

More Options: Before this, we had very few options for these perfect locks. Now, we have an infinite supply.
Better Security: Having many different, non-equivalent locks makes it much harder for hackers to find a universal "master key" that breaks all of them.
Quantitative Guarantee: The authors didn't just say "they exist." They gave a mathematical formula to estimate how many good magic numbers exist. For large systems, there are thousands of them.

The Bottom Line

Think of this paper as a blueprint for a factory.

We have two assembly lines (Family G and Family H).
We have a quality control scanner (the root test) that instantly tells us if a batch of "magic numbers" will produce a perfect lock.
We know that almost every number that passes the scanner creates a brand new, unique, and ultra-secure lock that has never been seen before.

This solves a major puzzle in cryptography, providing a vast new playground of secure building blocks for future digital security systems.

1. Problem Statement and Context

The construction of Almost Perfect Nonlinear (APN) permutations over finite fields is a central challenge in cryptography and coding theory. APN functions offer optimal resistance against differential cryptanalysis, and when they are also permutations, they serve as ideal S-boxes. However, constructing such functions is notoriously difficult; only a few infinite families are known, and their existence in every even dimension remains an open problem.

Recent work by Li and Kaleyski (2024) generalized two sporadic quadratic APN permutations found in dimension 9 into infinite families of trivariate functions over $\mathbb{F}_{2^{3m}}$ with scalar coefficients restricted to $\mathbb{F}_2$ .

The Core Problem: This paper investigates the generalization of these families where the scalar coefficient is allowed to range freely over the multiplicative group $\mathbb{F}_{2^m}^*$ . The authors aim to:

Characterize the conditions under which these generalized functions are permutations and APN.
Quantify the number of valid parameters.
Determine the equivalence classes of these new functions relative to existing families (specifically the Li–Kaleyski representatives).

2. Methodology

The authors employ a combination of algebraic geometry, finite field theory, and polynomial analysis.

Trivariate Definitions: Two families of functions $G_a, H_a: \mathbb{F}_{2^m}^3 \to \mathbb{F}_{2^m}^3$ $G_{a}, H_{a} : F_{2^{m}}^{3} \to F_{2^{m}}^{3}$ are defined, where $q = 2^i$ $q = 2^{i}$ with $\gcd(i, m) = 1$ $g cd (i, m) = 1$ and $m$ $m$ is odd.
- $G_a(x, y, z) = (x^{q+1} + ax^qz + yz^q, \ x^qz + y^{q+1}, \ xy^q + ay^qz + z^{q+1})$
- $H_a(x, y, z) = (x^{q+1} + axy^q + yz^q, \ xy^q + z^{q+1}, \ x^qz + y^{q+1} + ay^qz)$
Root-Theoretic Characterization: The authors reduce the multivariate permutation and APN problems to the study of univariate polynomials over $\mathbb{F}_{2^m}$ . They prove that the permutation property and the APN property are equivalent for these families and are both governed by the absence of roots of specific polynomials in $\mathbb{F}_{2^m}^*$ .
Algebraic Geometry Tools: To count the number of "good" parameters (those yielding APN permutations), the authors utilize the Lang–Weil bound and the Hasse–Weil bound. They analyze the collision curve associated with the parameter mapping function $g(u) = \frac{u^d+1}{u}$ (where $d = q^2+q+1$ ) to estimate the size of the image and the complement (the set of good parameters).
Equivalence Analysis: The paper investigates CCZ-equivalence (Carlet–Charpin–Zinoviev). For quadratic APN functions vanishing at zero, the authors leverage recent results (Shi et al., 2025) to show that CCZ-equivalence reduces to EL-equivalence (Extended Linear), which in turn reduces to diagonal equivalence for these specific trivariate forms. This allows them to use algebraic systems to prove non-equivalence.

3. Key Contributions and Results

A. Characterization of APN Permutations

The paper establishes that for both families $G_a$ and $H_a$ , the following are equivalent:

The function is a permutation.
The function is APN.
A specific associated univariate polynomial has no roots in $\mathbb{F}_{2^m}^*$ .

For $G_a$ , the condition is that $Q_a(T) = T^{q^2+q+1} + aT + 1$ has no roots in $\mathbb{F}_{2^m}$ .
For $H_a$ , the condition involves a polynomial $P'_a(T)$ which is shown to be root-equivalent to $Q_a(T)$ .
Implication: The same set of parameters $a$ yields APN permutations for both families.

B. Existence and Quantitative Bounds

Lower Bound: The authors derive a quantitative lower bound on the number of good parameters $a \in \mathbb{F}_{2^m}^*$ . Let $d = q^2+q+1$ . The number of good parameters is at least:
$\frac{2^m + 1 - (d-1)(d-2)2^{m/2} - d}{d}$
This proves the existence of infinite families of APN permutations for any odd $m$ .
Binary Case ( $q=2$ ): When $q=2$ , the condition simplifies. The authors prove that $a=1$ is a "good" parameter (yielding an APN permutation) if and only if $7 \nmid m$ . This recovers the Li–Kaleyski family as a special case.

C. Non-Equivalence Results

The paper provides strong results regarding the novelty of these families:

Diagonal Equivalence to Li–Kaleyski: $G_a$ $G_{a}$ (or $H_a$ $H_{a}$ ) is diagonally equivalent to the Li–Kaleyski representative ( $G_1$ $G_{1}$ or $H_1$ $H_{1}$ ) if and only if $a^{q^2+q+1} = 1$ $a^{q^{2} + q + 1} = 1$ .
- For $q=2$ and $7 \nmid m$ , the only solution is $a=1$ . Thus, every other good parameter $a \neq 1$ produces an APN permutation that is CCZ-inequivalent to the Li–Kaleyski family.
Mutual Inequivalence: For $m > 4, m \neq 6, 7 \nmid m$ $m > 4, m \neq = 6, 7 ∤ m$ , no member of the $G_a$ $G_{a}$ -family is CCZ-equivalent to any member of the $H_b$ $H_{b}$ -family (for the same $q$ $q$ ).
- This proves that the two families provide genuinely new, mutually inequivalent sources of APN permutations.

4. Significance

Expansion of Known Families: The paper significantly expands the known landscape of APN permutations by generalizing sporadic examples into infinite families with a free parameter $a$ .
Reduction to Univariate Problems: It demonstrates that complex multivariate APN/permutation problems can be reduced to checking the root-freeness of specific univariate polynomials, a much more tractable algebraic problem.
New CCZ Classes: By proving that the vast majority of parameters yield functions CCZ-inequivalent to known families (and to each other), the paper confirms the existence of a large number of distinct cryptographic primitives.
Methodological Advancement: The application of algebraic geometry (Lang–Weil/Hasse–Weil bounds) to count good parameters in constrained trivariate classes offers a robust framework for future constructions.

5. Open Problems

The authors conclude with several open questions:

Characterizing good parameters explicitly for the case $7 \mid m$ (where $a=1$ fails).
Extending the "Type I" permutations found computationally for $m=3$ to infinite families.
Investigating whether analogous constructions exist for even dimensions $m$ .
Generalizing these $n$ -variate constructions ( $n > 3$ ) and determining if the root-criterion approach generalizes.

In summary, this paper provides a rigorous algebraic foundation for a new class of APN permutations, proving their existence, quantifying their abundance, and establishing their distinctness from all previously known infinite families.