🔢 mathematics

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

Diese Arbeit stellt zwei unendliche Familien von APN-Permutationen auf $\mathbb{F}_{2^{3m}}$ vor, die durch verallgemeinerte trivariate Polynome definiert sind, und beweist deren Existenz, Charakterisierung sowie starke Nichtäquivalenz zu bestehenden Konstruktionen.

Ursprüngliche Autoren: Daniele Bartoli, Pantelimon Stanica

Veröffentlicht 2026-03-17

📖 4 Min. Lesezeit🧠 Tiefgang

CC0 1.0

Ursprüngliche Autoren: Daniele Bartoli, Pantelimon Stanica

Originalarbeit unter CC0 1.0 der Gemeinfreiheit gewidmet (http://creativecommons.org/publicdomain/zero/1.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Architekt, der unsichtbare, aber extrem sichere Schlösser für die digitale Welt baut. In der Welt der Kryptografie (also der Geheimcodes, die unsere Bankdaten und Nachrichten schützen) sind diese Schlösser sogenannte S-Boxen. Sie müssen zwei Dinge gleichzeitig perfekt können:

Unknackbar sein: Sie müssen so verwirrend sein, dass ein Hacker, der versucht, das Schloss durch systematisches Raten zu knacken (ein Angriff namens "Differential Cryptanalysis"), sofort scheitert. In der Mathematik nennt man diese Eigenschaft APN (Almost Perfect Nonlinear).
Umkehrbar sein: Sie müssen ein perfektes Schloss sein, das sich immer wieder öffnen und schließen lässt, ohne dass Teile verloren gehen. Das nennt man eine Permutation.

Das Problem? Solide Schlösser, die beides können, sind extrem selten. Bisher kannte man nur ein paar wenige Beispiele, und es war ein großes Rätsel, ob man sie in jeder Größe bauen kann.

Die Entdeckung: Ein neuer Bauplan

In diesem Papier stellen zwei Forscher, Daniele Bartoli und Pantelimon Stănică, einen neuen, genialen Bauplan vor. Sie haben zwei riesige Familien von solchen Schlössern entdeckt, die sie $G_a$ und $H_a$ nennen.

Stellen Sie sich diese Schlösser nicht als einzelne Objekte vor, sondern als unendliche Serien. Jeder einzelne Schlüssel in dieser Serie wird durch einen einzigen Zahl-Parameter (nennen wir ihn $a$ ) bestimmt.

Die alte Idee: Ein anderer Forscher-Team (Li und Kaleyski) hatte bereits zwei spezielle Schlösser gefunden, die nur mit dem Parameter $a=1$ funktionierten.
Die neue Idee: Die Autoren dieses Papiers sagen: "Warten Sie mal! Was, wenn wir den Parameter $a$ nicht auf 1 beschränken, sondern ihn frei durch eine ganze Welt von Zahlen ( $\mathbb{F}_{2^m}$ ) wandern lassen?"

Das große Rätsel: Welche Zahl $a$ funktioniert?

Nicht jede Zahl $a$ ergibt ein gutes Schloss. Wenn man die falsche Zahl wählt, ist das Schloss entweder nicht umkehrbar (es klemmt) oder nicht sicher genug (es lässt sich leicht knacken).

Die Forscher haben nun einen magischen Schlüssel gefunden, um zu erkennen, welche Zahlen $a$ funktionieren.
Stellen Sie sich vor, für jede Zahl $a$ gibt es eine kleine mathematische Maschine (ein Polynom), die man anwirft.

Wenn diese Maschine keine Nullstelle (kein "Ruhepunkt") findet, dann ist das Schloss perfekt: Es ist sicher (APN) und umkehrbar (Permutation).
Findet sie eine Nullstelle, ist das Schloss defekt.

Das ist der Durchbruch: Sie haben ein riesiges, komplexes 3D-Problem (wie funktioniert das ganze Schloss?) auf ein einfaches 1D-Problem reduziert (findet diese eine Maschine eine Nullstelle?).

Die Ergebnisse im Detail

Ein riesiger Vorrat an guten Schlössern:
Die Forscher haben berechnet, dass es in fast jeder Größe dieser Schlösser eine riesige Anzahl an guten Parametern $a$ gibt. Es ist nicht nur ein oder zwei, sondern hunderte oder tausende. Sie haben sogar eine Formel, die garantiert, dass es immer genug gute Kandidaten gibt.
Der Spezialfall $a=1$ :
Wenn die Größe des Schlössers bestimmte Eigenschaften hat (wenn die Zahl 7 die Größe nicht teilt), dann funktioniert der Parameter $a=1$ immer. Das bestätigt die alte Entdeckung von Li und Kaleyski, zeigt aber auch, dass es daneben noch viele andere gute Zahlen gibt.
Zwei verschiedene Familien:
Es gibt zwei Familien: $G_a$ und $H_a$ .
- Überraschung: Wenn eine Zahl $a$ für Familie $G$ ein gutes Schloss baut, baut sie automatisch auch für Familie $H$ ein gutes Schloss.
- Noch wichtiger: Diese beiden Familien sind völlig unterschiedlich! Man kann kein Schloss aus Familie $G$ durch einfaches Umdrehen oder Verschieben in ein Schloss aus Familie $H$ verwandeln. Sie sind wie zwei verschiedene Arten von Schlössern (z. B. Zylinderschloss vs. Hängeschloss), die beide sicher sind, aber grundlegend anders funktionieren.
Neuheit:
Die meisten dieser neuen Schlösser (für $a \neq 1$ ) sind wirklich neu. Sie sind nicht einfach nur eine verschlüsselte Version der alten Schlösser von Li und Kaleyski. Sie bieten völlig neue, bisher unbekannte Strukturen für die Kryptografie.

Warum ist das wichtig?

In der digitalen Welt brauchen wir immer mehr und sicherere Verschlüsselungsmethoden. Je mehr verschiedene, sichere "Schlüssel" wir haben, desto schwerer ist es für Hacker, das gesamte System zu kompromittieren.

Dieses Papier sagt im Grunde: "Wir haben nicht nur ein neues Schloss gefunden, sondern eine ganze Fabrik, die unendlich viele verschiedene, hochsichere und umkehrbare Schlösser produzieren kann." Und sie haben sogar eine Anleitung (die mathematische Bedingung), wie man die besten Rohstoffe ( $a$ ) auswählt, um keine defekten Schlösser zu bauen.

Zusammenfassend: Die Autoren haben einen Weg gefunden, wie man aus einem einzigen mathematischen Bauplan unzählige neue, extrem sichere digitale Schlösser herstellt, und sie haben bewiesen, dass diese Schlösser wirklich neuartig und einzigartig sind.

Titel und Autoren

Titel: Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$
Autoren: Daniele Bartoli (Universität Perugia) und Pantelimon Stănică (Naval Postgraduate School)
Datum: März 2026 (vorläufige Version)

1. Problemstellung

Die Konstruktion von Permutationspolynomen über endlichen Körpern mit einfacher algebraischer Struktur in mehreren Variablen ist ein herausforderndes Problem mit erheblichen Anwendungen in der Kryptographie (insbesondere bei S-Boxen) und der Kodierungstheorie.

Hintergrund: Fast perfekt nichtlineare (APN) Funktionen sind optimal gegen differentielle Kryptoanalyse. Wenn eine solche Funktion gleichzeitig eine Permutation ist, stellt sie einen idealen Baustein dar.
Aktueller Stand: Die Existenz von APN-Permutationen in jeder geraden Dimension ist ein offenes Problem. Es gibt nur wenige bekannte unendliche Familien.
Ausgangspunkt: Li und Kaleyski (2024) generalisierten zwei sporadische quadratische APN-Permutationen aus der Dimension 9 in unendliche Familien trivariater Funktionen mit Koeffizienten in $\mathbb{F}_2$ .
Ziel dieses Papers: Die Verallgemeinerung dieser Arbeit, indem der skalare Koeffizient nicht auf $\mathbb{F}_2$ beschränkt ist, sondern frei über $\mathbb{F}_{2^m}^*$ variieren darf. Es werden zwei verallgemeinerte Familien, $G_a$ und $H_a$ , untersucht.

2. Methodik

Die Autoren nutzen Methoden der algebraischen Geometrie und der Theorie endlicher Körper, um die Permutations- und APN-Eigenschaften der untersuchten Funktionen zu charakterisieren.

Algebraische Reduktion: Die Untersuchung der Permutations- und APN-Eigenschaften wird auf die Analyse von Nullstellen bestimmter univariater Polynome zurückgeführt.
Werkzeuge der algebraischen Geometrie:
- Verwendung des Satzes von Lang-Weil (Theorem 1.1) zur Abschätzung der Anzahl rationaler Punkte auf Varietäten.
- Anwendung des Aubry–McGuire–Rodier-Lemmas (Lemma 1.2) für projektive Hyperschalen.
- Nutzung der Lang-Weil-Schranke, um die Existenz von Kollisionen (und damit das Versagen der Permutations- oder APN-Eigenschaft) bei Vorhandensein von Nullstellen nachzuweisen.
Äquivalenzanalyse: Unterscheidung zwischen verschiedenen Äquivalenzbegriffen (affin, linear, diagonal, CCZ). Für quadratische APN-Funktionen mit $F(0)=0$ zeigen die Autoren, dass CCZ-Äquivalenz, EA-Äquivalenz und EL-Äquivalenz (erweitert linear) zusammenfallen.

3. Hauptbeiträge und Ergebnisse

A. Charakterisierung der Familie $G_a$

Die erste Familie ist definiert als:
$G_a(x, y, z) = (x^{q+1} + ax^qz + yz^q, \ x^qz + y^{q+1}, \ xy^q + ay^qz + z^{q+1})$
mit $a \in \mathbb{F}_{2^m}^*$ , $q=2^i$ , $\gcd(i, m)=1$ und $m$ ungerade.

Hauptsatz (Theorem 2.7): Für die Familie $G_a$ sind die folgenden Aussagen äquivalent:
1. Das Polynom $Q_a(T) = T^{q^2+q+1} + aT + 1$ hat keine Nullstelle in $\mathbb{F}_{2^m}$ .
2. $G_a$ ist eine Permutation auf $\mathbb{F}_{2^m}^3$ .
3. $G_a$ ist eine APN-Funktion auf $\mathbb{F}_{2^m}^3$ .
- Bedeutung: Das komplexe Problem der dreidimensionalen Permutation/APN-Eigenschaft wird auf ein einfaches Problem der Nullstellenvermeidung eines univariaten Polynoms reduziert.
Existenz und quantitative Schranke (Theorem 2.12):
- Es wird gezeigt, dass "gute" Parameter $a$ (solche, bei denen $Q_a$ keine Nullstelle hat) existieren.
- Eine quantitative untere Schranke für die Anzahl der guten Parameter wird hergeleitet:
  $|B_{m,q}| \geq 2^m + 1 - \frac{(d-1)(d-2)2^{m/2} - d}{d}$
  wobei $d = q^2 + q + 1$ .
- Spezialfall $q=2$ : Wenn $7 \nmid m$ , dann ist $a=1$ ein guter Parameter (Wiederherstellung der Li–Kaleyski-Familie). Für $a \neq 1$ mit $a^7 \neq 1$ ergeben sich neue, CCZ-inkquivalente Permutationen.

B. Charakterisierung der Familie $H_a$

Die zweite Familie ist definiert als:
$H_a(x, y, z) = (x^{q+1} + axy^q + yz^q, \ xy^q + z^{q+1}, \ x^qz + y^{q+1} + ay^qz)$

Äquivalenz der Kriterien (Corollary 3.4): Es wird bewiesen, dass $H_a$ genau dann eine APN-Permutation ist, wenn $G_a$ eine ist. Das zugrundeliegende Polynom für $H_a$ ist nullstellenäquivalent zu dem von $G_a$ .
Folge: Derselbe Satz an Parametern $a$ liefert APN-Permutationen für beide Familien.

C. Nicht-Äquivalenz-Ergebnisse

Ein zentraler Beitrag ist der Nachweis, dass diese neuen Familien echte, von den bekannten Li–Kaleyski-Familien verschiedene Quellen darstellen.

Diagonale Äquivalenz (Theorem 4.2):
- $G_a$ ist genau dann diagonal äquivalent zur Li–Kaleyski-Repräsentante $G_1$ , wenn $a^{q^2+q+1} = 1$ .
- Für $m > 4$ , $m \neq 6$ und $7 \nmid m$ impliziert das Fehlen dieser Bedingung (d.h. $a^{q^2+q+1} \neq 1$ ) die CCZ-Inäquivalenz.
- Im Fall $q=2$ und $7 \nmid m$ ist $\gcd(7, 2^m-1)=1$ , sodass $a^7=1$ nur für $a=1$ gilt. Somit sind alle guten Parameter $a \neq 1$ CCZ-inkquivalent zu den bekannten Familien.
Inäquivalenz zwischen $G_a$ und $H_b$ (Theorem 4.5):
- Für $m > 4$ , $m \neq 6$ und $7 \nmid m$ ist kein Element der Familie $G_a$ CCZ-äquivalent zu einem Element der Familie $H_b$ (für dasselbe $q$ ).
- Dies beweist, dass die beiden Familien zwei disjunkte, unendliche Quellen für APN-Permutationen darstellen.

4. Signifikanz und Bedeutung

Erweiterung des bekannten Spektrums: Das Paper liefert die ersten unendlichen Familien von APN-Permutationen in Dimension $3m$ (mit $m$ ungerade), die über die bekannten sporadischen Beispiele und die Li–Kaleyski-Familien hinausgehen.
Parametrisierung: Durch die Einführung des freien Parameters $a \in \mathbb{F}_{2^m}^*$ wird eine große Menge neuer Funktionen generiert. Die quantitative Schranke zeigt, dass diese Menge für große $m$ sehr groß ist.
Klassifikation und Struktur: Die Arbeit klärt die Beziehung zwischen Permutations- und APN-Eigenschaft auf (sie sind hier äquivalent) und liefert eine präzise algebraische Charakterisierung über Nullstellen von Polynomen.
Kryptographische Relevanz: Da CCZ-Äquivalenz der stärkste bekannte Äquivalenzbegriff für APN-Funktionen ist, die die APN-Eigenschaft erhalten, stellen diese neuen Familien echte, bisher unbekannte S-Box-Kandidaten dar, die in der Konstruktion von Blockchiffren verwendet werden könnten.
Methodischer Fortschritt: Die Reduktion des Problems auf univariate Polynomwurzeln und die Nutzung algebraischer Geometrie zur Zählung guter Parameter bieten einen neuen Ansatz für die Untersuchung multivariater Permutationspolynome.

5. Offene Probleme

Das Paper schließt mit einer Liste offener Fragen, darunter:

Explizite Konstruktion guter Parameter für den Fall $7 \mid m$ (wobei $a=1$ nicht funktioniert).
Untersuchung, ob die gefundenen Permutationen für $m=3$ auf unendliche Familien für größere $m$ erweitert werden können.
Gültigkeit der Ergebnisse für gerade Dimensionen $m$ .
Verallgemeinerung auf $n$ -variante Konstruktionen ( $n > 3$ ).

Zusammenfassend stellt dieses Paper einen bedeutenden Fortschritt im Verständnis und der Konstruktion von APN-Permutationen dar, indem es bekannte sporadische Beispiele in große, parametrisierte Familien überführt und deren strukturelle Eigenschaften sowie ihre Unterscheidbarkeit von bestehenden Familien rigoros beweist.