🔢 Mathematik

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

Dieses Paper führt die D-Klasse von Permutationen über $\mathbb{F}_{2^{n+1}}$ ein, um vollständige Permutationen mittels lokaler Konjugationen zu charakterisieren und zu konstruieren, deren algebraische Eigenschaften, kryptographische Schrankken und CCZ-Inäquivalenz festzustellen, während gleichzeitig Algorithmen präsentiert werden, die erfolgreich neue $\delta=4$ vollständige Permutationen enumerieren.

Ursprüngliche Autoren: Li Shuai

Veröffentlicht 2026-10-16

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Li Shuai

Originalarbeit lizenziert unter CC BY 4.0 (https://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

In der verborgenen Architektur moderner digitaler Sicherheit existiert eine Klasse mathematischer Objekte, die als vollständige Permutationen bekannt sind. Dies sind nicht bloß zufällige Vertauschungen von Zahlen; es handelt sich um hochstrukturierte Umordnungen, bei denen sowohl der Akt, ein Element an eine neue Position zu bewegen, als auch der Akt, es an eine Position zu bewegen, die die Summe der alten und neuen Position ist, zu einer perfekten, nicht überlappenden Ordnung führen. Diese duale Anforderung ist entscheidend für den Entwurf von Substitutionsboxen, oder S-Boxen, welche die primären Bestandteile in Verschlüsselungssystemen sind, die Daten verschleiern, um deren Bedeutung zu verbergen. Wenn diese Komponenten zu vorhersehbar sind, kann die Verschlüsselung gebrochen werden; wenn sie zu chaotisch sind, werden sie ineffizient. Die Herausforderung für Kryptographen bestand lange darin, den idealen Mittelpunkt zu finden: Permutationen, die komplex genug sind, um anspruchsvollen Angriffen zu widerstehen, aber dennoch strukturiert genug, um schnell implementiert werden zu können.

Eine aktuelle Studie von Li Shuai von der Ningxia Universität widmet sich dieser Herausforderung, indem sie eine spezifische Familie dieser Permutationen durch die Linse geometrischer Symmetrie untersucht. Die Forschung konzentriert sich auf eine Eigenschaft namens „lokale Krümmung“ (local crookedness), die beschreibt, wie sich eine Permutation verhält, wenn ihr Input um einen spezifischen Betrag verschoben wird. Der Autor führt eine neue Kategorie dieser Funktionen ein, die durch ein spezifisches Muster in der Art und Weise definiert ist, wie sich ihre Ausgaben verändern. Indem er diese Funktionen als Elemente einer größeren Gruppe behandelt, die durch Verschieben, Rotieren oder Vertauschen spezifischer Teile der Daten transformiert werden kann, kartiert die Studie eine Landschaft der Möglichkeiten. Das Ziel war es zu sehen, ob eine Bewegung innerhalb dieser Landschaft neue, überlegene Permutationen generieren kann, die einen besseren Schutz gegen differenzielle Kryptanalyse bieten – eine Methode, bei der Angreifer untersuchen, wie kleine Änderungen im Input die Ausgabe beeinflussen, um den geheimen Schlüssel abzuleiten.

Der Kern der Arbeit umfasst eine Konstruktionskette, die mit einer bekannten, gut strukturierten Permutation beginnt und eine Reihe präziser algebraischer Operationen anwendet, um neue zu erschaffen. Der Autor definiert eine spezifische Menge von Regeln, oder eine „D-Klasse“, die diese Permutationen befolgen müssen, um gültig zu bleiben. Innerhalb dieser Menge beweist der Forscher, dass die Sammlung von „gehobenen“ (lifted) Permutationen – jenen, die aus einem kleineren Raum in einen größeren Raum erweitert wurden – eine einzigartige Rigidität besitzt. Wenn man versucht, eine einzelne Permutation mit nur einer Art von Operation zu verändern, etwa einer einfachen Verschiebung oder einer linearen Rotation, scheitert das Ergebnis meist daran, eine gültige vollständige Permutation zu bleiben. Die Studie zeigt jedoch, dass die Kombination zweier verschiedener Operationen in einer spezifischen Sequenz diese Rigidität aufbricht. Diese Kombination ermöglicht es dem Forscher, sich in dem Raum der Möglichkeiten zu bewegen und von einer gültigen Permutation zur nächsten überzugehen, ohne die essenziellen Eigenschaften, die für die Sicherheit erforderlich sind, zu verlieren.

Um diesen theoretischen Rahmen praktisch nutzbar zu machen, entwickelt das Paper zwei unterschiedliche Algorithmen. Der erste ist eine Backtracking-Suche, die eine vollständige Permutation von Grund auf aufbaut und dabei in jedem Schritt sicherstellt, dass die dualen Ordnungsanforderungen erfüllt sind. Der zweite ist eine gierige lokale Suche (greedy local search), die mit einer bestehenden Permutation beginnt und versucht, diese durch Anwendung der zuvor beschriebenen kombinierten Operationen zu verbessern. Dieser zweite Algorithmus agiert wie ein Bergsteiger, der einen höheren Gipfel sucht: Er testet verschiedene kleine Modifikationen, akzeptiert eine Änderung jedoch nur dann, wenn sie die kryptographische Qualität der Permutation strikt verbessert. Die Qualität wird durch zwei Hauptindikatoren gemessen: die differentielle Uniformität, welche die Worst-Case-Häufigkeit von Output-Mustern zählt, und die Nichtlinearität, welche misst, wie weit die Funktion von einer einfachen linearen Gleichung entfernt ist. Eine niedrigere differentielle Uniformität und eine höhere Nichtlinearität sind im Allgemeinen besser für die Sicherheit.

Die Forscher testeten diese Methoden in einem spezifischen mathematischen Raum der Größe 32, was einem 5-Bit-System entspricht. Ausgehend von einer einfachen, linearen Permutation, die als schwach bekannt war, wurde der Algorithmus der gierigen Suche einhundert Mal ausgeführt. Die Experimente lieferten mehrere Permutationen mit einer differentiellen Uniformität von 4, was eine signifikante Verbesserung gegenüber dem Ausgangswert von 32 darstellt. Die Studie begann auch mit einhundert zufällig generierten Permutationen und wandte denselben Suchprozess an. Auch hier fand der Algorithmus konsistent Permutationen mit einer differentiellen Uniformität von 4. Die Ergebnisse waren nicht nur das Finden besserer Zahlen; die neuen Permutationen besaßen distinkte „Spektren“, also Muster von Output-Häufigkeiten, die sich voneinander und vom Ausgangspunkt unterschieden. Dies beweist, dass die Methode nicht bloß Variationen desselben Objekts produziert, sondern tatsächlich neue, distinkte Klassen sicherer Permutationen entdeckt.

Eines der bemerkenswertesten Ergebnisse betrifft die Beziehung zwischen diesen neuen Permutationen und einer berühmten Klasse von Funktionen, die als APN-Funktionen (Almost Perfect Nonlinear) bekannt sind. Historisch gesehen beruhten viele Konstruktionen sicherer Permutationen darauf, mit diesen APN-Funktionen zu beginnen. Die Studie stellte jedoch fest, dass die durch diese neue Methode der lokalen Konjugation generierten Permutationen, obwohl sie dieselbe exzellente differentielle Uniformität von 4 aufweisen, CCZ-inequivalent zu jenen sind, die aus den klassischen APN-Ansätzen abgeleitet wurden. Tatsächlich schnitt eine Referenz-Permutation, die auf einer bekannten APN-Funktion basiert, in diesem spezifischen Test schlechter ab, mit einer differentiellen Uniformität von 8. Dies deutet darauf hin, dass die neue Methode eine andere Region der mathematischen Landschaft erkundet und hochwertige Permutationen freilegt, die mit Standardkonstruktionstechniken bisher unzugänglich waren.

Das Paper schließt mit dem Vorschlag einer Vermutung (Conjecture) basierend auf den experimentellen Erkenntnissen: dass der gesamte Raum dieser gehobenen Permutationen zusammenhängend ist. Mit anderen Worten: Es scheint möglich zu sein, jede gültige Permutation in dieser Familie von jeder anderen auszugehen, indem man einem Pfad dieser spezifischen lokalen Modifikationen folgt. Obwohl diese Konnektivität mathematisch noch nicht bewiesen wurde, liefert die Tatsache, dass der Suchalgorithmus konsistent hochwertige Lösungen aus diversen Startpunkten fand, eine starke vorläufige Unterstützung für die Idee. Die Studie lässt zudem die Frage offen, ob diese spezifische Familie von Permutationen Funktionen enthält, die noch stärker sind als die gefundenen, und potenziell die theoretische Grenze der Sicherheit, bekannt als APN, erreichen könnten. Für den Moment bietet die Arbeit ein robustes neues Werkzeug zur Generierung sicherer Permutationen und zeigt auf, dass man durch das Verständnis der lokalen Symmetrien dieser mathematischen Objekte bessere Verteidigungen für die digitale Welt konstruieren kann.

Technisches Resümee: Konstruktion vollständiger Permutationen über der D-Klasse lokal gekrümmter Permutationen

Problemstellung

Die Arbeit befasst sich mit der Konstruktion von vollständigen Permutationen (Complete Permutations, CPs) über endlichen Körpern $\mathbb{F}_{2^n}$ . Eine Permutation $f$ ist eine CP, wenn sowohl $f$ als auch die Abbildung $x \mapsto f(x) + x$ Permutationen sind. CPs sind in der Kryptographie von entscheidender Bedeutung, insbesondere als Bausteine für S-Boxen im Lai–Massey-Framework und für die Generierung orthogonaler lateinischer Quadrate.

CPs sind über die Shuai–Li-Korrespondenz mit lokal gekrümmten Permutationen (Locally Crooked Permutations, LCPs) über $\mathbb{F}_{2^{n+1}}$ verknüpft. Frühere Methoden folgten einem „gekrümmte Funktion $\to$ LCP $\to$ CP“-Pfad, was jedoch restriktiv war, da es keine freie Bewegung oder Generierung neuer LCPs innerhalb der Klasse selbst ermöglichte. Die vorliegende Arbeit versucht, dies zu überwinden, indem sie direkt innerhalb der LCP-Klasse arbeitet, um durch interne Gruppenaktionen neue CPs zu generieren und somit den Suchraum für kryptographisch starke Permutationen zu erweitern.

Methodik

1. Die D-Klasse und Invarianz

Der Autor führt die D-Klasse ein, definiert als die Menge der Permutationen $f$ über $\mathbb{F}_{2^{n+1}}$ , deren Ableitung in einer festen Richtung $q_1 = 2^n$ ein Bild hat, das dem Komplement einer festen Hyperebene $H = \{x : x_n = 0\}$ entspricht.
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
wobei $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

Das Paper beweist, dass $D$ unter drei spezifischen Gruppenaktionen abgeschlossen ist:

Linke Translation: $t_a \circ f$ für beliebig $a \in \mathbb{F}_q$ .
Linke Multiplikation: $g \circ f$ für beliebig $g$ in der allgemeinen linearen Gruppe, welche $H$ erhält ( $GL_H$ ).
Rechte Multiplikation: $f \circ h$ für beliebig $h$ in der Zentralisator-Gruppe $C$ der Involution, welche $H$ und $K$ vertauscht.

Zusätzlich ist die Klasse unter spezifischen lokalen Translationen $t_{a,X}$ (Translationen, die auf eine Teilmenge $X$ beschränkt sind) abgeschlossen, sofern $X$ eine Vereinigung von Orbits einer spezifischen Diedergruppe ist, die durch die Translation und die konjugierte Involution erzeugt wird.

2. Rigidität und die Konstruktionskette

Der Autor definiert die hochgestellte CP-Teilklasse $D^\uparrow \subset D$ , bestehend aus Permutationen in $D$ , die auf dem Komplement $K$ die Identität bilden.

Rigidität: Das Paper beweist, dass $D^\uparrow$ unter jeder einzelnen Operation aus den oben genannten Abschlusseigenschaften „rigid“ ist (translation, lineare Multiplikation oder Zentralisator-Multiplikation). Eine einzelne Operation kann eine hochgestellte CP nicht in eine andere hochgestellte CP überführen, es sei denn, es handelt sich um die Identität.
Konstruktionskette: Um neue CPs zu generieren, konstruiert der Autor eine Kette, die einen Produkten von Operationen beinhaltet:
$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{lokale Translation}} LCP' \xrightarrow{\text{Zentralisator-Korrektur}} LCP'' \xrightarrow{\text{Restriktion}} \text{Neue } CP$
Diese Kette nutzt lokalisierte Zentralisator-Elemente ( $g_{a,X_1}$ und $g_{a,X_2}$ ), um den durch lokale Translationen eingeführten Defekt zu „reparieren“, wodurch sichergestellt wird, dass das Ergebnis in $D^\uparrow$ bleibt.

3. Lokale Konjugationen

Die Konstruktion liefert zwei spezifische lokale Konjugationen, $f_1$ und $f_2$ , definiert auf dem Basiskörper $\mathbb{F}_{2^n}$ :

$f_1$ : Eine Modifikation von $f$ auf einer Teilmenge $X_1 \subset H$ , wobei $X_1$ invariant unter einer Diedergruppe ist.
$f_2$ : Eine Modifikation, die die Inverse von $f$ auf einer Teilmenge $X_2$ involviert, wobei $X_2$ invariant unter einer zyklischen Gruppe ist.
Das Paper liefert notwendige und hinreichende Bedingungen dafür, dass diese modifizierten Abbildungen weiterhin CPs sind.

4. Algorithmen

Zwei Algorithmen werden zur Implementierung der Theorie vorgestellt:

Random Backtracking Search: Erzeugt zufällige CPs von Grund auf, indem Constraints auf $f(x)$ und $f(x)+x$ eingehalten werden.
Greedy Local Search: Wendet iterativ die lokalen Konjugationen ( $f_1, f_2$ ) auf eine Seed-CP an. Ein Schritt wird nur akzeptiert, wenn er eine Qualitätsfunktion basierend auf dem vollständigen Differenzspektrum (DDT) und dem Walsh-Spektrum strikt verbessert.

Hauptergebnisse

Theoretische Beiträge

Invarianzbeweis: Es wurde nachgewiesen, dass die D-Klasse unter den spezifizierten Gruppenaktionen und lokalen Translationen invariant ist.
Rigiditätssatz: Es wurde bewiesen, dass die hochgestellte CP-Teilklasse $D^\uparrow$ nicht durch Einzeloperationen generiert werden kann, was die kompositierte Konstruktionskette notwendig macht.
CCZ-Inäquivalenz-Kriterien: Es wurden Kriterien abgeleitet, um zu bestimmen, wann die neu konstruierten CPs CCZ-inequivalent zum Seed sind. Dies basiert auf der Prüfung, ob sich die DDT (Differential Distribution Table) oder die Multimenge der absoluten Walsh-Koeffizienten ändert.
Kryptographische Schranken: Schranken für die differentielle Uniformität ( $\delta$ ), Nichtlinearität ($nl$) und den algebraischen Grad ( $\deg$ ) unter lokalen Modifikationen wurden abgeleitet. Insbesondere ändert sich $\delta$ um höchstens $2m$ , wobei $m$ die Größe der modifizierten Teilmenge ist.

Experimentelle Befunde

Experimente wurden auf $H \cong \mathbb{F}_{2^5}$ (32 Elemente) durchgeführt:

Generierung von $\delta=4$ CPs: Ausgehend von einer linearen Seed ( $\delta=32$ ) und zufälligen Seeds konnte die Greedy-Suche erfolgreich mehrere vollständige Permutationen mit einer differentiellen Uniformität von $\delta=4$ finden.
Distinkte Spektren: Die generierten CPs wiesen im Vergleich zueinander und zu einer Referenz-Dillon-basierten CP (die $\delta=8$ hatte) distinkte differentielle Spektren auf.
CCZ-Inequivalenz: Die unterschiedlichen differentiellen Spektren bestätigen, dass die Konstruktion neue CCZ-Inequivalenzklassen produziert und nicht bloß affine Varianten des Seeds.
Evidenz für Konnektivität: Die wiederholte Konvergenz zu ähnlichen Indikatorverteilungen aus verschiedenen zufälligen Seeds liefert vorläufige Hinweise darauf, dass die Menge der hochgestellten CPs $D^\uparrow$ unter lokalen Konjugationsschritten möglicherweise zusammenhängend ist.

Bedeutung und Behauptungen

Das Paper behauptet, einen systematischen algebraischen Rahmen zur Generierung neuer vollständiger Permutationen bereitzustellen, indem die interne Struktur der LCP-Klasse ausgenutzt wird.

Über gekrümmte Funktionen hinaus: Im Gegensatz zu bisherigen Methoden, die von der Verwendung einer gekrümmten Funktion abhängen, erlaubt dieser Ansatz die Exploration des LCP-Raums selbst, um CPs zu finden.
Kryptographischer Nutzen: Die Methode produziert erfolgreich CPs mit niedriger differentieller Uniformität ( $\delta=4$ ), eine wünschenswerte Eigenschaft für S-Boxen, die über die Standard-Korrespondenz gekrümmter Funktionen schwerer zu konstruieren waren.
Strukturelle Einsicht: Die Identifizierung der „Rigidität“ von $D^\uparrow$ und die spezifische Rolle des Zentralisators bei der „Reparatur“ lokaler Translationen bietet ein tieferes theoretisches Verständnis der Beziehung zwischen LCPs und CPs.
Offene Probleme: Der Autor rahmt die Konnektivität von $D^\uparrow$ und die Existenz von APN-Funktionen innerhalb dieser Klasse bescheiden als offene Probleme ein und deutet an, dass die Experimente die Konnektivität zwar stützen, ein formaler Beweis jedoch erforderlich ist. Zudem wird angemerkt, dass die Ergebnisse zwar auf eine potenzielle Verbindung zu APN-Permutationen hindeuten, aber keine APN-Permutationen explizit in dieser Arbeit etabliert wurden.