🔢 mathematics

Triprojective almost perfect nonlinear permutations and functions

This paper introduces a large family of almost perfect nonlinear (APN) permutations for finite vector spaces of odd dimensions divisible by three, as well as non-bijective APN functions for even dimensions, all characterized by a triprojective structure induced by the general linear group $\mathrm{GL}(3,2^m)$ .

Original authors: Faruk Göloğlu, Lukas Kölsch

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Faruk Göloğlu, Lukas Kölsch

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 ultimate safe. In the world of digital security, the "locks" are mathematical functions used to scramble data so that hackers can't figure out the original message. The paper you're asking about is a blueprint for building a new, incredibly strong type of lock.

Here is the story of what the authors, Faruk Gölöglu and Lukas Kölsch, have discovered, explained without the heavy math jargon.

The Goal: The Perfect Scrambler

In cryptography, there is a specific type of lock called an S-Box (Substitution Box). Think of an S-Box as a machine that takes a set of inputs (like a combination of numbers) and spits out a completely different set of outputs.

The danger comes from a method called "differential cryptanalysis." Imagine a thief trying to crack your safe by noticing patterns: "If I turn the dial one click to the right, the lock changes its sound by a specific amount. If I turn it two clicks, the sound changes differently." If the lock reacts too predictably to small changes, the thief can work backward to find the key.

To stop this, mathematicians look for APN functions (Almost Perfect Nonlinear). These are the "perfect" locks where a tiny change in the input causes a chaotic, unpredictable change in the output. The goal is to make it so that no matter how the thief tweaks the input, the output looks like random noise.

The Big Challenge: The "Even Dimension" Problem

For a long time, mathematicians knew how to build these perfect locks for certain sizes of data (specifically, when the data size is an odd number). But for even-sized data blocks (which are very common in real-world computers), finding a perfect lock that is also a permutation (meaning every single input maps to a unique output, so nothing gets lost) has been a massive headache. It's like trying to find a key that fits every lock in a specific row of houses, but you keep finding that some keys open two locks at once, or some locks have no key at all.

The authors of this paper say: "We found a way to build these perfect, non-repeating locks for a huge new family of even-sized data blocks."

The Secret Ingredient: "Triprojective" Architecture

The authors didn't just stumble upon a random formula. They built their locks using a specific architectural style they call "Triprojective."

To understand this, imagine you are looking at a 3D sculpture.

Standard Locks: Usually, these are built by looking at the sculpture from just one angle (a flat, 2D view).
The New "Triprojective" Locks: The authors built their function by looking at the sculpture from three different angles simultaneously, using a special group of rules (related to a mathematical structure called $GL(3, 2^m)$ ).

They call this a "Triprojective" structure because it treats the data as if it exists in a 3D space where the rules of geometry are slightly twisted. By arranging the data this way, they ensure that the "scrambling" happens in a way that is incredibly hard to predict, regardless of how you try to probe it.

The Magic Formula

The paper presents a specific recipe (a formula) for these locks. It involves three variables ( $x, y, z$ ) and some special numbers ( $a, b, c$ ).

The recipe has a "safety check." Before you can use the lock, you have to run a quick test to make sure a specific equation has no solutions.

If the test passes: You get a perfect, unbreakable lock (an APN permutation).
If the test fails: The lock is still very strong (highly nonlinear), but it might not be a perfect permutation (some inputs might map to the same output).

The authors prove that if you choose your numbers correctly, this recipe works for every odd dimension that is divisible by three. This is a massive expansion of what was previously known.

Why This Matters (According to the Paper)

It Unifies Old Discoveries: The authors show that several other complicated formulas discovered by different mathematicians in recent years are actually just special, simplified versions of their new "Triprojective" recipe. It's like realizing that three different types of cars are actually just different paint jobs on the same chassis.
It's New and Unique: They prove that their new family of locks is fundamentally different from the "Gold" locks (a famous family of APN functions discovered decades ago). They aren't just re-labeling old keys; they are forging entirely new ones.
The Proof is "Clean": Previous attempts to prove these locks worked required massive computer simulations and pages of complex algebra. The authors used a clever, purely logical approach (using "twisted polynomials" and properties of finite fields) to prove their results without needing a supercomputer.

The Bottom Line

This paper is a mathematical breakthrough in the design of digital security locks. The authors have discovered a new, versatile "Triprojective" method to construct Almost Perfect Nonlinear Permutations.

In simple terms: They found a new, reliable way to build the strongest possible data scramblers for a wide range of computer data sizes, solving a problem that had stumped experts for years. They didn't just find one new lock; they found a whole factory for making them, and they proved that these new locks are distinct from any others we've seen before.

Technical Summary: Triprojective Almost Perfect Nonlinear Permutations and Functions

Problem Statement
The paper addresses the existence and construction of Almost Perfect Nonlinear (APN) permutations over finite vector spaces of even dimension. In the context of differential cryptanalysis, APN functions (those with differential uniformity $\Delta_F = 2$ ) are critical for designing secure S-Boxes in substitution-permutation networks. While APN functions are known to exist for odd dimensions, the existence of APN permutations (bijections) for even dimensions $n > 6$ remains a major open problem. Specifically, the authors focus on constructing large families of such functions in dimensions $n = 3m$ (where $m$ is odd) and characterizing their properties, including their equivalence classes and image set sizes.

Methodology
The authors employ a structural approach based on "triprojective" and "semi-quadratic" maps. The methodology proceeds through the following steps:

Projective Structure: The authors define a class of functions $F \in SQH(3, q)$ (semi-quadratic homogeneous) over $\mathbb{F}_q^3$ (where $q=2^m$ ). These functions are induced by semi-quadratic forms that satisfy specific homogeneity properties, allowing them to induce well-defined maps on the projective space $\mathbb{P}^2(\mathbb{F}_q)$ .
Bijection Criteria: Relying on previous work (Theorem 1.2), the paper utilizes a condition on a specific univariate polynomial $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ to ensure that the induced map on the projective space is a bijection.
Differential Uniformity Analysis:
- Case $m/d$ is even: The authors utilize the concept of the "core" of the function (a subfield over which the derivative map is linear) to show that the differential uniformity is $2d$ , where $d = \gcd(k, m)$ .
- Case $m/d$ is odd: The authors introduce tools from the theory of twisted polynomial rings (Ore rings) $\mathbb{F}_q[t; \sigma]$ . They establish a connection between the roots of the polynomial $P(X)$ and the existence of linear right divisors in the twisted ring. By extending the field and analyzing the least common left multiple (lclm) of polynomials, they prove that the differential uniformity remains $2d$ even in this more complex case.
Equivalence and Classification: The paper compares the new family to existing trivariate APN functions (specifically those by Li-Kaleyski and Bartoli-Stanica) using linear equivalence. Furthermore, it proves inequivalence to Gold APN functions ( $x^{2^i+1}$ ) by analyzing the linear automorphism groups ( $Aut_L(F)$ ) and showing they cannot be conjugate in the general linear group.

Key Contributions and Results

Construction of APN Permutations: The paper presents a large family of APN permutations for finite vector spaces of dimension $n=3m$ where $m$ is odd. The functions are defined as:
$F(x, y, z) = (x^{\sigma+1} + ay^\sigma z + bx^\sigma y + cx^\sigma z, \quad ay^{\sigma+1} + z^\sigma x + bz^\sigma y + cx^\sigma y, \quad z^{\sigma+1} + x^\sigma y)$
where $\sigma = 2^k$ , $a, b, c \in \mathbb{F}_q$ , and $a \neq 0$ .
Differential Uniformity: The authors prove that if the polynomial equation $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$ has no solution in $\mathbb{F}_q$ , the differential uniformity of $F$ is $2d$ (where $d = \gcd(k, m)$ ). Consequently, when $d=1$ and $m$ is odd, $F$ is an APN permutation.
Image Set Size: The paper characterizes the image set size of these functions. If $m/d$ is even, the function is $(2d+1)$ -to-one on $\mathbb{F}_q^3 \setminus \{0\}$ . If $m/d$ is odd, the function is bijective on $\mathbb{F}_q^3$ .
Unification of Existing Families: The authors demonstrate that several recently discovered families of trivariate APN functions (Li-Kaleyski and Bartoli-Stanica) are linearly equivalent to specific instances of their proposed family (obtained by setting specific parameters $a, b, c$ ). This provides a unified, elementary explanation for these constructions, avoiding the complex case distinctions and computer-assisted resultant calculations used in prior proofs.
Inequivalence to Gold Functions: The paper proves that for $m > 2$ and $m \neq 6$ , the constructed APN functions are CCZ-inequivalent to Gold APN functions. This is established by showing that their linear automorphism groups are not conjugate in $GL(3m, 2)$.

Significance and Claims
The paper claims to provide a "large family" of APN permutations in every odd dimension divisible by three, addressing the open question of APN bijections for even dimensions. The significance lies in:

Generality: The construction yields provably exponentially many pairwise inequivalent APN functions within the class of multiprojective maps.
Simplification: The proofs are described as "computer-free, much shorter and purely elementary" compared to previous works, offering a unified framework for understanding various trivariate APN functions.
New Examples: The family is shown to contain examples that are inequivalent to known APN functions (including Gold functions), expanding the known landscape of cryptographic primitives.

The authors note that while the Walsh spectra are known for the case where $m/d$ is even, determining the Walsh spectrum for the APN permutations (where $m$ is odd) remains an open problem. They also identify the classification of semi-quadratic homogeneous functions that lead to projective bijections as a natural direction for future research.