🔢 matematica

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

Questo articolo introduce la classe D di permutazioni su $\mathbb{F}_{2^{n+1}}$ per caratterizzare e costruire permutazioni complete tramite coniugazioni locali, stabilendo le loro proprietà algebriche, i limiti crittografici e l'inequivalenza CCZ, presentando al contempo algoritmi che enumerano con successo nuove permutazioni complete $\delta=4$ .

Autori originali: Li Shuai

Pubblicato 2026-10-16

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Li Shuai

Articolo originale sotto licenza CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nell'architettura nascosta della moderna sicurezza digitale, esiste una classe di oggetti matematici noti come permutazioni complete. Queste non sono meri rimescolamenti casuali di numeri; sono riarrangiamenti altamente strutturati dove l'atto di spostare un elemento in una nuova posizione e l'atto di spostarlo in una posizione che è la somma della sua vecchia e della sua nuova posizione portano entrambi a un ordine perfetto e non sovrapponibile. Questo doppio requisito è cruciale per la progettazione delle scatole di sostituzione, o S-box, che sono i componenti primari nei sistemi di cifratura che rimescolano i dati per nasconderne il significato. Se questi componenti sono troppo prevedibili, la cifratura può essere violata; se sono troppo caotici, diventano inefficienti. La sfida per i crittografi è stata a lungo quella di trovare il punto di equilibrio: permutazioni abbastanza complesse da resistere ad attacchi sofisticati, ma abbastanza strutturate da essere implementate rapidamente.

Uno studio recente di Li Shuai della Università di Ningxia affronta questa sfida esplorando una specifica famiglia di queste permutazioni attraverso la lente della simmetria geometrica. La ricerca si concentra su una proprietà chiamata "crookedness locale", che descrive come una permutazione si comporta quando il suo input viene traslato di un certo ammontare. L'autore introduce una nuova categoria di queste funzioni, definite da un pattern specifico in come i loro output cambiano. Trattando queste funzioni come elementi di un gruppo più ampio che può essere trasformato tramite traslazione, rotazione o scambio di parti specifiche dei dati, lo studio mappa un panorama di possibilità. L'obiettivo era vedere se muoversi all'interno di questo panorama potesse generare nuove, superiori permutazioni che offrano una migliore protezione contro la crittanalisi differenziale, un metodo in cui gli attaccanti studiano come piccole variazioni nell'input influenzano l'output per dedurre la chiave segreta.

Il nucleo del lavoro coinvolge una catena di costruzione che parte da una permutazione nota e ben comportata e applica una serie di precise operazioni algebriche per creare nuove permutazioni. L'autore definisce un insieme specifico di regole, o "classe D", che queste permutazioni devono seguire per rimanere valide. All'interno di questo insieme, il ricercatore dimostra che la collezione di permutazioni "sollevate" — quelle che sono state estese da uno spazio più piccolo a uno più grande — possiede una unicità rigida. Se si tenta di cambiare una singola permutazione usando solo un tipo di operazione, come una semplice traslazione o una rotazione lineare, il risultato solitmente fallisce nel rimanere una permutazione completa valida. Tuttavia, lo studio dimostra che combinare due diverse operazioni in una sequenza specifica rompe questa rigidità. Questa combinazione permette al ricercatore di navigare nello spazio delle possibilità, passando da una permutazione valida a un'altra senza perdere le proprietà essenziali richieste per la sicurezza.

Per rendere pratico questo framework teorico, l'articolo sviluppa due algoritmi distinti. Il primo è una ricerca con backtracking che costruisce una permutazione completa da zero, assicurando ad ogni passaggio che i requisiti di doppio ordinamento siano soddisfatti. Il secondo è una ricerca locale greedy che parte da una permutazione esistente e tenta di migliorarla applicando le operazioni combinate descritte in precedenza. Questo secondo algoritmo agisce come un scalatore che cerca una vetta più alta: testa varie piccole modifiche, ma accetta un cambiamento solo se migliora rigorosamente la qualità crittografica della permutazione. La qualità è misurata da due indicatori principali: l'uniformità differenziale, che conta la frequenza peggiore dei pattern di output, e la non linearità, che misura quanto la funzione sia lontana dall'essere una semplice equazione lineare. Una uniformità differenziale più bassa e una non linearità più alta sono generalmente migliori per la sicurezza.

I ricercatori hanno testato questi metodi su uno spazio matematico specifico di dimensione 32, che corrisponde a un sistema a 5 bit. Partendo da una permutazione lineare semplice, nota per essere debole, l'algoritmo di ricerca greedy è stato eseguito cento volte. Gli esperimenti hanno prodotto diverse permutazioni con un'uniformità differenziale di 4, un miglioramento significativo rispetto al valore iniziale di 32. Lo studio è iniziato anche con cento permutazioni generate casualmente e ha applicato lo stesso processo di ricerca. Anche in questo caso, l'algoritmo ha trovato costantemente permutazioni con un'uniformità differenziale di 4. I risultati non riguardavano solo il trovare numeri migliori; le nuove permutazioni possedevano "spettri" distinti, ovvero pattern di frequenza di output, che erano diversi tra loro e rispetto al punto di partenza. Ciò prova che il metodo non produce solo variazioni dello stesso oggetto, ma scopre realmente nuove e distinte classi di permutazioni sicure.

Uno dei risultati più sorprendenti riguarda la relazione tra queste nuove permutazioni e una famosa classe di funzioni note come funzioni APN (Almost Perfect Nonlinear). Storicamente, molte costruzioni di permutazioni sicure hanno fatto affidamento sull'utilizzo di queste funzioni APN come punto di partenza. Tuttavia, lo studio ha scoperto che le permutazioni generate da questo nuovo metodo di coniugazione locale, pur avendo la stessa eccellente uniformità differenziale di 4, sono CCZ-inequivalenti a quelle derivate dai classici approcci APN. In effetti, una permutazione di riferimento basata su una nota funzione APN ha performato peggio in questo test specifico, con un'uniformità differenziale di 8. Ciò suggerisce che il nuovo metodo esplora una regione diversa del panorama matematico, scoprendo permutazioni di alta qualità che erano precedentemente inaccessibili alle tecniche di costruzione standard.

L'articolo conclude proponendo una congettura basata sull'evidenza sperimentale: che l'intero spazio di queste permutazioni sollevate sia connesso. In altre parole, sembra possibile raggiungere qualsiasi permutazione valida in questa famiglia partendo da qualsiasi altra seguendo un percorso di queste specifiche modifiche locali. Sebbene questa connettività non sia stata matematicamente dimostrata, il fatto che l'algoritmo di ricerca abbia costantemente trovato soluzioni di alta qualità da punti di partenza diversi fornisce un forte supporto preliminare all'idea. Lo studio lascia anche aperta la questione se questa specifica famiglia di permutazioni contenga funzioni che siano ancora più forti di quelle trovate, potenzialmente raggiungendo il limite teorico di sicurezza noto come APN. Per ora, il lavoro fornisce un nuovo e robusto toolkit per generare permutazioni sicure, dimostrando che comprendendo le simmetrie locali di questi oggetti matematici, si possono costruire difese migliori per il mondo digitale.

Sintesi Tecnica: Costruzione di Permutazioni Complete tramite la Classe-D delle Permutazioni Localmente Crooked

Definizione del Problema

Il documento affronta la costruzione di Permutazioni Complete (CP) su campi finiti $\mathbb{F}_{2^n}$ . Una permutazione $f$ è una CP se sia $f$ che la mappa $x \mapsto f(x) + x$ sono permutazioni. Le CP sono fondamentali nella crittografia, specificamente come componenti costruttivi per le S-box nel framework di Lai–Massey e per la generazione di quadrati latini ortogonali.

Sebbene le CP siano collegate alle Permutazioni Localmente Crooked (LCP) su $\mathbb{F}_{2^{n+1}}$ tramite la corrispondenza di Shuai–Li, i metodi precedenti si basavano su un percorso "funzione crooked $\to$ LCP $\to$ CP". Questo approccio era restrittivo, poiché non permetteva il movimento libero o la generazione di nuove LCP all'interno della classe stessa. Il documento mira a superare questo limite lavorando direttamente all'interno della classe LCP per generare nuove CP attraverso azioni di gruppo interne, espandendo così lo spazio di ricerca per permutazioni crittograficamente forti.

Metodologia

1. La Classe-D e l'Invarianza

L'autore introduce la classe-D, definita come l'insieme di permutazioni $f$ su $\mathbb{F}_{2^{n+1}}$ tali che la derivata in una direzione fissa $q_1 = 2^n$ abbia un immagine uguale al complemento di un iperpiano fisso $H = \{x : x_n = 0\}$ .
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
dove $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

Il documento dimostra che $D$ è chiuso sotto tre specifiche azioni di gruppo:

Traslazione a Sinistra: $t_a \circ f$ per ogni $a \in \mathbb{F}_q$ .
Moltiplicazione a Sinistra: $g \circ f$ per ogni $g$ nel gruppo lineare generale che preserva $H$ ( $GL_H$ ).
Moltiplicazione a Destra: $f \circ h$ per ogni $h$ nel centralizzatore $C$ dell'involuzione che scambia $H$ e $K$ .

Inoltre, la classe è chiusa sotto traslazioni locali $t_{a,X}$ (traslazioni limitate a un sottoinsieme $X$ ) a condizione che $X$ sia l'unione di orbite di un gruppo diedrale specifico generato dalla traslazione e dall'involuzione coniugata.

2. Rigidità e la Catena di Costruzione

L'autore definisce la sottoclasse di CP sollevata $D^\uparrow \subset D$ , composta da permutazioni in $D$ che agiscono come identità sul complemento $K$ .

Rigidità: Il documento dimostra che $D^\uparrow$ è "rigida" rispetto a qualsiasi singola operazione dalle proprietà di chiusura sopra citate (traslazione, moltiplicazione lineare o moltiplicazione nel centralizzatore). Una singola operazione non può mappare una CP sollevata in un'altra CP sollevata a meno che non sia l'identità.
Catena di Costruzione: Per generare nuove CP, l'autore costruisce una catena che coinvolge un prodotto di operazioni:
$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{local translation}} LCP' \xrightarrow{\text{centralizer correction}} LCP'' \xrightarrow{\text{restriction}} \text{New } CP$
Questa catena utilizza elementi del centralizzatore localizzati ( $g_{a,X_1}$ e $g_{a,X_2}$ ) per "riparare" il difetto introdotto dalle traslazioni locali, garantendo che il risultato rimanga in $D^\uparrow$ .

3. Coniugazioni Locali

La costruzione produce due specifiche coniugazioni locali, $f_1$ e $f_2$ , definite sul campo base $\mathbb{F}_{2^n}$ :

$f_1$ : Una modifica di $f$ su un sottoinsieme $X_1 \subset H$ dove $X_1$ è invariante sotto un gruppo diedrale.
$f_2$ : Una modifica che coinvolge l'inverso di $f$ su un sottoinsieme $X_2$ dove $X_2$ è invariante sotto un gruppo ciclico.
Il documento fornisce le condizioni necessarie e sufficienti affinché queste mappe modificate rimangano CP.

4. Algoritmi

Due algoritmi sono presentati per implementare la teoria:

Ricerca con Backtracking Casuale: Genera CP casuali da zero mantenendo i vincoli su $f(x)$ e $f(x)+x$ .
Ricerca Locale Greedy: Applica iterativamente le coniugazioni locali ( $f_1, f_2$ ) a una CP seme. Accetta mosse solo se migliorano strettamente una funzione di qualità basata sul pieno spettro differenziale (DDT) e sullo spettro di Walsh.

Risultati Chiave

Contributi Teorici

Dimostrazione di Invarianza: Ha stabilito che la classe-D è invariante sotto le specificate azioni di gruppo e le traslazioni locali.
Teorema di Rigidità: Ha dimostrato che la sottoclasse di CP sollevata $D^\uparrow$ non può essere generata da singole operazioni, rendendo necessaria la catena di costruzione composita.
Criteri di CCZ-Inequivalenza: Ha derivato criteri per determinare quando le nuove CP costruite sono CCZ-inequivalenti al seme. Ciò si basa sulla verifica se la Tabella di Distribuzione Differenziale (DDT) o il multiset dei coefficienti assoluti di Walsh cambiano.
Limiti Crittografici: Ha derivato i limiti per l'uniformità differenziale ( $\delta$ ), la non linearità ($nl$) e il grado algebrico ( $\deg$ ) sotto modifiche locali. Nello specifico, $\delta$ cambia di al massimo $2m$ dove $m$ è la dimensione del sottoinsieme modificato.

Risultati Sperimentali

Sono stati condotti esperimenti su $H \cong \mathbb{F}_{2^5}$ (32 elementi):

Generazione di CP con $\delta=4$ : Partendo da un seme lineare ( $\delta=32$ ) e da semi casuali, la ricerca greedy ha trovato con successo molteplici permutazioni complete con uniformità differenziale $\delta=4$ .
Spettri Distinti: Le CP generate hanno esibito spettri differenziali distinti rispetto ad altre e rispetto a una CP di riferimento basata su Dillon (che aveva $\delta=8$ ).
CCZ-Inequivalenza: Gli spettri differenziali distinti confermano che la costruzione produce nuove classi di CCZ-inequivalenza, non solo varianti affini del seme.
Evidenza di Connettività: La ripetuta convergenza verso distribuzioni di indicatori simili da diversi semi casuali fornisce una prova preliminare che l'insieme delle CP sollevate $D^\uparrow$ possa essere connesso sotto mosse di coniugazione locale.

Significato e Rivendicazioni

Il documento sostiene di fornire un framework algebrico sistematico per generare nuove permutazioni complete sfruttando la struttura interna della classe LCP.

Oltre le Funzioni Crooked: A differenza dei metodi precedenti dipendenti dal partire da una funzione crooked, questo approccio permette di esplorare lo spazio LCP stesso per trovare CP.
Utilità Crittografica: Il metodo produce con successo CP con bassa uniformità differenziale ( $\delta=4$ ), una proprietà desiderabile per le S-box, che erano precedentemente più difficili da costruire tramite la standard corrispondenza delle funzioni crooked.
Intuizione Strutturale: L'identificazione della "rigidità" di $D^\uparrow$ e del ruolo specifico del centralizzatore nel "riparare" le traslazioni locali offre una comprensione teorica più profonda della relazione tra LCP e CP.
Problemi Aperti: L'autore inquadra modestamente la connettività di $D^\uparrow$ e l'esistenza di funzioni APN all'interno di questa classe come problemi aperti, suggerendo che, sebbene gli esperimenti supportino la connettività, è necessaria una prova formale. Nota inoltre che, sebbene i risultati suggeriscano un potenziale legame con le permutazioni APN, nessuna permutazione APN è stata esplicitamente stabilita in questo lavoro.