Triprojective almost perfect nonlinear permutations and functions

Stellen Sie sich vor, Sie sind ein Meister Schlosser, der versucht, den ultimativen Safe zu entwerfen. In der Welt der digitalen Sicherheit sind die „Schlösser" mathematische Funktionen, die Daten verschlüsseln, damit Hacker die ursprüngliche Nachricht nicht entschlüsseln können. Das Papier, nach dem Sie fragen, ist ein Bauplan für den Bau eines neuen, unglaublich starken Schloss-Typs.

Hier ist die Geschichte dessen, was die Autoren, Faruk Gölöglu und Lukas Kölsch, entdeckt haben, erklärt ohne schweres mathematisches Fachjargon.

Das Ziel: Der perfekte Verschlüssler

In der Kryptographie gibt es eine bestimmte Art von Schloss, die S-Box (Substitutionsbox) genannt wird. Stellen Sie sich eine S-Box als eine Maschine vor, die einen Satz von Eingaben (wie eine Kombination aus Zahlen) entgegennimmt und einen völlig anderen Satz von Ausgaben ausspuckt.

Die Gefahr geht von einer Methode namens „differentielle Kryptoanalyse" aus. Stellen Sie sich einen Dieb vor, der versucht, Ihren Safe zu knacken, indem er Muster bemerkt: „Wenn ich den Ziffernring einen Klick nach rechts drehe, ändert sich das Geräusch des Schlosses um einen bestimmten Betrag. Wenn ich ihn zwei Klicks drehe, ändert sich das Geräusch anders." Wenn das Schloss auf kleine Änderungen zu vorhersehbar reagiert, kann der Dieb rückwärts arbeiten, um den Schlüssel zu finden.

Um dies zu verhindern, suchen Mathematiker nach APN-Funktionen (Fast Perfekt Nichtlinear). Dies sind die „perfekten" Schlösser, bei denen eine winzige Änderung der Eingabe eine chaotische, unvorhersehbare Änderung der Ausgabe bewirkt. Das Ziel ist es, sicherzustellen, dass die Ausgabe wie zufälliges Rauschen aussieht, egal wie der Dieb die Eingabe manipuliert.

Die große Herausforderung: Das „Problem der geraden Dimension"

Lange Zeit wussten Mathematiker, wie man diese perfekten Schlösser für bestimmte Datengrößen baut (speziell, wenn die Datengröße eine ungerade Zahl ist). Aber für Datenblöcke mit gerader Größe (die in echten Computern sehr häufig vorkommen), war es eine massive Kopfschmerz-Quälerei, ein perfektes Schloss zu finden, das auch eine Permutation ist (was bedeutet, dass jede einzelne Eingabe auf einen eindeutigen Ausgang abgebildet wird, sodass nichts verloren geht). Es ist wie der Versuch, einen Schlüssel zu finden, der zu jedem Schloss in einer bestimmten Reihe von Häusern passt, man aber ständig feststellt, dass einige Schlüssel zwei Schlösser gleichzeitig öffnen oder einige Schlösser überhaupt keinen Schlüssel haben.

Die Autoren dieses Papiers sagen: „Wir haben einen Weg gefunden, diese perfekten, sich nicht wiederholenden Schlösser für eine riesige neue Familie von Datenblöcken mit gerader Größe zu bauen."

Der geheime Bestandteil: Die „Triprojektive" Architektur

Die Autoren sind nicht einfach auf eine zufällige Formel gestoßen. Sie bauten ihre Schlösser mit einem bestimmten architektonischen Stil, den sie „Triprojektiv" nennen.

Um dies zu verstehen, stellen Sie sich vor, Sie betrachten eine 3D-Skulptur.

• Standard-Schlösser: Normalerweise werden diese gebaut, indem man die Skulptur nur aus einem Winkel betrachtet (eine flache, 2D-Ansicht).
• Die neuen „Triprojektiven" Schlösser: Die Autoren bauten ihre Funktion, indem sie die Skulptur gleichzeitig aus drei verschiedenen Winkeln betrachteten, wobei sie eine spezielle Gruppe von Regeln verwendeten (bezogen auf eine mathematische Struktur namens $GL(3, 2^m)$).

Sie nennen dies eine „Triprojektive" Struktur, weil sie die Daten so behandeln, als ob sie in einem 3D-Raum existieren, in dem die Regeln der Geometrie leicht verzerrt sind. Indem sie die Daten auf diese Weise anordnen, stellen sie sicher, dass die „Verschlüsselung" auf eine Weise stattfindet, die unglaublich schwer vorherzusagen ist, unabhängig davon, wie man versucht, sie zu untersuchen.

Die magische Formel

Das Papier präsentiert ein spezifisches Rezept (eine Formel) für diese Schlösser. Es beinhaltet drei Variablen ($x, y, z$) und einige spezielle Zahlen ($a, b, c$).

Das Rezept hat eine „Sicherheitsprüfung". Bevor Sie das Schloss verwenden können, müssen Sie einen schnellen Test durchführen, um sicherzustellen, dass eine bestimmte Gleichung keine Lösungen hat.

• Wenn der Test besteht: Sie erhalten ein perfektes, unknackbareres Schloss (eine APN-Permutation).
• Wenn der Test fehlschlägt: Das Schloss ist immer noch sehr stark (hochgradig nichtlinear), aber es ist möglicherweise keine perfekte Permutation (einige Eingaben könnten auf denselben Ausgang abgebildet werden).

Die Autoren beweisen, dass diese Formel, wenn Sie Ihre Zahlen richtig wählen, für jede ungerade Dimension funktioniert, die durch drei teilbar ist. Dies ist eine massive Erweiterung dessen, was bisher bekannt war.

Warum dies wichtig ist (laut dem Papier)

1. Es vereint alte Entdeckungen: Die Autoren zeigen, dass mehrere andere komplizierte Formeln, die in den letzten Jahren von verschiedenen Mathematikern entdeckt wurden, tatsächlich nur spezielle, vereinfachte Versionen ihres neuen „Triprojektiven" Rezepts sind. Es ist wie die Erkenntnis, dass drei verschiedene Autotypen eigentlich nur unterschiedliche Lackierungen desselben Fahrgestells sind.
2. Es ist neu und einzigartig: Sie beweisen, dass ihre neue Familie von Schlössern grundlegend anders ist als die „Gold"-Schlösser (eine berühmte Familie von APN-Funktionen, die vor Jahrzehnten entdeckt wurde). Sie geben alten Schlüsseln nicht nur neue Etiketten; sie schmieden völlig neue.
3. Der Beweis ist „sauber": Frühere Versuche, zu beweisen, dass diese Schlösser funktionieren, erforderten massive Computersimulationen und Seiten voller komplexer Algebra. Die Autoren verwendeten einen cleveren, rein logischen Ansatz (unter Verwendung von „verzerrten Polynomen" und Eigenschaften endlicher Körper), um ihre Ergebnisse zu beweisen, ohne einen Supercomputer zu benötigen.

Das Fazit

Dieses Papier ist ein mathematischer Durchbruch im Design digitaler Sicherheitsschlösser. Die Autoren haben eine neue, vielseitige „Triprojektive" Methode entdeckt, um Fast Perfekt Nichtlineare Permutationen zu konstruieren.

Einfach ausgedrückt: Sie haben einen neuen, zuverlässigen Weg gefunden, die stärkstmöglichen Datenverschlüssler für eine breite Palette von Computerdatengrößen zu bauen und ein Problem zu lösen, das Experten jahrelang vor Rätsel gestellt hatte. Sie haben nicht nur einen neuen Schlüssel gefunden; sie haben eine ganze Fabrik zur Herstellung solcher Schlüssel entdeckt und bewiesen, dass diese neuen Schlösser sich von allen anderen unterscheiden, die wir bisher gesehen haben.