On the Walsh spectra of quadratic APN functions

Technische Samenvatting: Over de Walsh-spectra van kwadratische APN-functies

Probleemstelling
Bijna Perfect Niet-Lineaire (APN) functies zijn kritieke componenten in symmetrische cryptosystemen en bieden optimale weerstand tegen differentiaal-aanvallen. Een fundamentele eigenschap van deze functies is hun lineariteit, die wordt bepaald door hun Walsh-spectrum. Hoewel de amplitudeverdeling (en dus het Walsh-spectrum) van kwadratische APN-functies volledig is gekarakteriseerd voor oneven dimensies $n$, blijft het geval voor even $n$ grotendeels open. De enige bekende algemene beperking voor even $n$ is afgeleid uit de vierde moment van de Walsh-transformatie. Dit artikel adresseert het gat in het begrip van de mogelijke Walsh-spectra van kwadratische APN-functies $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ waarbij $n$ even is, met name door te streven naar het afleiden van sterkere voorwaarden voor hun amplitudeverdelingen.

Methodologie
De auteurs leggen twee nieuwe geometrische verbanden tussen kwadratische APN-functies en eindige meetkunde:

1. Vectorruimte-partities: Het artikel demonstreert dat de amplitudeverdeling van een kwadratische APN-functie uniek correspondeert met een vectorruimte-partitie van de omringende ruimte $\mathbb{F}_2^n$. Specifiek worden de niet-triviale niet-bent componentfuncties van $F$ geassocieerd met deelruimten in een partitie, waarbij de dimensie van elke deelruimte direct gekoppeld is aan de amplitude van de corresponderende componentfunctie.
2. Blokkerende verzamelingen: De verzameling van niet-triviale niet-bent componenten, aangeduid als $N_F$, blijkt een specifiek type blokkerende verzameling te vormen in de projectieve ruimte $PG(n-1, 2). Cruciaal bewijzen de auteurs dat de doorsnede van $N_F$ met elke deelruimte van dimensie $n/2$ een oneven aantal punten moet bevatten.

Door gebruik te maken van gevestigde stellingen over vectorruimte-partities en blokkerende verzamelingen (specifiek resultaten betreffende "staarten" van partities en minimale blokkerende verzamelingen), vertalen de auteurs deze geometrische beperkingen naar algebraïsche grenzen voor de amplitudeverdelingen van kwadratische APN-functies.

Belangrijkste Bijdragen en Resultaten

• Verband met Vectorruimte-partities (Sectie II):

  • Stelling II.4 stelt dat als een componentfunctie $F_b$ een amplitude van $2^{(n+k)/2}$ heeft, deze correspondeert met een deelruimte van dimensie $k$ in een vectorruimte-partitie van $\mathbb{F}_2^n$.
  • Dit verband maakt het toepassen van pakkingcondities en dimensiegrenzen uit de partitietheorie mogelijk.
  • Stelling II.10: Een kwadratische APN-functie kan hoogstens één componentfunctie hebben met een amplitude groter dan $2^{3n/4}$. Als zo'n component bestaat, moeten alle andere een amplitude hebben van ten hoogste $2^{(2n-l)/2}$, waarbij $l$ de exponent is van de maximale amplitude.
  • Proposities II.14–II.16: Nieuwe ondergrenzen voor het aantal niet-bent componenten ($|N_F|$) worden afgeleid op basis van de lineariteit en de aanwezigheid van specifieke amplitudes.

• Verband met Blokkerende Verzamelingen (Sectie III):

  • Corollarium III.3: De verzameling $N_F$ is een blokkerende verzameling in $PG(n-1, 2)$ met betrekking tot $(n/2)$-ruimten, met het extra kenmerk dat elke dergelijke ruimte $N_F$ snijdt in een oneven aantal punten.
  • Stelling III.9: Dit is de eerste niet-triviale, algemene bovengrens voor het aantal bent componentfuncties voor een kwadratische APN-functie. Specifiek geldt voor $n \ge 6$ dat het aantal niet-bent componenten voldoet aan $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$. Gelijkheid is alleen mogelijk als $n=8$. Bijgevolg is het aantal bent componenten ten hoogste $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$.

• Synthese en Dimensionale Analyse (Sectie IV):

  • Door de beperkingen van partities en blokkerende verzamelingen te combineren, elimineren de auteurs verschillende theoretisch mogelijke amplitudeverdelingen.
  • Stelling IV.1: Vectorruimte-partities van het type $[(n/2)^{2^{n/2+1}}]$ (een $(n/2)$-spreiding) corresponderen met geen enkele kwadratische APN-functie.
  • Stelling IV.5: Voor $n=8** beperkt het artikel de mogelijke amplitudeverdelingen tot een specifieke lijst (exclusief de triviale partitie en de 4-spreiding), waardoor het aantal potentiële uitgebreide Walsh-spectra wordt teruggebracht tot maximaal 18 onderscheiden types.
  • Propositie IV.4: Het artikel vergelijkt de sterkte van de afgeleide ondergrenzen voor $|N_F|$ over verschillende parameterbereiken, en identificeert welke grens dominant is afhankelijk van de lineariteit van de functie.

• Equivalentie en Permutaties (Sectie V):

  • Het artikel analyseert hoe deze structuren zich gedragen onder EA-equivalentie en CCZ-equivalentie.
  • Corollarium V.6: Als een kwadratische APN-functie CCZ-equivalent is aan een permutatie, kan deze niet weinig niet-bent componenten hebben; specifiek geldt $|N_F| \ge 3(2^{n/2}-1)$, en moet $N_F$ een 3-voudige blokkerende verzameling zijn.

Betekenis en Beweringen
Het artikel claimt de eerste algemene voorwaarden te bieden voor de Walsh-spectra van kwadratische APN-functies, verder dan de bekende vierde-momentgrens. Door de algebraïsche eigenschappen van deze functies te koppelen aan de combinatorische structuren van vectorruimte-partities en blokkerende verzamelingen, leiden de auteurs sterke beperkingen af voor de mogelijke amplitudeverdelingen.

De auteurs stellen expliciet dat hun resultaten:

1. Bewijzen dat een kwadratische APN-functie hoogstens één component kan hebben met een amplitude groter dan $2^{3n/4}$.
2. De eerste niet-triviale bovengrens bieden voor het aantal bent componenten.
3. Voorwaarden bieden om te bepalen of een functie CCZ-equivalent is aan een permutatie op basis van het aantal bent componenten.
4. Systematisch alle mogelijke amplitudeverdelingen lijsten voor kleine even dimensies (specifiek $n=6, 8, 10$), met een nadruk op welke worden gerealiseerd en welke open problemen blijven.

Het artikel sluit af met een lijst van open problemen, waaronder het bestaan van APN-functies met specifieke amplitudeverdelingen in dimensie 8 en de zoektocht naar oneindige families van kwadratische APN-functies met niet-klassieke Walsh-spectra. De auteurs behouden een bescheiden toon, en merken op dat hoewel ze veel mogelijkheden hebben uitgesloten, de volledige classificatie van Walsh-spectra voor kwadratische APN-functies een open uitdaging blijft.