Triprojective almost perfect nonlinear permutations and functions

Technische Samenvatting: Triprojectieve Bijna Perfect Niet-Lineaire Permutaties en Functies

Probleemstelling
Het artikel behandelt het bestaan en de constructie van Bijna Perfect Niet-Lineaire (APN) permutaties over eindige vectorruimten met een even dimensie. In de context van differentiaalcryptografie zijn APN-functies (die een differentieel uniformiteit $\Delta_F = 2$ hebben) cruciaal voor het ontwerpen van veilige S-blokken in substitutie-permutatienetwerken. Hoewel bekend is dat APN-functies bestaan voor oneven dimensies, blijft het bestaan van APN-permutaties (bijecties) voor even dimensies $n > 6$ een groot open probleem. De auteurs richten zich specifiek op het construeren van grote families van dergelijke functies in dimensies $n = 3m$ (waarbij $m$ oneven is) en het karakteriseren van hun eigenschappen, waaronder hun equivalentieklassen en de grootte van hun beeldverzamelingen.

Methodologie
De auteurs hanteren een structurele aanpak gebaseerd op "triprojectieve" en "semi-kwadratische" afbeeldingen. De methodologie verloopt via de volgende stappen:

1. Projectieve Structuur: De auteurs definiëren een klasse van functies $F \in SQH(3, q)$ (semi-kwadratisch homogeen) over $\mathbb{F}_q^3$ (waarbij $q=2^m$). Deze functies worden geïnduceerd door semi-kwadratische vormen die specifieke homogeniteitseigenschappen voldoen, waardoor ze goed gedefinieerde afbeeldingen op de projectieve ruimte $\mathbb{P}^2(\mathbb{F}_q)$ kunnen induceren.
2. Bijjectiecriteria: Gebaseerd op eerder werk (Stelling 1.2) maakt het artikel gebruik van een voorwaarde voor een specifieke univariate polynoom $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ om te garanderen dat de geïnduceerde afbeelding op de projectieve ruimte een bijjectie is.
3. Analyse van Differentieel Uniformiteit:
   • Geval $m/d$ is even: De auteurs maken gebruik van het concept van de "core" van de functie (een deellichaam waarover de afgeleide afbeelding lineair is) om aan te tonen dat de differentieel uniformiteit $2d$ is, waarbij $d = \gcd(k, m)$.
   • Geval $m/d$ is oneven: De auteurs introduceren hulpmiddelen uit de theorie van gedraaide polynoomringen (Ore-ringen) $\mathbb{F}_q[t; \sigma]$. Zij leggen een verband tussen de nulpunten van de polynoom $P(X)$ en het bestaan van lineaire rechterdelers in de gedraaide ring. Door het lichaam uit te breiden en de kleinste gemeenschappelijke linkervel (lclm) van polynomen te analyseren, bewijzen zij dat de differentieel uniformiteit ook in dit complexere geval $2d$ blijft.
4. Equivalentie en Classificatie: Het artikel vergelijkt de nieuwe familie met bestaande trivariate APN-functies (specifiek die van Li-Kaleyski en Bartoli-Stanica) aan de hand van lineaire equivalentie. Bovendien wordt ongelijkwaardigheid met Gold APN-functies ($x^{2^i+1}$) bewezen door de lineaire automorfismegroepen ($Aut_L(F)$) te analyseren en aan te tonen dat deze niet geconjugeerd kunnen zijn in de generale lineaire groep.

Belangrijkste Bijdragen en Resultaten

• Constructie van APN-permutaties: Het artikel presenteert een grote familie van APN-permutaties voor eindige vectorruimten met dimensie $n=3m$ waarbij $m$ oneven is. De functies zijn gedefinieerd als:
  $$F(x, y, z) = (x^{\sigma+1} + ay^\sigma z + bx^\sigma y + cx^\sigma z, \quad ay^{\sigma+1} + z^\sigma x + bz^\sigma y + cx^\sigma y, \quad z^{\sigma+1} + x^\sigma y)$$
  waarbij $\sigma = 2^k$, $a, b, c \in \mathbb{F}_q$, en $a \neq 0$.
• Differentieel Uniformiteit: De auteurs bewijzen dat, als de polynoomvergelijking $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$ geen oplossing heeft in $\mathbb{F}_q$, de differentieel uniformiteit van $F$ gelijk is aan $2d$ (waarbij $d = \gcd(k, m)$). Bijgevolg is $F$ een APN-permutatie wanneer $d=1$ en $m$ oneven is.
• Grootte van de Beeldverzameling: Het artikel karakteriseert de grootte van de beeldverzameling van deze functies. Als $m/d$ even is, is de functie $(2d+1)$-tot-één op $\mathbb{F}_q^3 \setminus \{0\}$. Als $m/d$ oneven is, is de functie bijectief op $\mathbb{F}_q^3$.
• Unificatie van Bestaande Families: De auteurs tonen aan dat verschillende recent ontdekte families van trivariate APN-functies (Li-Kaleyski en Bartoli-Stanica) lineair equivalent zijn aan specifieke instanties van hun voorgestelde familie (verkregen door specifieke parameters $a, b, c$ in te stellen). Dit biedt een verenigde, elementaire verklaring voor deze constructies, waardoor de complexe gevalonderscheidingen en door computers ondersteunde resultaatberekeningen uit eerdere bewijzen worden vermeden.
• Ongelijkwaardigheid met Gold-functies: Het artikel bewijst dat voor $m > 2$ en $m \neq 6$ de geconstrueerde APN-functies CCZ-ongelijkwaardig zijn aan Gold APN-functies. Dit wordt vastgesteld door aan te tonen dat hun lineaire automorfismegroepen niet geconjugeerd zijn in $GL(3m, 2)$.

Betekenis en Aanspraken
Het artikel claimt een "grote familie" van APN-permutaties te leveren in elke oneven dimensie die deelbaar is door drie, waarmee het open vraagstuk van APN-bijjecties voor even dimensies wordt aangepakt. De betekenis ligt in:

1. Generaliteit: De constructie levert bewijsbaar exponentieel veel paarsgewijs ongelijkwaardige APN-functies op binnen de klasse van multiprojectieve afbeeldingen.
2. Vereenvoudiging: De bewijzen worden beschreven als "zonder computer, veel korter en puur elementair" in vergelijking met eerdere werken, en bieden een verenigd kader voor het begrijpen van diverse trivariate APN-functies.
3. Nieuwe Voorbeelden: De familie blijkt voorbeelden te bevatten die ongelijkwaardig zijn aan bekende APN-functies (inclusief Gold-functies), waardoor het bekende landschap van cryptografische primitieven wordt uitgebreid.

De auteurs merken op dat hoewel de Walsh-spectra bekend zijn voor het geval waarin $m/d$ even is, het bepalen van het Walsh-spectrum voor de APN-permutaties (waarbij $m$ oneven is) een open probleem blijft. Zij identificeren de classificatie van semi-kwadratische homogene functies die leiden tot projectieve bijjecties als een natuurlijke richting voor toekomstig onderzoek.