Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers

Dit artikel bewijst dat asymptotisch bijna alle vectoriële functies over eindige velden triviale extended-affiene stabilisatoren hebben, wat impliceert dat het aantal equivalentieklassen overeenkomt met de ruwe schatting en dat het toevalsgewijs selecteren van cryptografische primitieven een veilige strategie is.

De kern

Stel je voor dat je een enorme bibliotheek bouwt, maar in plaats van boeken, bevat deze bibliotheek wiskundige functies. Deze functies zijn als de "geheime sleutels" of "geheime recepten" die computers gebruiken om informatie te versleutelen (zoals bij banktransacties of WhatsApp-berichten).

Deze paper van Keita Ishizuka gaat over een heel specifieke vraag: Hoe uniek zijn deze sleutels eigenlijk?

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. Het Probleem: De "Verkleedpartij" van de Wiskunde

In de cryptografie (het vakgebied van geheime codes) kijken we naar functies die getallen omzetten in andere getallen. Maar er is een trucje: twee functies kunnen er heel anders uitzien, maar eigenlijk precies hetzelfde doen.

Stel je voor dat je een recept hebt voor een taart.

• Recept A: "Meng bloem en suiker, bak op 180 graden."
• Recept B: "Meng suiker en bloem, bak op 180 graden."

Hoewel de volgorde van woorden anders is, is het resultaat exact hetzelfde. In de wiskunde noemen we dit EA-equivalentie (Extended-Affine equivalentie). Het betekent dat je de invoer en uitvoer van een functie kunt "verdraaien" (zoals het omdraaien van een taarttafel of het verwisselen van ingrediënten), en de functie blijft cryptografisch gezien hetzelfde.

De grote vraag voor de onderzoekers was: Als we willekeurig een nieuwe sleutel (functie) bedenken, is het dan waarschijnlijk dat we toevallig een sleutel vinden die al bestaat, maar dan net even anders verpakt?

2. De "Stabilisator": De Spiegel van de Functie

Om dit te begrijpen, introduceert de auteur het concept van een stabilisator.

Stel je een functie voor als een uniek kunstwerk, bijvoorbeeld een schilderij.

• Een triviale stabilisator betekent: "Als ik dit schilderij draai, spiegelen of verkleuren, ziet het er anders uit. Het is uniek."
• Een niet-triviale stabilisator betekent: "Als ik dit schilderij 180 graden draai, ziet het er precies hetzelfde uit!" (Net als een symmetrisch vlinder of een vierkant).

In de wiskundige wereld betekent een "niet-triviale stabilisator" dat de functie een soort symmetrie heeft. Als je de invoer en uitvoer op een bepaalde manier verandert, blijft de functie ongewijzigd. Dit is voor cryptografen vaak onhandig, omdat het betekent dat de functie minder "chaotisch" en dus minder veilig kan zijn.

3. De Grote Ontdekking: "Bijna Alles is Uniek"

De kernboodschap van dit paper is verrassend simpel, maar enorm belangrijk:

Bijna alle willekeurige functies hebben geen symmetrie.

De auteur bewijst dat als je een functie volledig willekeurig kiest uit de oneindig grote bibliotheek van alle mogelijke functies:

1. De kans dat deze functie een "spiegelbeeld" heeft (een niet-triviale stabilisator) is onvoorstelbaar klein.
2. Het is alsof je in een zaal staat met biljoenen mensen en je vraagt: "Wie heeft een perfecte spiegelbeeld-gezicht?" De kans is zo klein dat je kunt zeggen: "Niemand."

De paper laat zien dat functies met symmetrie (niet-triviale stabilisatoren) een exponentieel zeldzame groep zijn. Ze zijn als een naald in een hooiberg, maar dan zo klein dat je de hooiberg niet eens kunt vinden.

4. Wat betekent dit voor de praktijk?

Dit heeft twee enorme gevolgen voor mensen die beveiligingssystemen bouwen:

A. Het tellen van unieke sleutels (Classificatie)
Vroeger was het moeilijk om te zeggen hoeveel echt unieke functies er zijn. Je wist niet of je 1000 functies telde, of dat 900 daarvan eigenlijk hetzelfde waren, alleen anders verpakt.

• De nieuwe regel: Omdat bijna alle functies uniek zijn (geen symmetrie), kun je nu heel simpel tellen:

  Totaal aantal functies gedeeld door het aantal manieren om ze te verdraaien = Het aantal unieke sleutels.
  De "foutmarge" is zo klein dat hij verdwijnt. Het is alsof je zegt: "Als je 1 miljard mensen hebt en 1000 manieren om ze te groeperen, zijn er ongeveer 1 miljoen unieke groepen."

B. Willekeurig zoeken is veilig (Random Sampling)
Veel cryptografen proberen nieuwe, sterke sleutels te vinden door willekeurig functies te genereren (random sampling).

• De angst: "Zal ik per ongeluk een sleutel genereren die ik al heb, maar dan net even anders verpakt? Dan verspil ik tijd."
• De zekerheid: De paper zegt: Nee, dat hoeft je niet te maken. De kans dat twee willekeurig gekozen functies "verwant" zijn (EA-equivalent) is zo klein dat het statistisch onmogelijk lijkt.
  • Vergelijking: Het is alsof je twee mensen uit de hele wereld kiest en vraagt of ze exact dezelfde vingerafdruk hebben. De kans is nul. Je kunt dus gerust willekeurig zoeken; je zult bijna nooit op een "dubbel" stuiten.

Samenvatting in één zin

Dit paper bewijst dat in de wereld van cryptografische functies, symmetrie een uiterst zeldzame ziekte is; bijna elke willekeurig gekozen functie is uniek, waardoor het veilig en efficiënt is om nieuwe beveiligingssystemen te ontwerpen door gewoon willekeurig te "gokken".

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers" van Keita Ishizuka, geschreven in het Nederlands.

Titel: Bijna alle vectoriële functies hebben triviale uitgebreid-affiene stabilisatoren

1. Probleemstelling en Context

Vectoriële Boolese functies (afbeeldingen van $\mathbb{F}_q^n$ naar $\mathbb{F}_q^m$) spelen een centrale rol in de symmetrische cryptografie, bijvoorbeeld als S-blokken in blokchiffers en hash-functies. De classificatie van deze functies gebeurt vaak modulo equivalentierelaties die belangrijke cryptografische eigenschappen behouden, zoals differentiaaluniformiteit, het Walsh-spectrum en de algebraïsche graad.

De twee belangrijkste equivalentierelaties zijn:

• EA-equivalentie (Extended-Affine): Behoudt de meeste cryptografische eigenschappen en is gedefinieerd door conjugatie met affiene permutaties op het domein en de range.
• CCZ-equivalentie: Een bredere relatie die EA-equivalentie omvat, gedefinieerd via affiene equivalentie van de grafieken van de functies.

Twee fundamentele vragen in dit domein blijven vaak onbeantwoord of moeilijk te kwantificeren:

1. Classificatie: Hoeveel EA-equivalentieklassen bestaan er eigenlijk? Het tellen van deze klassen is cruciaal om de diversiteit van cryptografische primitieven te begrijpen.
2. Willekeurige steekproeven: Bij het zoeken naar functies met specifieke eigenschappen via willekeurige generatie, is er dan een risico dat men herhaaldelijk EA-equivalente functies vindt? Beperken "botsingen" (collisions) de efficiëntie van het zoeken in de ruimte van equivalentieklassen?

Beide vragen hangen direct samen met de structuur van de EA-stabilisator van een functie. De stabilisator is de groep van affiene permutaties die de functie invariant laten. Volgens de orbit-stabilisatorstelling is de grootte van een equivalentieklasse omgekeerd evenredig met de grootte van de stabilisator. Als stabilisatoren triviaal zijn (alleen de identiteit), zijn de klassen maximaal groot en is het aantal klassen gelijk aan het totale aantal functies gedeeld door de grootte van de groep.

2. Methodologie

De auteur hanteert een probabilistische en combinatorische aanpak om de verdeling van stabilisatoren in de ruimte van alle vectoriële functies te analyseren.

• Groepsacties en Orbit-Stabilisator: Het artikel maakt gebruik van de theorie van groepenacties. De EA-groep $\Gamma = \text{AGL}(U) \times \text{AGL}(W)$ werkt op de verzameling functies $\mathcal{F}$.
• Brandpuntanalyse (Fixed-Point Analysis): De kern van de bewijsvoering ligt in het afleiden van een bovengrens voor het aantal functies dat gefixeerd wordt door een niet-triviale element $g$ van de groep $\Gamma$ (d.w.z. $g \cdot F = F$).
  • De auteur analyseert de structuur van affiene permutaties en toont aan dat de verzameling van vaste punten van een niet-triviale affiene permutatie een affiene deelruimte is met dimensie ten hoogste $n-1$.
  • Door de cyclusstructuur van de permutaties te gebruiken, wordt bewezen dat het aantal functies dat invariant is onder een niet-triviale $g$ exponentieel kleiner is dan het totale aantal functies.
• Unie-bounds (Union Bound): Door de kans te berekenen dat een willekeurige functie een niet-triviale stabilisator heeft, wordt de unie-bounds toegepast over alle niet-triviale elementen van de groep. Dit levert een bovengrens op voor de totale kans op een niet-triviale stabilisator.
• Asymptotische Analyse: De resultaten worden geëvalueerd voor grote dimensies $n$ en $m$, waarbij de groei van de groepsgrootte wordt vergeleken met de groei van de functieruimte ($q^{m \cdot q^n}$).

3. Belangrijkste Bijdragen en Resultaten

A. Hoofdstelling: Triviale Stabilisatoren (Theorema 3.4)
De auteur bewijst dat voor een uniform willekeurige vectoriële functie $F: \mathbb{F}_q^n \to \mathbb{F}_q^m$, de kans dat de EA-stabilisator niet triviaal is, super-exponentieel afneemt.

• Formeel: $P(\text{Stab}_\Gamma(F) \neq \{\text{id}\}) \leq q^{-\Omega(m q^n)}$.
• Dit betekent dat functies met een niet-triviale EA-stabilisator een exponentieel zeldzame deelverzameling vormen. Voor cryptografisch relevante parameters (bijv. 8-bit S-blokken) is deze kans verwaarloosbaar klein (bijv. $\leq 2^{-368}$).

B. Tellen van Equivalentieklassen (Corollary 3.7)
Als gevolg van de trivialiteit van de stabilisatoren, is het aantal EA-equivalentieklassen asymptotisch gelijk aan de "naive schatting":
$$|\mathcal{F}/\Gamma| \sim \frac{|\mathcal{F}|}{|\Gamma|}$$
De relatieve fout tussen het werkelijke aantal klassen en deze schatting gaat naar nul ($o(1)$) naarmate de dimensie toeneemt. Dit bevestigt dat de EA-groepsactie asymptotisch vrij is.

C. Kansen op Botsingen (Proposition 3.8 & Corollary 3.9)

• EA-equivalentie: De auteur leidt een scherpe bovengrens af voor de kans dat twee onafhankelijk gekozen functies EA-equivalent zijn. Door de trivialiteit van de stabilisatoren te combineren met de orbit-stabilisatorstelling, wordt aangetoond dat deze kans asymptotisch gelijk is aan de bovengrens:
  $$P(F \sim_{EA} G) = \frac{|\Gamma|}{|\mathcal{F}|} (1 + o(1))$$
  Dit is een super-exponentieel kleine kans.
• CCZ-equivalentie: Er worden ook bovengrenzen afgeleid voor CCZ-equivalentie, hoewel de vraag of de meeste functies ook triviale CCZ-stabilisatoren hebben, nog openstaat.

4. Voorbeeld en Cryptografische Implicaties

De auteur illustreert de resultaten met concrete parameters voor symmetrische cryptografie ($q=2$):

• 4-bit S-blokken: De asymptotische benadering is nog niet volledig geldig omdat de functieruimte niet groot genoeg is ten opzichte van de groep.
• 8-bit S-blokken (AES-regime): De kans op een niet-triviale stabilisator is $\leq 2^{-368}$. De botsingskans voor EA-equivalentie is ongeveer $2^{-1900}$.

Significantie voor Cryptografie:

1. Validatie van Willekeurige Zoekstrategieën: De resultaten bevestigen dat het willekeurig genereren van functies een effectieve strategie is voor het vinden van cryptografisch sterke primitieven (zoals APN of AB-functies). Onderzoekers hoeven zich geen zorgen te maken over redundantie door EA-equivalentie; de kans dat twee willekeurig gegenereerde functies equivalent zijn, is verwaarloosbaar.
2. Structuur van de Functieruimte: Het toont aan dat de ruimte van vectoriële functies gedomineerd wordt door functies met triviale stabilisatoren. Functies met extra symmetrieën (niet-triviale stabilisatoren) zijn uiterst zeldzaam.
3. Theoretische Basis: Het werk verenigt eerdere resultaten over het tellen van klassen (via Burnside's lemma) met een fundamenteel structureel inzicht: de "naive" telling is correct omdat stabilisatoren bijna altijd triviaal zijn.

5. Conclusie

Het artikel lost de fundamentele vragen over de classificatie en het willekeurige zoeken naar vectoriële functies op. Het bewijst dat voor bijna alle functies de EA-stabilisator triviaal is, wat leidt tot een exacte asymptotische formule voor het aantal klassen en een super-exponentieel lage botsingskans. Dit onderbouwt theoretisch de praktijk van het gebruik van willekeurige steekproeven in het ontwerp van cryptografische primitieven. De vraag of een analoog resultaat geldt voor de bredere CCZ-equivalentie blijft een open probleem voor toekomstig onderzoek.