Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

Technische Samenvatting: Kwadratische APN-functies in Dimensie 8 via Gröbner-basis Zoektocht in een Zelf-equivalentie Subruimte

Probleemstelling
De classificatie van Almost Perfect Nonlinear (APN) functies over $\mathbb{F}_{2^n}$ tot CCZ-equivalentie is een centraal probleem in de cryptografie, in het bijzonder voor $n=8$. Terwijl de classificatie compleet is voor $n \leq 6$, blijft deze voor $n=8$ slechts gedeeltelijk. De zoekruimte voor kwadratische APN-functies is enorm ($2^{224}$ mogelijke coëfficiëntvectoren), waardoor een globale willekeurige zoektocht onhaalbaar is vanwege een geschatte APN-dichtheid van $\approx 2^{-n}$. Eerdere systematische inspanningen, zoals de recursieve boomzoektocht door Beierle, Brinkmann en Leander (BBL2021), verkenden gestructureerde algebraïsche subruimten gedefinieerd door zelf-equivalentie beperkingen. Specifiek rapporteerde BBL2021 het vinden van nul APN-functies binnen de 40-dimensionale zelf-equivalentie subruimte $V_A$ geassocieerd met een lineaire automorfisme $A$ van orde 5 (klasse-index 22). Dit artikel onderzoekt of deze subruimte werkelijk geen APN-functies bevat of dat de vorige zoekmethode er niet in geslaagd is deze te lokaliseren.

Methodologie
De auteurs stellen een tweefasige computationele pijplijn voor die willekeurige bemonstering combineert met algebraïsche enumeratie om $V_A$ effectiever te verkennen dan de vorige boomzoektocht.

1. Fase 1: Willekeurige Bemonstering via RREF-Parametrisatie
   De auteurs construeren een expliciete Reduced Row Echelon Form (RREF) parametrisatie van de 40-dimensionale subruimte $V_A = \{F : F \circ A = A \circ F\}$. Dit reduceert de zoekruimte van $2^{224}$ naar $2^{40}$. Binnen deze subruimte wordt de empirische dichtheid van APN-functies gevonden als ongeveer $10^{-4}$ (ongeveer 1 APN-functie per 11.000 willekeurige monsters), wat gerichte bemonstering haalbaar maakt. De auteurs voeren willekeurige bemonstering uit om "APN-centra" te identificeren (functies in $V_A$ die APN zijn).

2. Fase 2: Gröbner-basis Slice-berekening
   Voor elk APN-centrum gevonden in Fase 1, definiëren de auteurs een 24-dimensionale affiene hypervlak (een "NL=4 slice") dat door dat centrum loopt. Dit wordt bereikt door 200 van de 224 Algebraic Normal Form (ANF) coëfficiënten (specifiek die corresponderend met paren met indices $p \leq 4$) vast te zetten op de waarden van het centrum, waarbij 24 coëfficiënten als onbekenden worden achtergelaten.
   De APN-conditie voor de 255 niet-nul verschillen wordt gecodeerd als een systeem van polynoomvergelijkingen over de Booleaanse ring. De auteurs gebruiken het Magma computer algebra systeem om een Gröbner-basis voor dit systeem te berekenen.

   • Als het systeem onhaalbaar is, bevat de slice geen andere APN-functies.
   • Als het systeem oplossingen heeft, vindt de Gröbner-basis enumeratie alle APN-functies binnen die specifieke 24-dimensionale hypervlak.
     Cruciaal is dat hoewel het centrum gegarandeerd in $V_A$ ligt, de door de Gröbner-basis stap gevonden oplossingen niet beperkt zijn tot $V_A$; ze kunnen buiten de zelf-equivalentie subruimte liggen.

3. Classificatie en Verificatie
   Gevonden functies worden geclassificeerd met behulp van de ortho-afgeleide invariant $\sigma(F)$, die bewezen is een volledige CCZ-invariant te zijn voor kwadratische APN-functies (door de stelling van Yoshiara en resultaten van Canteaut et al.). De auteurs voeren streaming-vergelijkingen uit van deze signaturen tegen drie belangrijke databases: de BBL2021 pre-2020 compilatie, de Beierle et al. 2025 database (bevattende $\approx 3,8$ miljoen functies), en de klassieke Gold-functies.

Belangrijkste Resultaten
De auteurs voerden de pijplijn uit op 428 verschillende 24-dimensionale slices (0,65% van de totale $2^{16}$ mogelijke slices in $V_A$).

• Ontdekking van Nieuwe Klassen: De zoektocht leverde 566 unieke kwadratische APN-functies op die vallen onder zes CCZ-equivalentie klassen.
  • Vier Nieuwe Klassen (A, B, C, D): Deze 500 functies (362 in Klasse A, 72 in B, 36 in C, 30 in D) zijn niet aanwezig in de Beierle 2025 database, de BBL2021 pre-2020 database, of de klassieke Gold-families.
  • Twee Bekende Klassen (E, F): Deze komen overeen met de Gold-functies $x^3$ en $x^9$ (en hun Frobenius-banen), dienend als controles om de pijplijn te valideren.
• Structurele Bevindingen:
  • Subruimte Lidmaatschap: Een lidmaatschapstest ($F \circ A = A \circ F$) onthulde dat Klasse A, E en F volledig binnen $V_A$ liggen. Echter, Klassen B, C en D liggen volledig buiten $V_A$.
  • Het "Gateway" Fenomeen: De 138 functies in de nieuwe externe klassen (B, C, D) werden uitsluitend gevonden in slices gecentreerd op Gold-functies (Klassen E en F) die binnen $V_A$ liggen. Slices gecentreerd op Klasse A-functies leverden geen buren buiten $V_A$ op.
  • Falende Alternatieve Seeds: Vergelijkende experimenten met 532 APN-functies uit de Beierle 2025 database (die buiten $V_A$ liggen) als slice-centra resulteerden in nul gevonden APN-buren. Dit suggereert dat de "gateway"-capaciteit om nieuwe klassen te ontdekken via Gröbner-basis slicing specifiek is voor functies binnen de zelf-equivalentie subruimte, en niet een generiek eigenschap is van alle APN-functies.

Betekenis en Claims
Het artikel claimt enkele significante bijdragen aan het veld van de classificatie van kwadratische APN-functies:

1. Correctie van Vorige Resultaten: De auteurs demonstreren dat de zelf-equivalentie subruimte $V_A$ (klasse-index 22), die eerder door BBL2021 als bevattend nul APN-functies werd gerapporteerd, in feite ten minste vier kwadratische APN CCZ-klassen bevat. Het falen van de BBL2021 boomzoektocht wordt toegeschreven aan de branch-pruning strategie, die mogelijk geldige oplossingen in deze gestructureerde subruimte heeft geëlimineerd, terwijl de Gröbner-basis benadering een volledige enumeratie binnen elke slice uitvoert.
2. Ontdekking van Nieuwe Functies: Het artikel levert een rigoureus bewijs (via de ortho-afgeleide invariant) dat vier nieuwe kwadratische APN CCZ-klassen bestaan voor $n=8$, verschillend van de $\approx 3,8$ miljoen functies in de grootste bekende database.
3. Methodologische Innovatie: Het introduceert een "GB-navigatie" mechanisme. Het stelt dat men, hoewel een globale zoektocht onmogelijk is, gestructureerde subruimten met een hogere APN-dichtheid kan exploiteren om "seed" functies te vinden. De Gröbner-basis stap fungeert dan als een lokale enumerator, in staat om buiten de subruimte te treden om nieuwe klassen te vinden. De auteurs benadrukken dat dit mechanisme niet generiek is; het is afhankelijk van de specifieke algebraïsche structuur van de zelf-equivalentie subruimte, zoals bewezen door het falen van niet-subruimte functies om productieve seeds te zijn.
4. Volledigheid van de Ortho-Afgeleide: Het werk versterkt het nut van de ortho-afgeleide signature als een exacte CCZ-invariant voor kwadratische functies, wat rigoureuze classificatie mogelijk maakt zonder uitputtende pairwise testen.

De auteurs concluderen dat hun benadering een systematisch programma biedt voor het uitbreiden van de classificatie van kwadratische APN-functies door andere BBL2021 klasse-indices te verkennen en de Gröbner-basis slicing techniek te gebruiken om door het APN-landschap te navigeren.