The combinatorial structure and value distributions of plateaued functions

Titel: De combinatorische structuur en waardeverdelingen van plateau-functies

1. Probleemstelling

Plateau-functies vormen een belangrijke veralgemening van kwadratische functies, gebogen functies (bent functions) en de meeste bekende APN-functies (Almost Perfect Nonlinear). Deze functies zijn fundamenteel voor de cryptografie vanwege eigenschappen zoals hoge nonlineariteit, resiliëntie en lage additieve autocorrelatie.

Hoewel er veel onderzoek is gedaan naar specifieke klassen (zoals gebogen of APN-functies), ontbreekt er een diepgaand inzicht in de waardeverdeling (value distribution) van plateau-functies in het algemeen. Specifiek wordt onderzocht:

• Hoe groot de preimage-sets (de verzameling van invoerwaarden die naar een specifieke uitvoerwaarde afbeelden) zijn.
• De relatie tussen de Walsh-transformatie, de lineariteit en de differential uniformiteit van deze functies.
• De bestaansvoorwaarden voor "bijna gebalanceerde" (almost balanced) plateau-functies, waarbij alle preimage-sets (behalve één) dezelfde grootte hebben.
• De specifieke structuur van plateau-functies die monomiale vormen hebben ($x^d$) en hun gedrag als $d$-to-1 functies.

2. Methodologie

De auteurs gebruiken een spectrale benadering gebaseerd op de Walsh-transformatie om inzicht te krijgen in de combinatorische structuur van vectorele functies $F: \mathbb{F}_p^n \to \mathbb{F}_p^m$.

• Walsh-transformatie en Imbalans: De kern van de methode is het analyseren van de Walsh-coëfficiënten bij $a=0$. De auteurs definiëren een maat voor "imbalans" ($N_bF$), gebaseerd op de som van de kwadraten van de Walsh-coëfficiënten voor niet-nul componenten.
• Ongelijkheden voor Preimage-groottes: Door gebruik te maken van de Cauchy-Schwarz-ongelijkheid en de orthogonaliteit van karakters, leiden ze scherpe onder- en bovengrenzen af voor de grootte van preimage-sets ($|F^{-1}(\beta)|$) in termen van de imbalans en de grootte van het beeld ($|Im(F)|$).
• Karakterisering van "Bijna Gebalanceerd": Functies die de grenzen van deze ongelijkheden bereiken, worden gedefinieerd als "bijna gebalanceerd". De auteurs tonen aan dat dit concept direct gekoppeld kan worden aan de spectrale eigenschappen (de Walsh-coëfficiënten moeten constant zijn in grootte voor niet-nul componenten).
• Toepassing op Plateau-functies: Omdat plateau-functies per definitie een beperkt aantal waarden voor hun Walsh-coëfficiënten hebben (namelijk $0$ en $\pm p^{(n+t)/2}$), kunnen de algemene ongelijkheden worden verscherpt tot exacte voorwaarden voor het bestaan van bepaalde types functies.

3. Belangrijkste Bijdragen en Resultaten

A. Algemene Grenzen en Definities

• Stelling 3.3: De auteurs leiden nieuwe grenzen af voor de grootte van preimage-sets gebaseerd op de imbalans ($N_bF$) en de grootte van het beeld.
• Definitie 3.7: Een nieuwe definitie van "bijna gebalanceerde" functies wordt geïntroduceerd voor niet-surjectieve gevallen, gebaseerd op het bereiken van de bovengrens van de preimage-grootte.

B. Relatie tussen Imbalans en Walsh-transformatie

• Stelling 4.1: Voor surjectieve, bijna gebalanceerde functies wordt bewezen dat alle Walsh-coëfficiënten $W_F(b, 0)$ (voor $b \neq 0$) dezelfde absolute waarde moeten hebben. Dit leidt tot een directe relatie tussen de imbalans en de amplitude van de plateau-functie.
• Stelling 4.6: Het wordt aangetoond dat elke functie $F: \mathbb{F}_p^n \to \mathbb{F}_p^m$ met $m \leq n/2$ equivalent is aan een surjectieve functie (via een additieve verschuiving).

C. Plateau-functies die $d$-to-1 zijn

• Stelling 5.2: Dit is een van de belangrijkste resultaten. De auteurs bewijzen dat een plateau-functie die $d$-to-1 is (waarbij $d | (p^n-1)$ en $d > 2$), alleen kan bestaan als:
  • $n$ even is.
  • $d = p^t + 1$ voor een zekere $t \geq 1$ die $n/2$ deelt.
  • De functie bestaat uit een specifieke verdeling van gebogen componenten en componenten met amplitude $p^{n/2+t}$.
• Corollarium 5.4: Voor monomiale functies $F(x) = x^d$ geldt dat deze alleen plateau-functies kunnen zijn als ze permutaties zijn ($d=1$) of $(p^t+1)$-to-1 zijn.
• Stelling 5.5 & 5.6: Er worden scherpe ondergrenzen voor de differentiaaluniformiteit afgeleid. Een $(p^t+1)$-to-1 plateau-functie heeft een differentiaaluniformiteit van minstens $p^t$. Deze uniformiteit is exact $p^t$ dan en slechts dan als de functie differentieel 2-waardig is (d.w.z. de vergelijking $F(x+a)-F(x)=b$ heeft 0 of $p^t$ oplossingen).

D. Constructies van Bijna Gebalanceerde Functies

• Stelling 5.8: Een specifieke familie van monomiale functies $F(x) = Tr_{n/2}^n(x^{2r+1})$ wordt geanalyseerd en blijkt surjectief en bijna gebalanceerd te zijn met een specifieke verdeling van preimage-groottes.
• Propositie 5.9 & 5.10: Bestaande constructies van Maiorana-McFarland plateau-functies worden onderzocht. De auteurs tonen aan dat deze, onder bepaalde voorwaarden voor de gebruikte permutaties en functies, bijna gebalanceerd kunnen worden gemaakt.

E. Combinatorische Structuur van Plateau-APN Functies

• Propositie 6.3: Er worden onder- en bovengrenzen afgeleid voor de imbalans van plateau-APN functies. De ondergrens wordt bereikt als de functie een specifiek aantal gebogen componenten heeft; de bovengrens als er geen gebalanceerde componenten zijn.
• Stelling 6.7: Een belangrijk negatief resultaat: Er bestaan geen plateau-APN functies met de tweede mogelijke waardeverdeling voor functies met een minimaal beeld (zoals beschreven in eerdere literatuur). Dit sluit een klasse van mogelijke APN-functies uit binnen de plateau-functies.
• Stelling 6.8: Plateau-APN functies met een minimaal beeld kunnen geen enkele gebalanceerde componentfunctie hebben.

4. Betekenis en Impact

De resultaten van dit artikel hebben aanzienlijke implicaties voor de cryptanalyse en het ontwerp van cryptografische primitieven:

1. Beperking van Ontwerpruimte: De resultaten tonen aan dat plateau-functies met specifieke eigenschappen (zoals $d$-to-1 of monomiale vorm) zeer strikte voorwaarden moeten voldoen. Dit beperkt het aantal mogelijke kandidaten voor veilige cryptografische functies aanzienlijk.
2. Verband tussen Spectrale en Differentiële Eigenschappen: De paper legt een sterke, kwantitatieve link tussen de Walsh-transformatie (spectrale eigenschappen) en de differentiaaluniformiteit. Dit biedt nieuwe methoden om de veiligheid van functies te analyseren zonder alleen te vertrouwen op differentiaalanalyse.
3. Uitsluiting van Mogelijke APN-structuren: Door te bewijzen dat bepaalde waardeverdelingen onmogelijk zijn voor plateau-APN functies, helpt dit onderzoek bij het oplossen van het "Big APN" probleem (het bestaan van APN-permutaties in even dimensies) door de zoekruimte te verfijnen.
4. Praktische Toepassingen: De analyse van monomiale functies is direct relevant voor hash-functies die worden gebruikt in zero-knowledge bewijssystemen (zoals Poseidon en Rescue-Prime), aangezien deze vaak gebaseerd zijn op monomiale mappings.

Kortom, dit werk biedt een theoretisch raamwerk om de intrinsieke structuur van plateau-functies te begrijpen en stelt onderzoekers in staat om de bestaansvoorwaarden en veiligheidskarakteristieken van deze cruciale cryptografische bouwstenen nauwkeuriger te beoordelen.