🔢 mathematics

On Generalizations of Maiorana-McFarland and $\mathcal{PS}_{ap}$ Functions

Diese Arbeit stellt neue Verallgemeinerungen der Maiorana-McFarland- und $\mathcal{PS}_{ap}$ -Klassen von Bogen-Funktionen vor, die außerhalb der abgeschlossenen klassischen Klassen liegen, und untersucht deren Zerlegbarkeit sowie eine sekundäre Konstruktion mittels Verkettung unter Verwendung von Methoden aus der Theorie algebraischer Kurven und der Ableitungen von Bogen-Funktionen.

Ursprüngliche Autoren: Sezel Alkan, Nurdagül Anbar, Athina Avrantini, Erroxe Etxabarri-Alberdi, Tekgül Kalaycı, Beatrice Toesca

Veröffentlicht 2026-03-31

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Sezel Alkan, Nurdagül Anbar, Athina Avrantini, Erroxe Etxabarri-Alberdi, Tekgül Kalaycı, Beatrice Toesca

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 sind ein Architekt, der unsichtbare, perfekt symmetrische Muster für ein geheimes Schloss entwirft. In der Welt der Mathematik und Kryptografie heißen diese Muster Bent-Funktionen. Sie sind wie die ultimativen "Chaos-Ordnungs"-Hybriden: Sie sehen völlig zufällig aus, sind aber mathematisch so perfekt strukturiert, dass sie für Verschlüsselung unzerstörbar sind.

Dieser Artikel ist wie ein Reisebericht von sechs Architekten, die zwei alte, bewährte Baupläne für solche Schlösser untersuchen und dann völlig neue, revolutionäre Entwürfe präsentieren.

Hier ist die Geschichte des Papiers, einfach erklärt:

1. Die alten Baupläne (MM und PSap)

Seit Jahrzehnten kennen die Mathematiker zwei Hauptmethoden, um diese perfekten Muster zu bauen:

Die Maiorana-McFarland-Methode (MM): Stellen Sie sich vor, Sie haben einen riesigen Schrank mit Schubladen. Diese Methode sagt: "Nimm eine Schubladen-Nummer, schalte einen Hebel um, und du hast dein Muster." Es ist eine sehr direkte, mechanische Bauweise.
Die PSap-Methode (Partial Spread): Hier bauen Sie das Muster aus vielen kleinen, sich nicht überschneidenden Inseln. Jede Insel hat eine eigene Regel, aber zusammen ergeben sie ein perfektes Ganzes.

Das Problem? Viele dieser alten Schlösser sind zu vorhersehbar. Krypto-Angriffe können sie knacken, wenn sie wissen, wie der Schlüsselmechanismus funktioniert. Die Forscher wollten also neue Schlösser bauen, die nicht wie die alten aussehen.

2. Der erste große Durchbruch: Der "Misch- und Wende"-Trick

Die Autoren haben eine neue Art von MM-Funktion erfunden, nennen wir sie "Generalisierte MM".

Die Analogie: Stellen Sie sich vor, Sie haben zwei verschiedene Arten von Teig (z. B. Schokoladen- und Vanille-Teig). Die alte Methode sagte: "Mische nur Schokolade." Die neue Methode sagt: "Wenn du einen bestimmten Knopf drückst, nimm Schokoladenteig. Wenn du einen anderen drückst, nimm Vanille. Aber hier ist der Clou: Wir mischen sie so geschickt, dass das Ergebnis weder reiner Schokoladenteig noch reiner Vanille-Teig ist."
Das Ergebnis: Sie haben Funktionen gebaut, die so komplex sind, dass sie nicht in die alte Kategorie der "MM-Schlösser" passen. Sie sind wie ein neues, unbekanntes Material. Selbst wenn jemand versucht, sie mit den alten Werkzeugen zu zerlegen, scheitert er. Sie liegen "außerhalb des bekannten Universums".

3. Der zweite Durchbruch: Warum man manche Schlösser nicht zerlegen kann

Ein zweites Thema des Papers ist die Frage: "Kann man diese neuen, komplexen Schlösser in einfachere Teile zerlegen?"

Die Analogie: Stellen Sie sich vor, Sie haben einen riesigen, komplizierten Puzzle-Kasten. Normalerweise kann man sagen: "Ah, das ist nur ein kleineres Puzzle, das ich hier und da angehängt habe." Das nennt man "Zerlegung" (Decomposition).
Die Entdeckung: Die Autoren haben bewiesen, dass bei ihren neuen, generalisierten PSap-Funktionen (denen, die auf den "Inseln" basieren) das nicht funktioniert. Wenn das Muster komplex genug ist (genauer gesagt, wenn der mathematische "Grad" niedrig ist im Vergleich zur Größe des Feldes), dann ist das Puzzle ein einziges, untrennbares Ganzes.
Warum ist das wichtig? Viele alte Methoden, um neue Schlösser zu bauen, basierten darauf, kleine Puzzles zusammenzukleben (Konkatenation). Die Autoren zeigen: "Hey, diese neuen Schlösser lassen sich nicht kleben! Sie müssen von Grund auf neu gedacht werden." Das ist ein wichtiger Hinweis für Krypto-Experten: Man kann nicht einfach alte Bausteine nehmen und hoffen, dass sie funktionieren.

4. Der dritte Teil: Das "Vier-Farben"-Klebe-Experiment

Am Ende des Papers zeigen die Autoren, wie man trotzdem neue, sichere Schlösser bauen kann, indem man die Teile ihrer neuen Funktionen clever kombiniert.

Die Analogie: Stellen Sie sich vor, Sie haben ein vektorielles Schloss, das aus vier verschiedenen Farben besteht (z. B. Rot, Blau, Grün, Gelb). Normalerweise würde man sagen: "Das ist ein einziges Ding." Aber die Autoren sagen: "Nein, nehmen wir die rote Komponente, die blaue, die grüne und die gelbe, und kleben wir sie in einem ganz spezifischen, mathematisch perfekten Muster aneinander."
Das Ergebnis: Wenn man diese vier Teile richtig anordnet (eine sogenannte "4-Konkatenation"), entsteht ein neues, sicheres Bent-Modell. Es ist wie ein Mosaik, das aus vier verschiedenen, aber perfekt passenden Fliesen besteht.

Zusammenfassung für den Alltag

Stellen Sie sich vor, Sie bauen ein Schloss für eine Bank:

Früher: Man baute sie aus Standard-Bausteinen (MM und PSap). Hacker haben gelernt, diese zu knacken.
Jetzt (Dieses Papier):
- Die Autoren haben neue, exotische Bausteine erfunden, die so aussehen, als wären sie aus einem anderen Universum (Generalisierte MM).
- Sie haben bewiesen, dass man diese neuen Bausteine nicht in einfache Teile zerlegen kann (keine Zerlegung bei PSap). Das macht sie robuster gegen bestimmte Angriffe.
- Sie haben eine neue Klebetechnik entwickelt, um aus den Teilen dieser komplexen Schlösser noch stärkere, neue Schlösser zu bauen.

Warum ist das cool?
In einer Welt, in der Computer immer schneller werden und alte Verschlüsselungsmethoden brechen, brauchen wir ständig neue, unvorhersehbare mathematische Muster. Dieses Papier liefert die Baupläne für genau diese neuen, widerstandsfähigen Muster. Es zeigt uns, dass es noch viele unbekannte Ecken im mathematischen Universum gibt, in denen wir noch sicherere Geheimnisse verstecken können.

Titel: Verallgemeinerungen von Maiorana–McFarland- und PSap-Funktionen
Autoren: Sezel Alkan, Nurdagül Anbar, Athina Avrantini, Erroxe Etxabarri-Alberdi, Tekgül Kalaycı, Beatrice Toesca

1. Problemstellung und Motivation

Die Konstruktion von bent Funktionen (maximal nichtlineare boolesche Funktionen), die außerhalb der abgeschlossenen Maiorana–McFarland-Klasse ( $MM^\#$ ) liegen, ist ein zentrales Forschungsgebiet in der Kryptographie und der Theorie der booleschen Funktionen. Während alle bent Funktionen in Dimensionen bis zu 6 zur Klasse $MM^\#$ gehören, gibt es in höheren Dimensionen (ab $n=8$ ) bent Funktionen, die nicht äquivalent zu Funktionen dieser Klasse sind.

Die beiden klassischen primären Konstruktionsmethoden für bent Funktionen sind:

Die Maiorana–McFarland (MM)-Klasse.
Die Desarguesische Partial-Spread (PSap)-Klasse.

Das Hauptproblem besteht darin, neue Familien von bent Funktionen zu konstruieren, die weder zur $MM^\#$ -Klasse noch zur $PSap^\#$ -Klasse gehören, und deren strukturelle Eigenschaften (wie Zerlegbarkeit) zu analysieren. Insbesondere ist die Frage offen, ob verallgemeinerte PSap-Funktionen durch Sekundärkonstruktionen (wie Konkatenation) aus bekannten bent oder semibent Funktionen gewonnen werden können.

2. Methodik

Die Autoren bedienen sich einer Kombination aus algebraischen Methoden und der Theorie algebraischer Kurven über endlichen Körpern:

Verallgemeinerte Konstruktionen: Sie nutzen verallgemeinerte Maiorana–McFarland (GMM) und verallgemeinerte PSap (G-PSap) Konstruktionen, die auf endlichen Körpern $\mathbb{F}_{p^n}$ definiert sind (mit Fokus auf $p=2$ , also boolesche Funktionen).
Kriterien für Äquivalenz: Zur Charakterisierung der Zugehörigkeit zur $MM^\#$ -Klasse verwenden sie das Dillon-Kriterium, das auf dem Verschwinden von zweiten Ableitungen (second-order derivatives) über einem Unterraum (M-Unterraum) basiert. Eine Funktion gehört genau dann zu $MM^\#$ , wenn sie einen M-Unterraum der Dimension $n/2$ besitzt.
Zerlegungsanalyse: Die Untersuchung der Zerlegbarkeit (Decomposition) von bent Funktionen erfolgt über die Analyse der zweiten Ableitung der dualen Funktion $f^*$ . Ein bent Funktion erlaubt eine semibent Zerlegung genau dann, wenn ihre duale Funktion einen nicht-trivialen M-Unterraum besitzt.
Algebraische Geometrie: Ein wesentlicher Teil der Beweise stützt sich auf die Abschätzung der Anzahl rationaler Punkte auf algebraischen Kurven (insbesondere Artin-Schreier-Kurven) über endlichen Körpern mittels der Hasse-Weil-Schranke. Dies dient dazu zu zeigen, dass bestimmte zweite Ableitungen nicht konstant sind.

3. Wichtige Beiträge und Ergebnisse

A. Konstruktion von GMM-Funktionen außerhalb der $MM^\#$ -Klasse

Die Autoren stellen eine neue Familie von verallgemeinerten Maiorana–McFarland-Funktionen vor, die nicht zur abgeschlossenen MM-Klasse gehören.

Ansatz: Sie kombinieren MM-Funktionen, die nur triviale gemeinsame M-Unterräume besitzen (Dimension $\le 1$ ), in einem höherdimensionalen GMM-Rahmen.
Mechanismus: Durch die Verwendung einer Permutation $\pi$ , die eine spezifische Eigenschaft (P) erfüllt (basierend auf der Struktur der zweiten Ableitungen), und durch geschicktes "Mischen" von MM-Funktionen über verschiedene Unterräume, wird sichergestellt, dass die resultierende Funktion keinen M-Unterraum der kritischen Dimension $n/2 + k$ besitzt.
Ergebnis: Es werden explizite Klassen von Funktionen konstruiert (basierend auf Permutationen wie $x^{2^m-2}$ und Gold-Funktionen $x^{2^k+1}$ unter bestimmten Bedingungen an $m$ und $k$ ), die zur GMM-Klasse gehören, aber nicht äquivalent zu Funktionen in $MM^\#$ sind.

B. Zerlegbarkeit verallgemeinerter PSap-Funktionen

Die Autoren untersuchen, ob verallgemeinerte PSap-Funktionen durch Konkatenation von bent oder semibent Funktionen entstehen.

Hauptresultat: Sie beweisen, dass verallgemeinerte PSap-Funktionen, deren algebraischer Grad hinreichend klein im Verhältnis zur Größe des zugrundeliegenden endlichen Körpers ist, im Allgemeinen keine Zerlegung in bent oder semibent Funktionen zulassen.
Beweisführung: Sie zeigen, dass die duale Funktion dieser PSap-Funktionen keine nicht-trivialen M-Unterräume besitzt. Dies wird durch den Nachweis erreicht, dass die zweite Ableitung der dualen Funktion nicht konstant ist. Die Nicht-Konstanz wird durch die Existenz rationaler Punkte auf zugehörigen algebraischen Kurven (Artin-Schreier-Kurven) gesichert, wobei die Hasse-Weil-Schranke verwendet wird, um die Existenz dieser Punkte für hinreichend große $m$ zu garantieren.
Konsequenz: Solche Funktionen können nicht durch bekannte Sekundärkonstruktionen (basierend auf Konkatenation) erhalten werden.

C. Sekundärkonstruktion durch Konkatenation von Vektorfunktionen

Als dritten Beitrag präsentieren die Autoren eine neue Sekundärkonstruktion für boolesche bent Funktionen.

Idee: Sie nutzen die Komponenten von vektorwertigen verallgemeinerten PSap-Funktionen.
Ergebnis: Durch Konkatenation der Komponenten dieser vektorwertigen Funktionen (unter Ausnutzung spezifischer Eigenschaften der dualen Funktionen, wie z.B. $(F_\alpha)^* + (F_\beta)^* = (F_{\alpha+\beta})^*$ ) entsteht eine neue Familie von booleschen bent Funktionen.
Theorem 4: Es wird eine allgemeine Konstruktion vorgestellt, die auf der Verteilung der Urbilder (preimage distribution) der verallgemeinerten Desarguesischen Streuung basiert und bent Funktionen erzeugt, die durch eine Partition des Raums definiert sind.

4. Signifikanz und Bedeutung

Erweiterung des Konstruktionswissens: Die Arbeit liefert neue, explizite Klassen von bent Funktionen, die außerhalb der etablierten $MM^\#$ - und $PSap^\#$ -Klassen liegen. Dies ist entscheidend für die Suche nach Funktionen mit optimalen kryptographischen Eigenschaften, da die $MM^\#$ -Klasse nur einen winzigen Bruchteil aller bent Funktionen ausmacht.
Strukturelle Einsichten: Die Ergebnisse zur Nicht-Zerlegbarkeit verallgemeinerter PSap-Funktionen klären die Grenzen bekannter Sekundärkonstruktionen auf. Sie zeigen, dass es "neue" bent Funktionen gibt, die nicht aus einfacheren bent Funktionen durch Konkatenation aufgebaut werden können.
Methodische Stärke: Die erfolgreiche Anwendung der Theorie algebraischer Kurven und der Hasse-Weil-Schranke auf Probleme der booleschen Funktionentheorie demonstriert die Fruchtbarkeit der Verbindung zwischen endlicher Geometrie und Kryptographie.
Kryptographische Relevanz: Da bent Funktionen für die Konstruktion von S-Boxen und anderen kryptographischen Bausteinen verwendet werden, erweitert diese Arbeit das Portfolio an verfügbaren, sicheren Funktionen und bietet neue Ansätze für die Analyse von Äquivalenzklassen.

Zusammenfassend leistet das Papier einen wesentlichen Beitrag zur Klassifikation und Konstruktion von bent Funktionen, indem es neue Familien außerhalb der klassischen Klassen identifiziert und deren strukturelle Unzerlegbarkeit mathematisch rigoros beweist.