🔢 mathematics

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

Diese Arbeit präsentiert eine hybride computergestützte Suche, die Zufallsstichproben und Gröbner-Basis-Enumeration innerhalb eines spezifischen 40-dimensionalen Selbstäquivalenz-Unterraums kombiniert, um 566 quadratische APN-Funktionen in Dimension 8 zu entdecken, einschließlich drei zuvor unbekannter CCZ-Äquivalenzklassen, die von früheren erschöpfenden Datenbanken übersehen wurden.

Ursprüngliche Autoren: Oleksandr Kuznetsov

Veröffentlicht 2026-06-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Oleksandr Kuznetsov

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 versuchen, einen ganz bestimmten, unglaublich seltenen Typ von Lockpick (eine sogenannte APN-Funktion) in einem riesigen, dunklen Lagerhaus zu finden. Dieses Lagerhaus repräsentiert alle mathematischen Funktionen einer bestimmten Größe. Das Problem ist, dass dieses Lagerhaus so gewaltig ist (es enthält mehr Möglichkeiten als es Atome im Universum gibt), dass Sie wahrscheinlich niemals in Ihrem ganzen Leben einen einzigen Lockpick finden würden, wenn Sie einfach nur zufällig umherlaufen würden.

Dieses Paper beschreibt eine clevere neue Strategie, um diese seltenen Lockpicks zu finden, indem man eine „Taschenlampe“ und einen „Magneten“ benutzt, um einen spezifischen, kleineren Abschnitt des Lagerhauses zu durchsuchen, der zuvor als leer galt.

Hier ist die Aufschlüsselung ihrer Entdeckung unter Verwendung einfacher Analogien:

1. Das Problem: Die Nadel im kosmischen Heuhaufen

In der Welt der Kryptographie (der Wissenschaft der Geheimcodes) sind diese „Lockpicks“ spezielle mathematische Werkzeuge, die verwendet werden, um Daten so zu verschlüsseln, dass sie nicht geknackt werden können. Lange Zeit haben Mathematiker versucht, neue, bessere Lockpicks für eine bestimmte Datengröße (8 Bit) zu finden.

Der alte Weg: Frühere Forscher versuchten, diese zu finden, indem sie einen riesigen Baum aus Möglichkeiten aufbauten und Ast für Ast überprüften. Sie untersuchten einen spezifischen, organisierten Abschnitt des Lagerhauses (einen „Selbstäquivalenz-Unterraum“) und kamen zu dem Schluss: „Hier ist nichts.“ Sie hörten auf zu suchen.
Die Realität: Die Autoren dieses Papers sagen: „Moment mal. Dieser Abschnitt ist nicht leer. Ihr habt die Gegenstände nur übersehen, weil eure Methode des Baumkletterns zu starr war.“

2. Die neue Strategie: Die Taschenlampe und der Magnet

Die Autoren entwickelten einen zweistufigen Prozess, um diese verborgenen Lockpicks zu finden:

Schritt 1: Die Taschenlampe (Zufälliges Sampling in einer strukturierten Zone)
Anstatt das ganze Universum zu durchsuchen, konzentrierten sie sich auf einen spezifischen, organisierten 40-dimensionalen „Raum“ innerhalb des Lagerhauses. Sie erkannten, dass diese „Lockpicks“ in diesem speziellen Raum viel häufiger vorkommen als anderswo.
Sie verwendeten eine spezielle Karte (eine sogenannte RREF-Parametrisierung), um sich zufällig durch diesen Raum zu bewegen. Dabei fanden sie hunderte von „Zentrum“-Lockpicks, die genau dort lagen und nur darauf warteten, entdeckt zu werden.
Schritt 2: Der Magnet (Die Gröbner-Basis-Suche)
Dies ist der magische Trick. Sobald sie einen „Zentrum“-Lockpick gefunden hatten, hörten sie nicht einfach auf. Sie nutzten ein mächtiges mathematisches Werkzeug namens Gröbner-Basis (denken Sie an einen Super-Magneten), um die unmittelbare Nachbarschaft um dieses Zentrum herum abzusuchen.
Hier ist der überraschende Teil: Der Magnet fand nicht nur mehr Lockpicks im selben Raum. Er zog neue Lockpicks hervor, die in den benachbarten Räumen versteckt waren, außerhalb des organisierten Abschnitts, in dem sie begonnen hatten.
- Analogie: Stellen Sie sich vor, Sie finden eine seltene Münze in einer bestimmten Schublade. Sie benutzen einen Magneten, um die Schublade abzusuchen, und plötzlich zieht der Magnet drei andere seltene Münzen heraus, die am Boden der Schublade festklebten, obwohl diese Münzen technisch gesehen zu einer ganz anderen Schublade gehören.

3. Die Entdeckung: Neue Schatzklassen

Mit dieser Methode fanden das Team 566 neue Lockpicks. Sie sortierten sie in sechs Gruppen (Klassen):

Zwei Gruppen waren „bekannte“ Typen (wie die berühmten Gold-Funktionen). Diese fungierten als Gateways (Tore). Wenn die Autoren diese bekannten Typen als Ausgangspunkt verwendeten, zog der „Magnet“ die neuen, unbekannten Typen hervor.
Vier Gruppen waren völlig neu. Diese waren noch nie zuvor gesehen worden.
- Eine Gruppe (Klasse A) wurde direkt innerhalb des organisierten Raums gefunden.
- Drei Gruppen (Klassen B, C und D) wurden außerhalb des Raums gefunden, aber sie waren nur entdeckbar, weil der „Magnet“ an die bekannten „Gateway“-Lockpicks innerhalb des Raums angebracht war.

4. Der Beweis: Warum es wichtig ist

Die Autoren haben nicht nur geraten, dass dies neu sei. Sie nutzten ein „Fingerabdruck“-System (genannt Ortho-Derivat-Invariante), um ihre Funde mit den größten Datenbanken der Welt abzugleichen, die Millionen bekannter Lockpicks enthalten.

Ergebnis: Ihre vier neuen Gruppen stimmten mit keinem der Millionen existierenden Einträge überein. Sie sind genuin neu.
Der Mythos des „leeren Raums“: Sie bewiesen, dass die vorangegangenen Forscher sich geirrt hatten, dass der Raum leer sei. Der Raum war nicht leer; die vorherige Suchmethode konnte die Gegenstände nur deshalb nicht sehen, weil sie sie einzeln betrachtete, während diese neue Methode das gesamte Umfeld gleichzeitig betrachtet.

5. Die große Lektion: Das „Gateway“-Phänomen

Die wichtigste Erkenntnis ist nicht nur die Entdeckung der neuen Lockpicks, sondern auch, wie sie gefunden wurden.
Die Autoren entdeckten, dass man nicht einfach irgendeinen zufälligen Lockpick wählen und hoffen kann, in der Nähe neue zu finden. Man muss mit einem sehr spezifischen, strukturierten Typ beginnen (den „Gold“-Funktionen innerhalb des organisierten Raums).

Die Analie: Wenn man versucht, einen Magneten an einem zufälligen Stück Schrott im Lagerhaus zu benutzen, passiert nichts. Aber wenn man den Magneten an einem spezifischen „Gateway“-Objekt benutzt, offenbart er eine ganze verborgene Welt neuer Objekte, die zuvor unsichtbar waren.

Zusammenfassung

Dieses Paper handelt davon, verborgene mathematische Schätze an einem Ort zu finden, von dem alle glaubten, er sei leer. Indem sie eine intelligentere Karte nutzten, um einen Ausgangspunkt zu finden, und einen mächtigen mathematischen „Magneten“ verwendeten, um die Umgebung abzusuchen, fanden die Autoren 566 neue kryptographische Werkzeuge, einschließlich vier völlig neuer Familien, die noch nie zuvor gesehen wurden. Sie bewiesen, dass man, um das Neue zu finden, manchmal auf den Schultern des Bekannten stehen muss – aber man braucht die richtigen Werkzeuge, um zu sehen, was direkt hinter der Grenze lauert.

Technisches Resümee: Quadratische APN-Funktionen in Dimension 8 via Gröbner-Basis-Suche in einem Selbstäquivalenz-Unterraum

Problemstellung
Die Klassifizierung von Almost Perfect Nonlinear (APN) Funktionen über $\mathbb{F}_{2^n}$ bis hin zur CCZ-Äquivalenz ist ein zentrales Problem in der Kryptographie, insbesondere für $n=8$ . Während die Klassifizierung für $n \leq 6$ vollständig ist, bleibt sie für $n=8$ unvollständig. Der Suchraum für quadratische APN-Funktionen ist gewaltig ( $2^{224}$ mögliche Koeffizientenvektoren), was eine globale Zufallssuche aufgrund einer geschätzten APN-Dichte von $\approx 2^{-n}$ unmöglich macht. Vorherige systematische Bemühungen, wie die rekursive Baumsuche von Beierle, Brinkmann und Leander (BBL2021), untersuchten strukturierte algebraische Unterräume, die durch Selbstäquivalenz-Beschränkungen definiert sind. Speziell berichtete BBL2021, dass innerhalb des 40-dimensionalen Selbstäquivalenz-Unterraums $V_A$ , der mit einem linearen Automorphismus $A$ der Ordnung 5 (Klassenindex 22) assoziiert ist, null APN-Funktionen gefunden wurden. Diese Arbeit untersucht, ob dieser Unterraum tatsächlich keine APN-Funktionen enthält oder ob die vorherige Suchmethode diese lediglich nicht lokalisieren konnte.

Methodik
Die Autoren schlagen eine zweiphasige computergestützte Pipeline vor, die Random Sampling mit algebraischer Enumeration kombiniert, um $V_A$ effektiver zu explorieren als die vorherige Baumsuche.

Phase 1: Random Sampling via RREF-Parametrisierung
Die Autoren konstruieren eine explizite parametrisierte reduzierte Zeilenstufenform (RREF) des 40-dimensionalen Unterraums $V_A = \{F : F \circ A = A \circ F\}$ . Dies reduziert den Suchraum von $2^{224}$ auf $2^{40}$ . Innerhalb dieses Unterraums liegt die empirische Dichte von APN-Funktionen bei etwa $10^{-4}$ (etwa 1 APN-Funktion pro 11.000 Zufallsstichproben), was ein gezieltes Sampling ermöglicht. Die Autoren führen Random Sampling durch, um „APN-Zentren“ (Funktionen in $V_A$ , die APN sind) zu identifizieren.
Phase 2: Gröbner-Basis-Schnittberechnungen (Slice Computation)
Für jedes in Phase 1 gefundene APN-Zentrum definieren die Autoren eine 24-dimensionale affine Hyperebene (einen „NL=4 Slice“), die durch dieses Zentrum verläuft. Dies wird erreicht, indem 200 der 224 Koeffizienten der Algebraischen Normalform (ANF) (speziell jene, die zu Paaren mit Indizes $p \leq 4$ gehören) auf die Werte des Zentrums fixiert werden, wodurch 24 Koeffizienten als Unbekannte verbleiben.
Die APN-Bedingung für die 255 Nicht-Null-Differenzen wird als System von Polynomgleichungen über dem Boole’schen Ring kodiert. Die Autoren verwenden das Computer-Algebra-System Magma, um eine Gröbner-Basis für dieses System zu berechnen.

Falls das System unlösbar ist, enthält der Slice keine weiteren APN-Funktionen.
Falls das System Lösungen besitzt, findet die Gröbner-Basis-Enumeration alle APN-Funktionen innerhalb dieser spezifischen 24-dimensionalen Hyperebene.
Entscheidend ist, dass die durch den Gröbner-Basis-Schritt gefundenen Lösungen zwar durch das Zentrum in $V_A$ definiert sind, aber nicht zwingend in $V_A$ liegen müssen; sie können außerhalb des Selbstäquivalenz-Unterraums liegen.

Klassifizierung und Verifizierung
Die gefundenen Funktionen werden mittels des Ortho-Derivat-Invarianten $\sigma(F)$ klassifiziert, welcher nach Yoshiaras Theorem und den Ergebnissen von Canteaut et al. als vollständiger CCZ-Invariant für quadratische APN-Funktionen bewiesen ist. Die Autoren führen Streaming-Vergleiche dieser Signaturen gegen drei große Datenbanken durch: die BBL2021 Pre-2020-Kompilierung, die Beierle et al. 2025-Datenbank (die $\approx 3,8$ Millionen Funktionen enthält) und die klassischen Gold-Funktionen.

Wichtigste Ergebnisse
Die Autoren führten die Pipeline auf 428 distinkten 24-dimensionalen Slices aus (0,65 % der gesamten $2^{16}$ möglichen Slices in $V_A$ ) aus.

Entdeckung neuer Klassen: Die Suche ergab 566 einzigartige quadratische APN-Funktionen, die zu sechs CCZ-Äquivalenzklassen fallen.
- Vier neue Klassen (A, B, C, D): Diese 500 Funktionen (362 in Klasse A, 72 in B, 36 in C, 30 in D) sind weder in der Beierle 2025-Datenbank noch in der BBL2021 Pre-2020-Datenbank noch in den klassischen Gold-Familien enthalten.
- Zwei bekannte Klassen (E, F): Diese entsprechen den Gold-Funktionen $x^3$ und $x^9$ (und deren Frobenius-Orbits) und dienen als Kontrollinstanzen zur Validierung der Pipeline.
Strukturelle Erkenntnisse:
- Mitgliedschaft im Unterraum: Ein Mitgliedschaftstest ( $F \circ A = A \circ F$ ) zeigte, dass die Klassen A, E und F vollständig in $V_A$ liegen. Die Klassen B, C und D liegen jedoch vollständig außerhalb von $V_A$ .
- Das „Gateway“-Phänomen: Die 138 Funktionen der neuen externen Klassen (B, C, D) wurden ausschließlich in Slices gefunden, die auf Gold-Funktionen (Klassen E und F) zentriert waren, welche wiederum in $V_A$ liegen. Slices, die auf Funktionen der Klasse A zentriert waren, lieferten keine Nachbarn außerhalb von $V_A$ .
- Versagen alternativer Seeds: Vergleichende Experimente unter Verwendung von 532 APN-Funktionen aus der Beierle 2025-Datenbank (die außerhalb von $V_A$ liegen) als Slice-Zentren führten zu null gefundenen APN-Nachbarn. Dies deutet darauf hin, dass die „Gateway“-Fähigkeit, neue Klassen via Gröbner-Basis-Slicing zu entdecken, spezifisch für Funktionen innerhalb des Selbstäquivalenz-Unterraums ist und keine generische Eigenschaft aller APN-Funktionen darstellt.

Bedeutung und Ansprüche
Das Paper beansprucht mehrere signifikante Beiträge zur Klassifizierung von APN-Funktionen:

Korrektur früherer Ergebnisse: Die Autoren zeigen auf, dass der Selbstäquivalenz-Unterraum $V_A$ (Klassenindex 22), der zuvor von BBL2021 als frei von APN-Funktionen gemeldet wurde, tatsächlich mindestens vier quadratische APN-CCZ-Klassen enthält. Das Versagen der BBL2021 Baumsuche wird auf deren Branch-Pruning-Strategie zurückgeführt, die möglicherweise gültige Lösungen innerhalb dieses strukturierten Unterraums eliminiert hat, während der Gröbner-Basis-Ansatz eine vollständige Enumeration innerhalb jedes Slices ermöglicht.
Entdeckung neuer Funktionen: Die Arbeit liefert den rigorosen Beweis (via Ortho-Derivat-Invariant), dass vier neue quadratische APN-CCZ-Klassen für $n=8$ existieren, die von den $\approx 3,8$ Millionen Funktionen der größten bekannten Datenbank verschieden sind.
Methodische Innovation: Die Arbeit führt einen „GB-Navigation“-Mechanismus ein. Sie postuliert, dass man – während eine globale Suche unmöglich ist – strukturierte Unterräume mit höherer APN-Dichte nutzen kann, um „Seed“-Funktionen zu finden. Der Schritt der Gröbner-Basis fungiert dann als lokaler Enumerator, der in der Lage ist, aus dem Unterraum herauszutreten, um neue Klassen zu finden. Die Autoren betonen, dass dieser Mechanismus nicht generisch ist; er beruht auf der spezifischen algebraischen Struktur des Selbstäquivalenz-Unterraums, wie das Scheitern von Nicht-Unterraum-Funktionen als produktive Seeds zeigt.
Vollständigkeit des Ortho-Derivats: Die Arbeit untermauert die Nützlichkeit der Ortho-Derivat-Signatur als exakter CCZ-Invariant für quadratische Funktionen, was eine rigorose Klassifizierung ohne erschöpfende Paarvergleiche ermöglicht.

Die Autoren kommen zu dem Schluss, dass ihr Ansatz ein systematisches Programm bietet, um die Klassifizierung quadratischer APN-Funktionen zu erweitern, indem andere BBL2021-Klassenindizes exploriert und die Gröbner-Basis-Slicing-Technik zur Navigation in der APN-Landschaft genutzt wird.