🔢 mathematics

The combinatorial structure and value distributions of plateaued functions

Der Artikel untersucht die kombinatorischen Eigenschaften und Werteverteilungen plateauer Funktionen, insbesondere deren Zusammenhang mit der Walsh-Transformation, Linearität und Differenzialuniformität, wobei er sich auf fast ausgeglichene Fälle und APN-Funktionen konzentriert.

Ursprüngliche Autoren: Lukas Kölsch, Alexandr Polujan

Veröffentlicht 2026-03-26

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Lukas Kölsch, Alexandr Polujan

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

🛡️ Die unsichtbaren Architekten der digitalen Sicherheit: Eine Reise zu „Plateaued"-Funktionen

Stellen Sie sich vor, Sie bauen ein gigantisches Schloss, das die Geheimnisse der Welt schützen soll. Die Wächter an den Toren sind mathematische Funktionen. Damit diese Wächter stark sind, müssen sie zwei Dinge tun:

Unvorhersehbar sein: Ein Angreifer darf nicht erraten können, was passiert, wenn er einen Knopf drückt (das nennt man Nichtlinearität).
Gut verteilt sein: Wenn viele Leute durch das Tor gehen, dürfen sie sich nicht alle in einer Ecke drängen. Sie sollten sich gleichmäßig im ganzen Schloss verteilen (das nennt man Ausgewogenheit).

Die Autoren dieses Papers, Lukas und Alexandr, haben sich eine spezielle Gruppe von Wächtern genauer angesehen: die sogenannten „Plateaued"-Funktionen (auf Deutsch etwa: „Plateau-Funktionen").

🏔️ Was ist eine „Plateau"-Funktion?

Stellen Sie sich eine Landschaft vor.

Eine flache Ebene wäre eine einfache, langweilige Funktion (wie eine lineare Gleichung). Das ist zu einfach zu knacken.
Ein spitzer Berg wäre eine extrem chaotische Funktion.
Eine Plateau-Funktion ist wie eine Hochfläche. Sie ist nicht ganz flach, aber sie hat keine steilen, unkontrollierbaren Spitzen. Sie ist „gut genug" in ihrer Unvorhersehbarkeit, aber strukturell überschaubar.

Fast alle wichtigen Bausteine in modernen Verschlüsselungen (wie in Bitcoin, WhatsApp oder Bank-Apps) basieren auf solchen Funktionen. Die Autoren fragen sich: „Wie genau sehen diese Landschaften aus, und wie verteilen sich die Besucher (die Daten) darauf?"

⚖️ Das Problem der „Fast-Ausgewogenheit"

Ein ideales Schloss hat eine perfekte Verteilung: Jeder Raum wird genau gleich oft betreten. Das nennt man ausgewogen (balanced).
Aber in der Mathematik ist Perfektion selten. Oft ist eine Funktion fast ausgewogen (almost balanced).

Die Analogie: Stellen Sie sich eine Party vor. Fast jeder Raum hat genau 10 Gäste. Aber in einem speziellen Raum gibt es plötzlich 12 Gäste, und in einem anderen nur 8.
Die Autoren haben herausgefunden, dass diese „fast perfekten" Funktionen eine sehr spezielle Struktur haben. Sie haben ein Werkzeug entwickelt (die Walsh-Transformation), das wie ein Röntgengerät funktioniert. Damit können sie durch die Funktion schauen und genau sehen, wie viele Gäste in welchem Raum sind, ohne die Party zu stören.

🧩 Das große Rätsel: Die „d-zu-1"-Funktionen

Ein besonders interessanter Fall sind Funktionen, die wie ein Trichter wirken.

Die Analogie: Stellen Sie sich vor, Sie haben 1000 Personen (Eingaben), die in 500 Räume (Ausgaben) gehen.
- Bei einer perfekten Verteilung gehen 2 Personen pro Raum.
- Bei einer d-zu-1-Funktion (z. B. 3-zu-1) gehen immer genau 3 Personen in einen Raum, außer in einen einzigen Raum, wo nur 1 Person ist.

Die Autoren haben eine erstaunliche Entdeckung gemacht: Solche Trichter-Funktionen können nur dann als „Plateau"-Funktionen existieren, wenn die Zahl der Personen pro Raum (das „d") eine ganz bestimmte Form hat.
Es ist, als ob das Universum sagt: „Du darfst nur Trichter bauen, bei denen die Gruppengröße eine Zahl wie $p^t + 1$ ist (z. B. 3, 5, 9, 17...)." Andere Zahlen sind verboten. Das schränkt die Möglichkeiten für Krypto-Entwickler enorm ein und hilft ihnen, schwache Bausteine zu vermeiden.

🕵️‍♂️ Die APN-Helden (Fast-Perfekte Wächter)

Einige dieser Funktionen sind besonders stark: die APN-Funktionen. Sie sind die Elite-Wächter, die selbst bei raffinierten Angriffen (differential attacks) nicht wanken.
Die Autoren haben untersucht, wie diese Elite-Wächter ihre „Gäste" verteilen.

Ergebnis: Sie haben bewiesen, dass bestimmte Verteilungsmuster, die man theoretisch für möglich gehalten hat, für diese speziellen Plateau-Funktionen unmöglich sind.
Die Metapher: Es ist, als ob man herausfindet, dass ein bestimmter Wächter niemals in einer bestimmten Konstellation stehen kann. Wenn jemand behauptet, so etwas gesehen zu haben, dann war es entweder kein echter Wächter oder jemand hat gelogen.

💡 Warum ist das wichtig?

In der Welt der Cybersicherheit bauen wir auf diesen mathematischen Funktionen auf.

Sicherheit: Wenn wir wissen, welche Verteilungen möglich sind und welche nicht, können wir schwache Verschlüsselungen früher erkennen und vermeiden.
Effizienz: Die Autoren geben den Ingenieuren eine Art „Bauplan". Sie sagen: „Wenn du eine Plateau-Funktion bauen willst, die sicher ist, achte darauf, dass sie diese und jene Form hat."
Neue Wege: Sie zeigen, wie man aus bekannten Bausteinen (wie Monomen oder Maiorana-McFarland-Konstruktionen) neue, sichere Funktionen zusammensetzen kann.

Zusammenfassung in einem Satz

Die Autoren haben mit mathematischen Röntgenbildern herausgefunden, wie die „Landschaften" unserer digitalen Sicherheitswächter aufgebaut sein müssen, und bewiesen, dass nur sehr spezifische, fast-perfekte Verteilungen möglich sind – was uns hilft, stärkere und sicherere Verschlüsselungen für die Zukunft zu bauen.

Titel

Die kombinatorische Struktur und Werteverteilungen plateauerter Funktionen
(The combinatorial structure and value distributions of plateaued functions)

1. Problemstellung und Motivation

Plateauerte Funktionen bilden eine wichtige Oberklasse in der Kryptographie, die lineare, quadratische und gebogene (bent) Funktionen sowie die meisten bekannten APN-Funktionen (Almost Perfect Nonlinear) umfasst. Diese Funktionen sind entscheidend für die Konstruktion kryptografischer Primitive aufgrund ihrer hohen Nichtlinearität, Resilienz und niedrigen additiven Autokorrelation.

Ein zentrales Forschungsziel ist das Verständnis der Werteverteilung (Value Distribution) dieser Funktionen, insbesondere der Größe von Urbildmengen (Preimage Sets). Während für gebogene Funktionen und perfekte nichtlineare Funktionen bereits Ergebnisse vorliegen, fehlt eine umfassende Analyse für den allgemeinen Fall plateauerter Funktionen.
Die Autoren untersuchen speziell:

Das Zusammenspiel zwischen Walsh-Transformation, Linearität und Differential-Eigenschaften.
Die Existenz und Eigenschaften von „fast ausgeglichenen" (almost balanced) Funktionen, bei denen alle Urbilder bis auf eines die gleiche Größe haben.
Die kombinatorische Struktur von $d$ -zu-1-Funktionen (Funktionen, bei denen ein Urbild die Größe 1 hat und alle anderen nicht-leeren Urbilder die Größe $d$ ).
Die speziellen Eigenschaften von plateauerten APN-Funktionen, insbesondere im Hinblick auf ihre Werteverteilung und Imbalance.

2. Methodik

Die Arbeit basiert auf einer analytischen Herangehensweise, die die Walsh-Transformation als Hauptwerkzeug nutzt, um Rückschlüsse auf die Struktur von Urbildmengen zu ziehen.

Walsh-Transformation bei $a=0$ : Die Autoren nutzen die Tatsache, dass die Summe der Walsh-Koeffizienten bei $a=0$ direkt mit der Größe der Urbildmengen verknüpft ist.
Imbalance ( $N_bF$ ): Sie führen den Begriff der Imbalance ein, definiert als $N_bF = \frac{1}{p^m} \sum_{b \neq 0} |W_F(b, 0)|^2$ . Dieser Wert misst die Abweichung von einer ausgeglichenen (balanced) Funktion.
Ungleichungen und Momenten-Analyse: Durch Anwendung der Cauchy-Schwarz-Ungleichung auf die Summe der Quadrate der Urbildgrößen werden scharfe Schranken für die Größe einzelner Urbildmengen in Abhängigkeit von der Imbalance und der Bildmenge hergeleitet.
Spektrale Analyse: Da plateauerte Funktionen nur Walsh-Koeffizienten mit wenigen diskreten Werten (Amplituden) annehmen können, lassen sich starke strukturelle Einschränkungen für $d$ -zu-1-Funktionen und monomiale Funktionen ableiten.

3. Hauptbeiträge und Ergebnisse

A. Allgemeine Schranken und fast ausgeglichene Funktionen

Satz 3.3: Es werden neue Schranken für die Größe von Urbildmengen $|F^{-1}(\beta)|$ in Abhängigkeit von der Imbalance $N_bF$ und der Größe der Bildmenge hergeleitet.
Definition 3.7: Der Begriff der „fast ausgeglichenen" Funktion wird verallgemeinert. Eine Funktion ist fast ausgeglichen, wenn sie eine nicht-triviale Imbalance hat und die Schranke für mindestens ein Urbild mit Gleichheit erreicht wird. Dies verallgemeinert frühere Ergebnisse auf nicht-surjektive Fälle.
Satz 4.1: Für fast ausgeglichene, surjektive Funktionen wird gezeigt, dass alle nicht-trivialen Walsh-Koeffizienten bei $a=0$ den gleichen Betrag haben müssen. Dies führt zu einer exakten Charakterisierung der Urbildgrößen.

B. Plateauerte $d$ -zu-1-Funktionen

Satz 5.2: Dies ist ein zentrales Ergebnis. Es wird bewiesen, dass eine plateauerte $d$ $d$ -zu-1-Funktion $F: \mathbb{F}_p^n \to \mathbb{F}_p^n$ $F : F_{p}^{n} \to F_{p}^{n}$ (mit $d > 2$ $d > 2$ ) nur für sehr spezifische Werte von $d$ $d$ existieren kann.
- $n$ muss gerade sein.
- $d$ muss die Form $d = p^t + 1$ haben, wobei $t \ge 1$ und $t$ teilt $n/2$ .
- Die Funktion besitzt eine spezifische Mischung aus gebogenen (bent) und plateauerten Komponenten mit Amplituden $p^{n/2}$ und $p^{n/2+t}$ .
Korollar 5.4: Für monomiale Funktionen $F(x) = x^d$ folgt daraus, dass plateauerte Abbildungen entweder Permutationen ( $d=1$ ) oder $(p^t+1)$ -zu-1-Abbildungen sind.
Satz 5.5 & 5.6: Es werden untere Schranken für die differential uniformity (Differentialuniformität) abgeleitet. Eine $(p^t+1)$ -zu-1 plateauerte Funktion hat eine Differentialuniformität von mindestens $p^t$ . Sie erreicht genau $p^t$ genau dann, wenn sie differential zweiwertig ist (d.h. die Gleichung $F(x+a)-F(x)=b$ hat entweder 0 oder $p^t$ Lösungen).

C. Konstruktionen fast ausgeglichener Funktionen

Satz 5.8: Es wird eine Familie von plateauerten Funktionen über $\mathbb{F}_{2^n}$ definiert (basierend auf Spuren von Monomen $x^{2^r+1}$ ), die surjektiv und fast ausgeglichen sind.
Proposition 5.9 & 5.10: Es werden Konstruktionen vom Typ Maiorana-McFarland analysiert. Es wird gezeigt, wie durch geeignete Wahl der Komponenten (z.B. 2-zu-1 Permutationen) fast ausgeglichene plateauerte Funktionen konstruiert werden können, die entweder genau ein großes Urbild oder zwei große Urbilder haben.

D. Kombinatorische Struktur plateauerter APN-Funktionen

Proposition 6.3: Es werden untere und obere Schranken für die Imbalance $N_bF$ $N_{b} F$ von plateauerten APN-Funktionen hergeleitet.
- Untere Schranke: $(2^{n+1}-2)/3$ (erreicht, wenn $2(2^n-1)/3$ Komponenten gebogen und der Rest ausgeglichen sind).
- Obere Schranke: $2^{n+1}-2$ (erreicht, wenn keine Komponente ausgeglichen ist).
Lemma 6.4 & Satz 6.5: Es wird gezeigt, dass $N_bF \equiv 2 \pmod 4$ gilt und die Anzahl der gebogenen Komponenten einer plateauerten APN-Funktion $\equiv 2 \pmod 4$ ist.
Satz 6.7: Eine wichtige Nicht-Existenzaussage: Plateauerte APN-Funktionen mit der minimalen Bildmengengröße können nicht die zweite der drei bekannten Werteverteilungen (aus [19]) aufweisen. Diese Verteilung würde eine Imbalance von $2^{n+1}-4$ erfordern, was im Widerspruch zu Lemma 6.4 steht.
Satz 6.8: Plateauerte APN-Funktionen mit minimaler Bildmengengröße können keine ausgeglichenen Komponentenfunktionen besitzen.

4. Signifikanz und Implikationen

Die Arbeit leistet einen wesentlichen Beitrag zum Verständnis der Struktur kryptografisch relevanter Funktionen:

Verbindung von Spektrum und Struktur: Sie etabliert eine direkte und starke Verbindung zwischen der spektralen Eigenschaft (Walsh-Transformation/Imbalance) und der kombinatorischen Struktur (Größe der Urbilder).
Einschränkung von Konstruktionsmöglichkeiten: Die Ergebnisse zeigen, dass plateauerte $d$ -zu-1-Funktionen und insbesondere monomiale plateauerte Funktionen extrem eingeschränkt sind. Dies schränkt die Suche nach neuen APN-Kandidaten ein und liefert notwendige Bedingungen für deren Existenz.
Klärung von APN-Eigenschaften: Durch die Analyse der Imbalance und der Anzahl gebogener Komponenten werden neue notwendige Bedingungen für APN-Funktionen abgeleitet. Die Unmöglichkeit bestimmter Werteverteilungen für plateauerte APN-Funktionen hilft, die „Big APN"-Vermutung (Existenz von APN-Permutationen in gerader Dimension) weiter einzugrenzen.
Praktische Relevanz: Da viele moderne kryptografische Algorithmen (wie Keccak, Ascon) und Zero-Knowledge-Proof-Systeme (Poseidon, Rescue-Prime) auf monomialen oder plateauerten Funktionen basieren, liefern diese Ergebnisse wichtige Kriterien für die Bewertung der Sicherheit und Struktur dieser Primitive.

Zusammenfassend bietet das Paper einen theoretischen Rahmen, der es ermöglicht, die Werteverteilung und kombinatorische Struktur einer breiten Klasse kryptografischer Funktionen präzise zu analysieren und zu klassifizieren.