🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

Diese Arbeit untersucht grundlegende Resultate und jüngste Fortschritte im Entwurf und der Analyse von booleschen Bent-Funktionen, wobei der Schwerpunkt insbesondere auf deren Beziehung zur vervollständigten Maiorana-McFarland-Klasse liegt.

Ursprüngliche Autoren: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Veröffentlicht 2026-08-25

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

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

In der verborgenen Architektur moderner digitaler Sicherheit existiert ein spezielles mathematisches Objekt, das als bent-Funktion bekannt ist. Dies sind keine physischen Geräte oder biologischen Entitäten, sondern komplexe Regeln zur Verarbeitung binärer Daten – Zeichenketten aus Einsen und Nullen, die die Grundlage der gesamten Computerkommunikation bilden. Stellen Sie sich eine riesige Landschaft möglicher Regeln vor, in der die meisten vorhersehbar und leicht zu analysieren sind. Bent-Funktionen stehen an der Spitze der Unvorhersehbarkeit; sie befinden sich so weit wie möglich entfernt von jedem einfachen, geradlinigen Muster. Aufgrund dieser extremen Unregelmäßigkeit sind sie unschätzbare Werkzeuge für den Schutz von Daten in der Kryptographie und in Fehlerkorrekturverfahren, da sie als chaotisches Rauschen fungieren, das Verhindert, dass Lauscher ein Signal finden. Seit Jahrzehnten wissen Mathematiker, wie man eine spezifische, gut verstandene Familie dieser Funktionen konstruiert, eine Gruppe, die nach den Forschern benannt ist, die sie zuerst beschrieben haben. Diese Familie, oft als Maiorana-McFarland-Klasse bezeichnet, hat als primärer Bauplan für die Erstellung von bent-Funktionen gedient, vergleichbar mit einem Standard-Architekturplan für den Bau eines Hauses. Doch eine anhaltende Frage hat das Feld heimgesucht: Sind diese Standard-Baupläne der einzige Weg, um solche Funktionen zu bauen, oder existieren andere, seltsamere Designs, die wir bisher noch nicht entdeckt haben?

Ein Team von Forschern hat nun eine umfassende Untersuchung dieser Frage vorgenommen und die gesamte Landschaft der bent-Funktionen sondiert, um zu sehen, wie sie mit jener Standardfamilie zusammenhängen. Ihre Arbeit bestätigt, dass die bekannten Baupläne, obwohl sie nützlich sind, nur einen winzigen Bruchteil der Gesamtmöglichkeiten darstellen. Im speziellen Fall von Funktionen mit acht Variablen haben Computersuchen ergeben, dass die Gesamtzahl der bent-Funktionen astronomisch groß ist, etwa zwei hoch einhundertsechs. Im krassen Gegensatz dazu wird die Anzahl der Funktionen, die unter Verwendung des Standard-Maiorana-McFarland-Bauplans gebaut werden können, auf höchstens zwei hoch einundachtzig geschätzt. Diese massive Lücke deutet darauf darauf hin, dass die überwiegende Mehrheit der bent-Funktionen fundamental anders ist als die, die wir explizit konstruieren konnten. Das Ziel der Forscher war es, das Territorium zwischen diesen beiden Extremen kartografisch zu erfassen, neue Methoden für den Bau von bent-Funktionen zu identifizieren, die definitiv nicht in die alte Form passen, und die strukturellen Gründe zu verstehen, warum sie sich so sehr unterscheiden.

Die Arbeit beginnt mit der Untersuchung zweier spezifischer Familien von bent-Funktionen, bekannt als C- und D-Klassen, die dazu entwickelt wurden, den Standard-Bauplan zu modifizieren. Diese Familien führen kleine, bewusste Änderungen an der Standardformel ein, indem sie spezifische Muster zum Output hinzufügen. Die Forscher untersuchten, ob diese Modifikationen ausreichten, um die resultierenden Funktionen aus der Standardfamilie zu drängen. Sie fanden heraus, dass diese modifizierten Funktionen unter bestimmten Bedingungen tatsächlich verschieden sind. Wenn beispielsweise die zugrunde liegende Permutation, die in der Konstruktion verwendet wird, über spezifische algebraische Eigenschaften verfügt – im Wesentlichen, wenn sie bestimmte verborgene Symmetrien vermissen lässt –, kann die resultierende bent-Funktion nicht in die Standardform zurücktransformiert werden. Die Autoren lieferten klare, testbare Regeln, um zu bestimmen, wann eine Funktion zu diesen neuen, exotischen Familien gehört und wann sie in der alten gefangen bleibt. Sie untersuchten auch „Superklassen“, die verschiedene Arten von Modifikationen kombinieren, und stellten fest, dass einige Kombinationen funktionieren, während andere gar keine bent-Funktionen erzeugen, was die notwendige Balance verdeutlicht, die erforderlich ist, um das notwendige Maß an Unvorhersehbarkeit aufrechtzuerhalten.

Jenseits dieser spezifischen Familien betrachteten die Forscher Funktionen, die auf der multiplikativen Struktur endlicher Körper basieren, oft beschrieben durch Trace-Terme. Dies sind Funktionen, bei denen der Output von der Summe einer Zahl abhängig ist, die zu einer bestimmten Potenz erhoben wird. Die Studie hebt hervor, dass viele dieser Funktionen, insbesondere solche, die auf bestimmten Exponenten basieren, nachweislich außerhalb der Standardfamilie liegen. Die Forscher verwendeten einen spezifischen mathematischen Test unter Verwendung von Ableitungen zweiter Ordnung – eine Methode, um zu messen, wie sich die Änderungsrate der Funktion selbst verändert –, um zu beweisen, dass diese Funktionen die strukturelle Regelmäßigkeit aufweisen, die in der Standardklasse zu finden ist. Sie untersuchten auch Funktionen, die als Indikatoren für andere wichtige mathematische Objekte dienen, wie etwa fast perfekte nichtlineare Funktionen, und zeigten, dass diese Indikatoren oft die einzigartigen, nicht-standardmäßigen Eigenschaften von bent-Funktionen besitzen, die außerhalb der bekannten Familien liegen.

Ein zentrales Thema der Forschung ist das Konzept eines „Linearitätsindex“, der als Maß dafür betrachtet werden kann, wie sehr eine Funktion einem einfachen, linearen Muster ähnelt. Die Standard-Maiorana-McFarland-Funktionen haben einen hohen Linearitätsindex, was bedeutet, dass sie in große, einfache affine Stücke zerlegt werden können. Die Forscher identifizierten eine neue Kategorie von Funktionen mit dem minimal möglichen Linearitätsindex, die sie „optimal“ nennen. Diese Funktionen sind das Gegenteil der Standardfunktionen; sie sind so unregelmäßig, dass sie überhaupt nicht in große affine Blöcke vereinfacht werden können. Die Arbeit beschreibt, wie man diese optimalen Funktionen konstruiert, und beweist, dass sie fundamental verschieden von der Standardklasse sind. Durch die Untersuchung der „M-Unterräume“ – spezieller geometrischer Substrukturen innerhalb des Funktionsbereichs, die seine zugrunde liegende Symmetrie offenbaren – zeigten die Autoren, dass diese optimalen Funktionen eine einzigartige, minimale Struktur besitzen, die die Standardfunktionen schlichtweg nicht haben.

Die Untersuchung vertieft sich auch in einen breiteren, flexibleren Rahmen, der als die verallgemeinerte Maiorana-McFarland-Klasse bezeichnet wird. Dieser Rahmen ermöglicht Funktionen, die aus affinen Stücken unterschiedlicher Größe aufgebaut sind, statt nur aus der festen Größe, die in der Standardklasse verwendet wird. Die Forscher charakterisierten exakt, wann eine Funktion in dieser breiteren Klasse innerhalb der Standardfamilie bleibt und wann sie aus ihr heraustritt. Sie fanden heraus, dass man durch die sorgfältige Wahl der Bausteine Funktionen erschaffen kann, die „fast“ Standard sind, aber dennoch verschieden, sowie Funktionen, die völlig fremd gegenüber der Standardfamilie sind. Die Arbeit schließt mit der Auflistung mehrerer offener Probleme und räumt ein, dass sie zwar signifikante Teile dieses mathematischen Territoriums kartografiert haben, die vollständige Enumeration aller bent-Funktionen jedoch ein Mysterium bleibt. Sie fordern zukünftige Forscher heraus, mehr unendliche Familien dieser exotischen Funktionen zu finden und die präzisen algebraischen Strukturen zu verstehen, die sie einzigartig machen, um sicherzustellen, dass sich das Feld über die Grenzen der ursprünglichen Baupläne hinaus weiterentwickelt.

Technisches Resümee: Bent-Funktionen und die vervollständigte Maiorana-McFarland-Klasse

Problemstellung
Booleanische Bent-Funktionen, eingeführt von Rothaus, repräsentieren eine fundamentale Klasse von Funktionen mit einer geraden Anzahl von Variablen, die maximale Nichtlinearität (maximalen Abstand zu affinen Funktionen) erreichen. Während die Maiorana-McFarland-Klasse (M) und deren vervollständigte Version ( $M^\#$ ) die am gründlichsten verstandene explizite Familie von Bent-Funktionen darstellen, deutet jüngste computergestützte Evidenz auf eine signifikante Diskrepanz zwischen der Gesamtzahl der Bent-Funktionen und jenen, die zur $M^\#$ -Klasse gehören, hin. Speziell in Dimension 8 beträgt die Gesamtzahl der Bent-Funktionen etwa $2^{106}$ , während die Anzahl der äquivalenten Maiorana-McFarland-Funktionen auf höchstens $2^{81}$ geschätzt wird. Diese Beobachtung motiviert das zentrale Problem dieser Untersuchung: die Charakterisierung von Bent-Funktionen, die außerhalb der vervollständigten Maiorana-McFarland-Klasse ( $M^\#$ ) liegen, das Verständnis ihrer algebraischen Strukturen und die Entwicklung expliziter Konstruktionsmethoden für solche Funktionen. Die Arbeit konzentriert sich auf das „Exklusionsproblem“ – die Bestimmung des Schnittpunkts verschiedener Klassen von Bent-Funktionen mit $M^\#$ und die Identifizierung von Bedingungen, unter denen Funktionen nachweislich außerhalb dieser Klasse liegen.

Methodik
Die Arbeit verwendet eine umfassende Survey-Methodik, die grundlegende Ergebnisse und jüngste Fortschritte im Design und der Analyse von Booleanischen Bent-Funktionen synthetisiert. Der technische Ansatz stützt sich schwerpunktmäßig auf:

Algebraische Charakterisierung: Nutzung des Kriteriums der zweiten Ableitung (Lemma 1.2), um die Zugehörigkeit zu $M^\#$ zu charakterisieren. Eine Funktion gehört genau dann zu $M^\#$ , wenn es einen $m$ -dimensionalen Unterraum $U$ gibt, sodass alle zweiten Ableitungen $D_a D_b f$ für $a, b \in U$ verschwinden.
Linearitätsindex und M-Unterräume: Analyse des „Linearitätsindex“ ($ind(f)$), definiert als der maximale Durchmesser eines M-Unterraums (ein Unterraum, in dem zweite Ableitungen verschwinden). Funktionen mit $ind(f) = n/2$ gehören zu $M^\#$ , während Funktionen mit minimalen Indizes ($ind(f)=1$) als $\ell$ -optimal bezeichnet werden.
Sekundäre Konstruktionen: Untersuchung, wie Operationen wie direkte/indirekte Summen, Konkatenationen (2- und 4-Konkatenation) sowie das Hinzufügen von Trace-Termen oder Indikatoren von Unterräumen die Zugehörigkeit zu $M^\#$ beeinflussen.
Generalisierte Frameworks: Erweiterung der Analyse von der klassischen M-Klasse ( $r=s=n/2$ ) zur Generalisierten Maiorana-McFarland (GMM)-Klasse ( $Mr,s$ ), wobei $f(x,y) = x \cdot \phi(y) + h(y)$ mit $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s$ und $r \neq s$ .

Wesentliche Beiträge und Ergebnisse

Carlets C- und D-Klassen: Die Arbeit beschreibt die C- und D-Klassen, welche die Maiorana-McFarland-Form durch das Hinzufügen von Indikatoren von Vektorunterräumen modifizieren.
- Klasse C: Funktionen der Form $x \cdot \pi(y) + 1_{L^\perp}(x)$ . Die Autoren fassen hinreichende Bedingungen für die Permutation $\pi$ und den Unterraum $L$ (speziell Eigenschaft (C)) zusammen, die garantieren, dass die Funktion bent und außerhalb von $M^\#$ ist. Ein Schlüsselergebnis betrifft Permutationen, deren Komponenten keine nicht-verschwindenden linearen Strukturen aufweisen.
- Klasse D und $D_0$ : Funktionen der Form $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ und die Unterklasse $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ ). Die Arbeit liefert eine vollständige Charakterisierung von $D_0 \cap M^\#$ und zeigt, dass die Zugehörigkeit bei quadratischen Permutationen davon abhängt, ob die Permutation auf einem affinen Hyperplan affin ist. Für höhere Grade liegen Funktionen oft außerhalb von $M^\#$ .
- Superklassen: Die Untersuchung betrachtet Superklassen (SC, CD, SD), die durch die Kombination von Indikatoren gebildet werden. Es wird festgestellt, dass einige Kombinationen (wie SC) Bent-Funktionen außerhalb von $M^\#$ liefern, während andere (wie SD) gar keine Bent-Funktionen erzeugen.
Trace-Terme und die $P_\tau$ -Eigenschaft:
- Die Arbeit überprüft Monomial-, Binomial- und verwandte Bent-Funktionen, die über Trace-Terme definiert sind (z. B. Dillon- und Kasami-Exponenten). Sie bestätigt, dass viele dieser Funktionen, insbesondere solche mit spezifischen Niho-Exponenten, außerhalb von $M^\#$ liegen.
- Ein wesentlicher Teil widmet sich der $P_\tau$ -Eigenschaft, die das Hinzufügen von Polynomkombinationen von Trace-Termen zu einer Bent-Funktion beinhaltet. Die Arbeit detailliert, wie die $P_\tau$ -Eigenschaft – charakterisiert durch verschwindende zweite Ableitungen der dualen Funktion – die Konstruktion unendlicher Familien von Bent-Funktionen außerhalb von $M^\#$ ermöglicht, die nicht durch die C- oder D-Klassen abgedeckt werden.
Generalisierte Maiorana-McFarland (GMM)-Klasse:
- Die Arbeit führt die GMM-Klasse ( $Mr,s$ ) und deren vervollständigte Version ein. Sie charakterisiert die Bent-Eigenschaft in dieser Klasse mittels „Bent-Mengen“ und „teilweise definierter Bent-Funktionen“.
- Fast Maiorana-McFarland ( $k=1$ ): Funktionen mit einem Linearitätsindex von $n/2 - 1$ werden analysiert. Die Arbeit unterscheidet zwischen „trivialen“, „nicht-echten“ und „echten“ Partitionen des Definitionsbereichs und zeigt, dass spezifische echte Partitionen Bent-Funktionen außerhalb von $M^\#$ ergeben.
- $\ell$ -optimale Funktionen: Die Untersuchung diskuttierte Funktionen mit minimalem Linearitätsindex ($ind(f)=1$) und stellt fest, dass diese das „Gegenteil“ von Maiorana-McFarland-Funktionen sind. Konstruktionen, die Permutationen mit der Eigenschaft (P1) (nicht-verschwindende zweite Ableitungen) nutzen, werden als Methode hervorgehoben, um solche Funktionen zu generieren.
M-Unterräume und sekundäre Konstruktionen:
- Die Arbeit liefert eine tiefgehende algebraische und kombinatorische Analyse von M-Unterräumen. Sie etabliert Schranken für die Anzahl maximaler M-Unterräume und verknüpft diese mit der Klassifizierung von Bent-Funktionen.
- Sie präsentiert notwendige und hinreichende Bedingungen dafür, dass sekundäre Konstruktionen (direkte Summe, indirekte Summe, 2- und 4-Konkatenation) zu Funktionen außerhalb von $M^\#$ führen. Insbesondere wird bewiesen, dass die 4-Konkatenation einer außerhalb von $M^\#$ liegenden Bent-Funktion mit einer beliebigen anderen Bent-Funktion eine neue Bent-Funktion ergibt, die ebenfalls außerhalb von $M^\#$ liegt.

Bedeutung
Die Arbeit positioniert sich als umfassender Survey, der die Lücke zwischen der gut verstandenen Maiorana-McFarland-Klasse und dem weiten, weitgehend unklassifizierten Raum der Bent-Funktionen schließt. Ihre primäre Bedeutung liegt in:

Systematisierung der Exklusion: Bereitstellung eines einheitlichen Rahmens zur Bestimmung, wann Bent-Funktionen außerhalb von $M^\#$ liegen, indem sie über ad-hoc Beispiele hinausgeht und strukturelle Charakterisierungen basierend auf Linearitätsindizes und M-Unterräumen nutzt.
Erweiterung der Konstruktionsmethoden: Detaillierung expliziter Methoden (C, D, $P_\tau$ , GMM), um unendliche Familien von Bent-Funktionen außerhalb von $M^\#$ zu generieren, was den spärlichen Beispielen in festen Dimensionen entgegenwirkt.
Klärung der algebraischen Struktur: Einführung und Verfeinerung von Konzepten wie dem Linearitätsindex und M-Unterräumen als fundamentale Werkzeuge zum Verständnis der algebraischen Eigenschaften von Bent-Funktionen und ihrer Beziehung zur generalisierten Maiorana-McFarland-Hierarchie.
Identifizierung offener Probleme: Die Arbeit schließt mit der Auflistung zahlreicher offener Probleme ab, darunter die exakte Enumeration von EA-Äquivalenzklassen in $M^\#$ , die Erweiterung dieser Theorien auf $p$ -äre Bent-Funktionen sowie die Konstruktion von Differenzmengen außerhalb der McFarland-Klasse.

Die Autoren wahren einen bescheidenen Ton und erkennen an, dass trotz erheblicher Fortschritte bei der Identifizierung von Funktionen außerhalb von $M^\#$ , die Gesamtenumeration der Bent-Funktionen und eine vollständige Klassifizierung ihrer algebraischen Strukturen weiterhin offene Herausforderungen bleiben. Das Werk dient als fundiertes Referenzwerk für Forscher, die darauf abzielen, kryptographisch signifikante Booleanische Funktionen mit spezifischen Nichtlinearitätseigenschaften zu entwerfen, die durch die Standard-Maiorana-McFarland-Konstruktion nicht erfasst werden können.

Mehr davon