🔢 wiskunde

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

Dit artikel introduceert de D-klasse van permutaties over $\mathbb{F}_{2^{n+1}}$ om volledige permutaties via lokale conjugaties te karakteriseren en te construeren, waarbij de algebraïsche eigenschappen, cryptografische grenzen en CCZ-inequivalentie worden vastgesteld terwijl algoritmen worden gepresenteerd die succesvol nieuwe $\delta=4$ volledige permutaties enumereren.

Oorspronkelijke auteurs: Li Shuai

Gepubliceerd 2026-10-16

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Li Shuai

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In de verborgen architectuur van de moderne digitale beveiliging bestaat een klasse wiskundige objecten die bekend staan als complete permutaties. Dit zijn niet louter willekeurige verschuivingen van getallen; het zijn hooggestructureerde herschikkingen waarbij de handeling van het verplaatsen van een item naar een nieuwe positie en de handeling van het verplaatsen naar een positie die de som is van de oude en nieuwe locatie, beide resulteren in een perfecte, niet-overlappende orde. Aan deze dubbele vereiste wordt voldaan door de vormgeving van substitutieboxen, of S-boxen, die de primaire componenten zijn in encryptiesystemen die gegevens versleutelen om hun betekenis te verbergen. Als deze componenten te voorspelbaar zijn, kan de encryptie worden gekraakt; als ze te chaotisch zijn, worden ze inefficiënt. De uitdaging voor cryptografen is lang geweest om het ideale evenwicht te vinden: permutaties die complex genoeg zijn om geavanceerde aanvallen te weerstaan, maar gestructureerd genoeg om snel geïmplementeerd te kunnen worden.

Een recente studie door Li Shuai van de Ningxia Universiteit pakt deze uitdaging aan door een specifieke familie van deze permutaties te verkennen door de lens van geometrische symmetrie. Het onderzoek richt zich op een eigenschap genaamd "lokale kromheid" (local crookedness), die beschrijft hoe een permutatie zich gedraagt wanneer de invoer met een specifieke hoeveelheid wordt verschoven. De auteur introduceert een nieuwe categorie van deze functies, gedefinieerd door een specifiek patroon in hoe hun outputs veranderen. Door deze functies te behandelen als elementen van een grotere groep die getransformeerd kan worden door het verschuiven, roteren of verwisselen van specifieke delen van de data, brengt de studie een landschap van mogelijkheden in kaart. Het doel was om te zien of beweging binnen dit landschap nieuwe, superieure permutaties kon genereren die betere bescherming bieden tegen differentiële cryptanalyse, een methode waarbij aanvallers bestuderen hoe kleine veranderingen in de invoer de uitvoer beïnvloeden om de geheime sleutel af te leiden.

De kern van het werk betreft een constructieketen die begint met een bekende, goed gedragende permutatie en een reeks precieze algebraïsche operaties toepast om nieuwe te creëren. De auteur definieert een specifieke set regels, of een "D-klasse", die deze permutaties moeten volgen om geldig te blijven. Binnen deze set bewijst de onderzoeker dat de collectie van "gelifte" (lifted) permutaties — die zijn uitgebreid van een kleinere ruimte naar een grotere ruimte — een unieke rigiditeit bezit. Als men probeert een enkele permutatie te veranderen met slechts één type operatie, zoals een eenvoudige verschuiving of een lineaire rotatie, faalt het resultaat meestal om een geldige complete permutatie te blijven. Echter, de studie demonstreert dat het combineren van twee verschillende operaties in een specifieke sequentie deze rigiditeit doorbreekt. Deze combinatie stelt de onderzoeker in staat om door de ruimte van mogelijkheden te navigeren, waarbij men van de ene geldige permutatie naar de andere beweegt zonder de essentiële eigenschappen die vereist zijn voor beveiliging te verliezen.

Om dit theoretische kader praktisch te maken, ontwikkelt het artikel twee verschillende algoritmen. Het eerste is een backtracking-zoekalgoritme dat vanaf nul een complete permutatie opbouwt, waarbij op elke stap wordt gewaarborgd dat aan de dubbele ordeningseisen wordt voldaan. Het tweede is een "greedy" lokale zoekmethode die begint met een bestaande permutatie en probeert deze te verbeteren door de eerder beschreven gecombineerde operaties toe te passen. Dit tweede algoritme werkt als een klimmer die een hogere top zoekt: het test diverse kleine modificaties, maar accepteert een verandering alleen als deze de cryptografische kwaliteit van de permutatie strikt verbetert. De kwaliteit wordt gemeten aan de hand van twee hoofdonderdelen: differentiële uniformiteit, die de worst-case frequentie van outputpatronen telt, en niet-lineariteit, die de afstand meet tot een eenvoudige lineaire vergelijking. Lagere differentiële uniformiteit en hogere niet-lineariteit zijn over het algemeen beter voor de beveiliging.

De onderzoekers testten deze methoden op een specifieke wiskundige ruimte van omvang 32, wat overeenkomt met een 5-bits systeem. Startend vanaf een eenvoudige, lineaire permutatie die bekend stond als zwak, werd het greedy zoekalgoritme honderd keer uitgevoerd. De experimenten leverden verschillende permutaties op met een differentiële uniformiteit van 4, een significante verbetering ten opzichte van de startwaarde van 32. De studie begon ook met honderd willekeurig gegenereerde permutaties en paste hetzelfde zoekproces toe. Opnieuw vond het algoritme consistent permutaties met een differentiële uniformiteit van 4. De resultaten gingen niet alleen over het vinden van betere getallen; de nieuwe permutaties bezaten duidelijke "spectra", of patronen in outputfrequenties, die van elkaar verschilden en van het startpunt. Dit bewijst dat de methode niet slechts variaties van hetzelfde object produceert, maar werkelijk nieuwe, onderscheidende klassen van veilige permutaties ontdekt.

Een van de meest opvallende bevindingen betreft de relatie tussen deze nieuwe permutaties en een beroemde klasse functies bekend als APN (Almost Perfect Nonlinear) functies. Historisch gezien hebben veel constructies van veilige permutaties geleund op het starten met deze APN-functies. Echter, de studie vond dat de door deze nieuwe lokale conjugatie-methode gegenereerde permutaties, hoewel ze dezelfde uitstekende differentiële uniformiteit van 4 hebben, CCZ-inequivalent zijn aan die afgeleid van de klassieke APN-benaderingen. Sterker nog, een referentie-permutatie gebaseerd op een bekende APN-functie presteerde slechter in deze specifieke test, met een differentiële uniformiteit van 8. Dit suggereert dat de nieuwe methode een ander gebied van het wiskundige landschap verkent en hoogwaardige permutaties ontsluit die voorheen ontoegankelijk waren voor standaard constructietechnieken.

Het artikel concludeert door een conjectuur voor te stellen op basis van het experimentele bewijs: dat de gehele ruimte van deze gelifte permutaties verbonden is. Met andere woorden, het lijkt mogelijk om elke geldige permutatie in deze familie van de ene naar de andere te bereiken door een pad van deze specifieke lokale modificaties te volgen. Hoewel deze connectiviteit niet wiskundig bewezen is, biedt het feit dat het zoekalgoritme consistent hoogwaardige oplossingen vond vanuit diverse startpunten sterk voorlopig bewijs voor dit idee. De studie laat ook de vraag open of deze specifieke familie van permutaties functies bevat die nog sterker zijn dan de gevonden, potentieel reikend tot de theoretische limiet van beveiliging die bekend staat als APN. Voor nu biedt het werk een robuust nieuw instrumentarium voor het genereren van veilige permutaties, waarbij wordt aangetoond dat men door de lokale symmetrieën van deze wiskundige objecten te begrijpen, betere verdedigingen voor de digitale wereld kan construeren.

Technische Samenvatting: De Constructie van Volledige Permutaties via de D-klasse van Lokaal Kromme Permutaties

Probleemstelling

Het artikel behandelt de constructie van Volledige Permutaties (CP's) over eindige lichamen $\mathbb{F}_{2^n}$ . Een permutatie $f$ is een CP als zowel $f$ als de afbeelding $x \mapsto f(x) + x$ permutaties zijn. CP's zijn cruciaal in de cryptografie, specifiek als bouwstenen voor S-boxen in het Lai–Massey-raamwerk en voor het genereren van orthogonale Latijnse vierkanten.

CP's zijn verbonden aan Lokaal Kromme Permutaties (LCP's) over $\mathbb{F}_{2^{n+1}}$ via de Shuai–Li-correspondentie, maar eerdere methoden vertrouwden op een "kromme functie $\to$ LCP $\to$ CP"-pad. Deze benadering was beperkend, omdat het geen vrije beweging of generatie van nieuwe LCP's binnen de klasse zelf mogelijk maakte. Het artikel beoogt dit te overwinnen door direct binnen de LCP-klasse te werken om nieuwe CP's te genereren via interne groepsacties, waardoor de zoekruimte voor cryptografisch sterke permutaties wordt uitgebreid.

Methodologie

1. De D-klasse en Invariantie

De auteur introduceert de D-klasse, gedefinieerd als de verzameling permutaties $f$ over $\mathbb{F}_{2^{n+1}}$ waarvoor de afgeleide in een vaste richting $q_1 = 2^n$ een beeld heeft dat gelijk is aan het complement van een vaste hypervlak $H = \{x : x_n = 0\}$ .
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
waarbij $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

Het artikel bewijst dat $D$ gesloten is onder drie specifieke groepsacties:

Links Translatie: $t_a \circ f$ voor elke $a \in \mathbb{F}_q$ .
Links Multiplicatie: $g \circ f$ voor elke $g$ in de algemene lineaire groep die $H$ behoudt ( $GL_H$ ).
Rechts Multiplicatie: $f \circ h$ voor elke $h$ in de centralisator $C$ van de involutie die $H$ en $K$ verwisselt.

Daarnaast is de klasse gesloten onder specifieke lokale translaties $t_{a,X}$ (translaties beperkt tot een deelverzameling $X$ ), mits $X$ een vereniging is van banen van een specifieke diadale groep gegenereerd door de translatie en de geconjugeerde involutie.

2. Rigiditeit en de Constructieketen

De auteur definieert de gelifte CP-subklasse $D^\uparrow \subset D$ , bestaande uit permutaties in $D$ die optreden als de identiteit op het complement $K$ .

Rigiditeit: Het artikel bewijst dat $D^\uparrow$ "rigide" is onder elke enkele operatie uit de bovenstaande sluitingseigenschappen (translatie, lineaire multiplicatie, of centralisator-multiplicatie). Een enkele operatie kan een gelifte CP niet naar een andere gelifte CP brengen, tenzij het de identiteit is.
Constructieketen: Om nieuwe CP's te genereren, construeert de auteur een keten die een product van operaties omvat:
$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{lokale translatie}} LCP' \xrightarrow{\text{centralisator correctie}} LCP'' \xrightarrow{\text{restrictie}} \text{Nieuwe } CP$
Deze keten maakt gebruik van gelokaliseerde centralisatorelementen ( $g_{a,X_1}$ en $g_{a,X_2}$ ) om het defect te herstellen dat door lokale translaties wordt geïntroduceerd, waardoor wordt gegarandeerd dat het resultaat in $D^\uparrow$ blijft.

3. Lokale Conjugaties

De constructie levert twee specifieke lokale conjugaties op, $f_1$ en $f_2$ , gedefinieerd op het basislichaam $\mathbb{F}_{2^n}$ :

$f_1$ : Een modificatie van $f$ op een deelverzameling $X_1 \subset H$ waar $X_1$ invariant is onder een diadale groep.
$f_2$ : Een modificatie die de inverse van $f$ betreft op een deelverzameling $X_2$ waar $X_2$ invariant is onder een cyclische groep.
Het artikel geeft noodzakelijke en voldoende voorwaarden waaronder deze gemodificeerde afbeeldingen de CP's blijven.

4. Algoritmen

Twee algoritmen worden gepresenteerd om de theorie te implementeren:

Random Backtracking Search: Genereert willekeurige CP's vanaf nul door beperkingen op $f(x)$ en $f(x)+x$ in stand te houden.
Greedy Local Search: Past iteratief de lokale conjugaties ( $f_1, f_2$ ) toe op een seed CP. Het accepteert alleen stappen die de kwaliteit van een functiewaarde strikt verbeteren op basis van het volledige differentiële spectrum (DDT) en het Walsh-spectrum.

Belangrijkste Resultaten

Theoretische Bijdragen

Invariantiebewijs: Vastgesteld dat de D-klasse invariant is onder de gespecificeerde groepsacties en lokale translaties.
Rigiditeitstheorema: Bewezen dat de gelifte CP-subklasse $D^\uparrow$ niet gegenereerd kan worden door enkele operaties, wat de samengestelde constructieketen noodzakelijk maakt.
CCZ-Inequivalentie Criteria: Afgeleid welke criteria nodig zijn om te bepalen wanneer de nieuw geconstrueerde CP's CCZ-inequivalent zijn aan de seed. Dit berust op het controleren of de Differentiele Distributietabel (DDT) of de multiset van absolute Walsh-coëfficiënten verandert.
Cryptografische Grenzen: Afgeleide grenzen voor differentiële uniformiteit ( $\delta$ ), nonlineariteit ($nl$) en algebraïsche graad ( $\deg$ ) onder lokale modificaties. Specifiek verandert $\delta$ met maximaal $2m$ , waarbij $m$ de grootte van de gemodificeerde deelverzameling is.

Experimentele Bevindingen

Experimenten werden uitgevoerd op $H \cong \mathbb{F}_{2^5}$ (32 elementen):

Generatie van $\delta=4$ CP's: Startend vanaf een lineaire seed ( $\delta=32$ ) en willekeurige seeds, vond de greedy search succesvol meerdere volledige permutaties met een differentiële uniformiteit van $\delta=4$ .
Distincte Spectra: De gegenereerde CP's vertoonden verschillende differentiële spectra vergeleken met elkaar en met een referentie Dillon-gebaseerde CP (die een $\delta=8$ had).
CCZ-Inequivalentie: De verschillende differentiële spectra bevestigen dat de constructie nieuwe CCZ-inequivalente klassen produceert, en niet slechts affine varianten van de seed.
Connectiviteitsbewijs: Het herhaaldelijk convergeren naar vergelijkbare indicatorverdelingen vanuit verschillende willekeurige seeds biedt voorlopig bewijs dat de verzameling gelifte CP's $D^\uparrow$ mogelijk verbonden is onder lokale-conjugatiebewegingen.

Betekenis en Claims

Het artikel claimt een systematisch algebraïsch raamwerk te bieden voor het genereren van nieuwe volledige permutaties door de interne structuur van de LCP-klasse uit te buiten.

Voorbij Kromme Functies: In tegenstelling tot eerdere methoden die afhankelijk waren van het starten met een kromme functie, staat deze benadering het verkennen van de LCP-ruimte zelf toe om CP's te vinden.
Cryptografisch Nut: De methode produceert succesvol CP's met een lage differentiële uniformiteit ( $\delta=4$ ), een gewenste eigenschap voor S-boxen, die voorheen moeilijker te construeren waren via de standaard kromme-functie correspondentie.
Structureel Inzicht: De identificatie van de "rigiditeit" van $D^\uparrow$ en de specifieke rol van de centralisator bij het "herstellen" van lokale translaties biedt een dieper theoretisch begrip van de relatie tussen LCP's en CP's.
Open Problemen: De auteur kadert de connectiviteit van $D^\uparrow$ en het bestaan van APN-functies binnen deze klasse bescheiden als open problemen, waarbij wordt gesuggereerd dat hoewel de experimenten de connectiviteit ondersteunen, een formeel bewijs vereist is. Er wordt ook opgemerkt dat hoewel de resultaten wijzen op een potentiële link naar APN-permutaties, er in dit werk geen APN-permutaties expliciet zijn vastgesteld.