🔢 mathematics

On the Walsh spectra of quadratic APN functions

Diese Arbeit stellt neuartige Verbindungen zwischen den Walsh-Spektren quadratischer APN-Funktionen und Vektorraumpartitionen oder Blockierungsmengen in projektiven Räumen her, was die Herleitung starker spektraler Bedingungen ermöglicht, wie etwa einer Begrenzung hochamplitudiger Komponentenfunktionen, einer nichttrivialen oberen Schranke für gebogene Komponenten und Kriterien für die CCZ-Äquivalenz zu Permutationen.

Ursprüngliche Autoren: Sophie Hannah Bénéteau, Nicolas Goluboff, Lukas Kölsch, Divyesh Vaghasiya

Veröffentlicht 2026-05-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC0 1.0

Ursprüngliche Autoren: Sophie Hannah Bénéteau, Nicolas Goluboff, Lukas Kölsch, Divyesh Vaghasiya

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 entwerfen einen hochsicheren Tresor (einen Blockchiffre), um digitale Geheimnisse zu schützen. Um diesen Tresor unknackbar zu machen, müssen Sie eine spezielle Art von „Schloss" darin installieren. In der Welt der Kryptographie sind diese Schlösser mathematische Funktionen, die als APN-Funktionen bezeichnet werden.

Denken Sie an eine APN-Funktion als einen Hauptschlüssel, der Daten so perfekt verschlüsselt, dass selbst ein Dieb, der versucht, durch den Vergleich zweier leicht unterschiedlicher Schlüssel (ein „differenzieller Angriff") herauszufinden, wie das Schloss funktioniert, absolut keine nützlichen Informationen erhält. Diese Funktionen sind der Goldstandard für Sicherheit.

Allerdings sind nicht alle Schlösser gleich geschaffen. Einige sind „quadratisch" (mathematisch einfacher und leichter zu untersuchen), und die Forscher in diesem Papier versuchen, den internen „Fingerabdruck" dieser spezifischen Schlösser zu verstehen.

Hier ist das, was das Papier entdeckt hat, erklärt durch alltägliche Analogien:

1. Der Fingerabdruck: Das Walsh-Spektrum

Jedes Schloss hat einen einzigartigen „Fingerabdruck", der Walsh-Spektrum genannt wird. Man kann sich dies als ein Zeugnis vorstellen, das misst, wie „linear" oder vorhersagbar das Schloss ist.

Das Ziel: Wir wollen, dass das Schloss so unvorhersagbar wie möglich ist.
Die Metrik: Das Papier betrachtet die „Amplitude" verschiedener Teile des Schlosses. Stellen Sie sich vor, das Schloss besteht aus vielen kleineren Zahnrädern (Komponentenfunktionen). Einige Zahnräder drehen sich glatt (niedrige Amplitude), während andere ruckeln und laut sind (hohe Amplitude). Die Forscher wollen wissen: Wie viele laute Zahnräder kann ein sicheres Schloss haben, bevor es schwach wird?

2. Die erste Entdeckung: Die Analogie der „Raumaufteilung"

Die Autoren fanden eine überraschende Verbindung zwischen diesen mathematischen Schlössern und dem Aufteilen eines Raumes.

Stellen Sie sich den Raum vor, in dem das Schloss operiert, als einen riesigen Raum, der mit Punkten (Vektoren) gefüllt ist. Die Forscher bewiesen, dass die „lauten Zahnräder" (die Teile des Schlosses mit hoher Amplitude) den Raum zwingen, in spezifische, sich nicht überlappende Unter-Räume (Vektorräume) aufgeteilt zu werden.

Die Regel: Jeder Punkt im Raum muss genau einem Unter-Raum angehören, und keine zwei Unter-Räume dürfen außer dem Mittelpunkt einen gemeinsamen Raum teilen.
Die Einsicht: Dies ist keine zufällige Aufteilung. Die Größe dieser Unter-Räume hängt direkt damit zusammen, wie „laut" (hohe Amplitude) die Zahnräder sind. Wenn man weiß, wie der Raum aufgeteilt ist, kennt man den Fingerabdruck des Schlosses.

Was dies bedeutet: Sie bewiesen, dass ein sicheres Schloss höchstens eines extrem „lautes" Zahnrad haben kann (Amplitude größer als ein bestimmter Schwellenwert). Wenn es zwei hätte, könnte der Raum nicht korrekt aufgeteilt werden, und das Schloss würde den Sicherheitstest nicht bestehen.

3. Die zweite Entdeckung: Die Analogie des „Staus"

Das Papier untersuchte auch die „leisen Zahnräder" (Bent-Komponenten) im Vergleich zu den „lauten Zahnrädern". Sie entdeckten, dass die lauten Zahnräder eine spezielle Art von Stau (eine „Blocking-Set") in einer geometrischen Landschaft bilden.

Die Analogie: Stellen Sie sich ein Stadtgitter vor, in dem bestimmte Kreuzungen blockiert sind. Eine „Blocking-Set" ist eine Sammlung blockierter Kreuzungen, sodass jede mögliche gerade Straße, die man zu befahren versucht, mindestens eine blockierte Kreuzung trifft.
Die Entdeckung: Die Forscher fanden heraus, dass für diese quadratischen Schlösser die „lauten Zahnräder" einen Stau erzeugen, der sehr spezifisch ist. Es ist nicht irgendein Stau; es ist ein Stau, bei dem die Anzahl der blockierten Kreuzungen auf jeder Straße immer eine ungerade Zahl ist.
Das Ergebnis: Diese „Regel der ungeraden Zahl" ermöglicht es ihnen, eine strikte Obergrenze dafür festzulegen, wie viele leise Zahnräder (Bent-Komponenten) ein Schloss haben kann. Es ist das erste Mal, dass eine allgemeine „Obergrenze" für diese Anzahl bei diesen Arten von Schlössern festgelegt wurde.

4. Alles zusammenfügen: Der „Bauplan"-Check

Durch die Kombination der Regeln „Raumaufteilung" und „Stau" erstellten die Autoren eine leistungsstarke Checkliste.

Sie nahmen Schlösser bestimmter Größen (Dimensionen 6, 8 und 10) und listeten jeden möglichen „Bauplan" (Amplitudenverteilung) auf, der theoretisch existieren könnte.
Dann wandten sie ihre neuen Regeln an, um unmögliche Baupläne zu streichen.
Beispiel: Für ein Schloss der Größe 8 gab es viele theoretische Möglichkeiten, die Zahnräder anzuordnen. Ihre Mathematik zeigte, dass viele dieser Anordnungen unmöglich sind, weil sie die Regeln der „Raumaufteilung" oder des „Staus" verletzen würden. Dies schränkte die Liste der möglichen sicheren Schlösser erheblich ein.

5. Das „Permutations"-Rätsel

Schließlich geht das Papier auf ein berühmtes ungelöstes Rätsel ein: Können diese Schlösser so umgeordnet werden, dass sie eine perfekte „Permutation" werden (eine Eins-zu-eins-Zuordnung, bei der jede Eingabe eine eindeutige Ausgabe hat, wie ein perfektes Mischen eines Kartendecks)?

Die Autoren fanden heraus, dass, wenn ein Schloss CCZ-äquivalent (eine bestimmte Art mathematischer Ähnlichkeit) zu einem perfekten Mischen ist, es nicht „wenige" laute Zahnräder haben kann. Es muss eine spezifische, große Anzahl davon haben. Dies gibt Kryptographen eine neue Möglichkeit zu testen, ob ein Schloss jemals ein perfektes Mischen sein kann.

Zusammenfassung der „Offenen Probleme"

Das Papier endet damit, zuzugeben, dass sie, obwohl sie einen besseren Zaun um die möglichen Schlösser gebaut haben, noch nicht alle Schlösser gefunden haben.

Sie haben eine Liste theoretischer Baupläne für Schlösser der Größe 8, aber sie haben keine physischen Beispiele für alle von ihnen gefunden.
Sie fragen die mathematische Gemeinschaft: „Können Sie ein Schloss bauen, das zu diesen spezifischen, seltenen Bauplänen passt, die wir gefunden haben?"

Kurz gesagt: Dieses Papier hat kein neues Schloss erfunden, sondern einen viel besseren Bauplan-Scanner gebaut. Es verwendet Geometrie (Raumaufteilungen und Staus), um Ihnen sofort zu sagen, welche mathematischen Entwürfe für sichere Schlösser unmöglich sind, und schränkt die Suche nach dem perfekten, unknackbaren digitalen Tresor ein.

Technische Zusammenfassung: Über die Walsh-Spektren quadratischer APN-Funktionen

Problemstellung
Fast Perfekt Nichtlineare (APN) Funktionen sind kritische Komponenten in symmetrischen Kryptosystemen und bieten optimalen Widerstand gegen differentielle Angriffe. Eine fundamentale Eigenschaft dieser Funktionen ist ihre Linearität, die durch ihr Walsh-Spektrum bestimmt wird. Während die Amplitudenverteilung (und somit das Walsh-Spektrum) quadratischer APN-Funktionen für ungerade Dimensionen $n$ vollständig charakterisiert ist, bleibt der Fall für gerade $n$ weitgehend offen. Die einzige bekannte allgemeine Einschränkung für gerade $n$ leitet sich aus dem vierten Moment der Walsh-Transformation ab. Dieser Beitrag schließt die Lücke im Verständnis der möglichen Walsh-Spektren quadratischer APN-Funktionen $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ , wobei $n$ gerade ist, mit dem spezifischen Ziel, stärkere Bedingungen für ihre Amplitudenverteilungen herzuleiten.

Methodik
Die Autoren stellen zwei neuartige geometrische Verbindungen zwischen quadratischen APN-Funktionen und der endlichen Geometrie her:

Vektorraum-Partitionen: Der Beitrag zeigt, dass die Amplitudenverteilung einer quadratischen APN-Funktion eindeutig einer Vektorraum-Partition des umgebenden Raums $\mathbb{F}_2^n$ entspricht. Konkret sind die nicht-trivialen, nicht-bögen Komponentenfunktionen von $F$ mit Unterräumen in einer Partition assoziiert, wobei die Dimension jedes Unterraums direkt mit der Amplitude der entsprechenden Komponentenfunktion verknüpft ist.
Blocking Sets (Blockierende Mengen): Die Menge der nicht-trivialen, nicht-bögen Komponenten, bezeichnet als $N_F$ , bildet einen spezifischen Typ von Blocking Set im projektiven Raum $PG(n-1, 2)$. Entscheidend beweisen die Autoren, dass der Schnitt von $N_F$ mit jedem Unterraum der Dimension $n/2$ eine ungerade Anzahl von Punkten enthalten muss.

Indem die Autoren auf etablierte Theoreme über Vektorraum-Partitionen und Blocking Sets zurückgreifen (insbesondere Ergebnisse bezüglich „Enden" von Partitionen und minimaler Blocking Sets), übersetzen sie diese geometrischen Einschränkungen in algebraische Schranken für die Amplitudenverteilungen quadratischer APN-Funktionen.

Hauptbeiträge und Ergebnisse

Verbindung zu Vektorraum-Partitionen (Abschnitt II):
- Satz II.4 stellt fest, dass eine Komponentenfunktion $F_b$ mit der Amplitude $2^{(n+k)/2}$ einem Unterraum der Dimension $k$ in einer Vektorraum-Partition von $\mathbb{F}_2^n$ entspricht.
- Diese Verbindung ermöglicht die Anwendung von Packungsbedingungen und Dimensionsgrenzen aus der Partitionstheorie.
- Satz II.10: Eine quadratische APN-Funktion kann höchstens eine Komponentenfunktion mit einer Amplitude größer als $2^{3n/4}$ besitzen. Falls eine solche Komponente existiert, müssen alle anderen eine Amplitude von höchstens $2^{(2n-l)/2}$ haben, wobei $l$ der Exponent der maximalen Amplitude ist.
- Propositionen II.14–II.16: Neue untere Schranken für die Anzahl der nicht-bögen Komponenten ( $|N_F|$ ) werden basierend auf der Linearität und dem Vorhandensein spezifischer Amplituden hergeleitet.
Verbindung zu Blocking Sets (Abschnitt III):
- Korollar III.3: Die Menge $N_F$ ist ein Blocking Set in $PG(n-1, 2)$ bezüglich $(n/2)$ -Räumen, mit der zusätzlichen Eigenschaft, dass jeder solche Raum $N_F$ in einer ungeraden Anzahl von Punkten schneidet.
- Satz III.9: Dies ist die erste nicht-triviale, allgemeine obere Schranke für die Anzahl der bögen Komponentenfunktionen einer quadratischen APN-Funktion. Konkret gilt für $n \ge 6$ , dass die Anzahl der nicht-bögen Komponenten $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ erfüllt. Gleichheit ist nur für $n=8$ möglich. Folglich beträgt die Anzahl der bögen Komponenten höchstens $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$ .
Synthese und Dimensionsanalyse (Abschnitt IV):
- Durch die Kombination der Einschränkungen aus Partitionen und Blocking Sets eliminieren die Autoren mehrere theoretisch mögliche Amplitudenverteilungen.
- Satz IV.1: Vektorraum-Partitionen vom Typ $[(n/2)^{2^{n/2+1}}]$ (ein $(n/2)$ -Spread) entsprechen keiner quadratischen APN-Funktion.
- Satz IV.5: Für $n=8** schränkt der Beitrag die möglichen Amplitudenverteilungen auf eine spezifische Liste ein (unter Ausschluss der trivialen Partition und des 4-Spreads) und reduziert die Anzahl potenzieller erweiterter Walsh-Spektren auf höchstens 18 verschiedene Typen.
- Proposition IV.4: Der Beitrag vergleicht die Stärke der hergeleiteten unteren Schranken für $|N_F|$ über verschiedene Parameterbereiche hinweg und identifiziert, welche Schranke abhängig von der Linearität der Funktion dominant ist.
Äquivalenz und Permutationen (Abschnitt V):
- Der Beitrag analysiert, wie sich diese Strukturen unter EA-Äquivalenz und CCZ-Äquivalenz verhalten.
- Korollar V.6: Wenn eine quadratische APN-Funktion CCZ-äquivalent zu einer Permutation ist, kann sie nicht wenige nicht-bögen Komponenten besitzen; spezifisch gilt $|N_F| \ge 3(2^{n/2}-1)$ , und $N_F$ muss ein 3-faches Blocking Set sein.

Bedeutung und Behauptungen
Der Beitrag beansprucht, die ersten allgemeinen Bedingungen für die Walsh-Spektren quadratischer APN-Funktionen jenseits der bekannten vierten-Moment-Schranke zu liefern. Indem die Autoren die algebraischen Eigenschaften dieser Funktionen mit den kombinatorischen Strukturen von Vektorraum-Partitionen und Blocking Sets verknüpfen, leiten sie starke Einschränkungen für die möglichen Amplitudenverteilungen her.

Die Autoren stellen explizit fest, dass ihre Ergebnisse:

beweisen, dass eine quadratische APN-Funktion höchstens eine Komponente mit einer Amplitude größer als $2^{3n/4}$ besitzen kann;
die erste nicht-triviale obere Schranke für die Anzahl der bögen Komponenten liefern;
Bedingungen bieten, um zu bestimmen, ob eine Funktion basierend auf ihrer Anzahl böger Komponenten CCZ-äquivalent zu einer Permutation ist;
systematisch alle möglichen Amplitudenverteilungen für kleine gerade Dimensionen (speziell $n=6, 8, 10$ ) auflisten und hervorheben, welche realisiert sind und welche offene Probleme darstellen.

Der Beitrag schließt mit einer Auflistung offener Probleme, einschließlich der Existenz von APN-Funktionen mit spezifischen Amplitudenverteilungen in der Dimension 8 und der Suche nach unendlichen Familien quadratischer APN-Funktionen mit nicht-klassischen Walsh-Spektren. Die Autoren bewahren einen bescheidenen Ton und stellen fest, dass, obwohl sie viele Möglichkeiten ausgeschlossen haben, die vollständige Klassifizierung der Walsh-Spektren quadratischer APN-Funktionen weiterhin eine offene Herausforderung bleibt.