🔢 mathematics

Triprojective almost perfect nonlinear permutations and functions

Questo articolo introduce una vasta famiglia di permutazioni quasi perfettamente non lineari (APN) per spazi vettoriali finiti di dimensioni dispari divisibili per tre, nonché funzioni APN non biiettive per dimensioni pari, tutte caratterizzate da una struttura triproiettiva indotta dal gruppo lineare generale $\mathrm{GL}(3,2^m)$ .

Autori originali: Faruk Göloğlu, Lukas Kölsch

Pubblicato 2026-05-19

📖 5 min di lettura🧠 Approfondimento

CC0 1.0

Autori originali: Faruk Göloğlu, Lukas Kölsch

Articolo originale dedicato al pubblico dominio sotto CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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

Immagina di essere un fabbro esperto che cerca di progettare la cassaforte definitiva. Nel mondo della sicurezza digitale, i "lucchetti" sono funzioni matematiche utilizzate per mescolare i dati in modo che gli hacker non possano risalire al messaggio originale. Il documento su cui stai chiedendo informazioni è un progetto per costruire un nuovo tipo di lucchetto incredibilmente robusto.

Ecco la storia di ciò che gli autori, Faruk Gölöglu e Lukas Kölsch, hanno scoperto, spiegata senza il pesante gergo matematico.

L'Obiettivo: Il Mescolatore Perfetto

In crittografia, esiste un tipo specifico di lucchetto chiamato S-Box (Scatola di Sostituzione). Pensa a un S-Box come a una macchina che prende un insieme di input (come una combinazione di numeri) e sputa un insieme completamente diverso di output.

Il pericolo deriva da un metodo chiamato "crittanalisi differenziale". Immagina un ladro che cerca di forzare la tua cassaforte notando dei modelli: "Se giro la manopola di un scatto verso destra, il lucchetto cambia il suo suono di una quantità specifica. Se la giro di due scatti, il suono cambia in modo diverso." Se il lucchetto reagisce in modo troppo prevedibile a piccoli cambiamenti, il ladro può lavorare all'indietro per trovare la chiave.

Per fermare questo, i matematici cercano funzioni APN (Quasi Perfettamente Non Lineari). Questi sono i lucchetti "perfetti" in cui un piccolo cambiamento nell'input causa un cambiamento caotico e imprevedibile nell'output. L'obiettivo è rendere tale che, non importa come il ladro modifichi l'input, l'output appaia come rumore casuale.

La Grande Sfida: Il Problema della "Dimensione Pari"

Per molto tempo, i matematici hanno saputo costruire questi lucchetti perfetti per determinate dimensioni di dati (nello specifico, quando la dimensione dei dati è un numero dispari). Ma per i blocchi di dati di dimensione pari (che sono molto comuni nei computer reali), trovare un lucchetto perfetto che sia anche una permutazione (il che significa che ogni singolo input mappa su un output unico, così nulla va perso) è stato un enorme mal di testa. È come cercare una chiave che si adatti a ogni lucchetto in una specifica fila di case, ma continui a scoprire che alcune chiavi aprono due lucchetti contemporaneamente, o che alcuni lucchetti non hanno affatto una chiave.

Gli autori di questo documento dicono: "Abbiamo trovato un modo per costruire questi lucchetti perfetti e non ripetitivi per una vasta nuova famiglia di blocchi di dati di dimensione pari."

L'Ingrediente Segreto: Architettura "Triproiettiva"

Gli autori non hanno semplicemente inciampato in una formula casuale. Hanno costruito i loro lucchetti utilizzando uno stile architettonico specifico che chiamano "Triproiettivo".

Per capire questo, immagina di guardare una scultura tridimensionale.

Lucchetti Standard: Di solito, questi sono costruiti guardando la scultura da un solo angolo (una vista piatta, 2D).
I Nuovi Lucchetti "Triproiettivi": Gli autori hanno costruito la loro funzione guardando la scultura da tre angoli diversi simultaneamente, utilizzando un gruppo speciale di regole (relativo a una struttura matematica chiamata $GL(3, 2^m)$ ).

Chiamano questa una struttura "Triproiettiva" perché tratta i dati come se esistessero in uno spazio 3D dove le regole della geometria sono leggermente distorte. Disponendo i dati in questo modo, assicurano che il "mescolamento" avvenga in un modo incredibilmente difficile da prevedere, indipendentemente da come si tenta di sondarlo.

La Formula Magica

Il documento presenta una ricetta specifica (una formula) per questi lucchetti. Coinvolge tre variabili ( $x, y, z$ ) e alcuni numeri speciali ( $a, b, c$ ).

La ricetta ha un "controllo di sicurezza". Prima di poter usare il lucchetto, devi eseguire un rapido test per assicurarti che una specifica equazione non abbia soluzioni.

Se il test supera: Ottieni un lucchetto perfetto e inattaccabile (una permutazione APN).
Se il test fallisce: Il lucchetto è ancora molto forte (altamente non lineare), ma potrebbe non essere una permutazione perfetta (alcuni input potrebbero mapparsi sullo stesso output).

Gli autori dimostrano che se scegli i tuoi numeri correttamente, questa ricetta funziona per ogni dimensione dispari divisibile per tre. Questa è un'espansione massiccia di ciò che era precedentemente noto.

Perché Questo È Importante (Secondo il Documento)

Unifica le Scoperte Antiche: Gli autori mostrano che diverse altre formule complicate scoperte da diversi matematici negli ultimi anni sono in realtà solo versioni semplificate e speciali della loro nuova ricetta "Triproiettiva". È come rendersi conto che tre diversi tipi di auto sono in realtà solo diverse verniciature sullo stesso telaio.
È Nuovo e Unico: Dimostrano che la loro nuova famiglia di lucchetti è fondamentalmente diversa dai lucchetti "Gold" (una famosa famiglia di funzioni APN scoperta decenni fa). Non stanno solo ridenominando vecchie chiavi; stanno forgando chiavi completamente nuove.
La Prova è "Pulita": I precedenti tentativi di dimostrare che questi lucchetti funzionavano richiedevano massicce simulazioni al computer e pagine di algebra complessa. Gli autori hanno utilizzato un approccio astuto e puramente logico (usando "polinomi distorti" e proprietà dei campi finiti) per dimostrare i loro risultati senza bisogno di un supercomputer.

La Conclusione

Questo documento è una svolta matematica nella progettazione dei lucchetti di sicurezza digitale. Gli autori hanno scoperto un nuovo e versatile metodo "Triproiettivo" per costruire Permutazioni Quasi Perfettamente Non Lineari.

In termini semplici: Hanno trovato un nuovo e affidabile modo per costruire i mescolatori di dati più forti possibili per una vasta gamma di dimensioni di dati dei computer, risolvendo un problema che aveva messo in difficoltà gli esperti per anni. Non hanno trovato solo un nuovo lucchetto; hanno trovato un'intera fabbrica per produrli, e hanno dimostrato che questi nuovi lucchetti sono distinti da qualsiasi altro che abbiamo visto prima.

Sintesi Tecnica: Permutazioni e Funzioni Quasi Perfettamente Non Lineari Triproiettive

Enunciato del Problema
Il lavoro affronta l'esistenza e la costruzione di permutazioni Quasi Perfettamente Non Lineari (APN) su spazi vettoriali finiti di dimensione pari. Nel contesto della crittanalisi differenziale, le funzioni APN (quelle con uniformità differenziale $\Delta_F = 2$ ) sono fondamentali per la progettazione di S-Box sicure nelle reti di sostituzione-permutazione. Sebbene sia noto che le funzioni APN esistano per dimensioni dispari, l'esistenza di permutazioni APN (bijezioni) per dimensioni pari $n > 6$ rimane un problema aperto di primaria importanza. Nello specifico, gli autori si concentrano sulla costruzione di grandi famiglie di tali funzioni nelle dimensioni $n = 3m$ (dove $m$ è dispari) e sulla caratterizzazione delle loro proprietà, incluse le classi di equivalenza e le dimensioni degli insiemi immagine.

Metodologia
Gli autori adottano un approccio strutturale basato su mappe "triproiettive" e "semi-quadratiche". La metodologia procede attraverso i seguenti passaggi:

Struttura Proiettiva: Gli autori definiscono una classe di funzioni $F \in SQH(3, q)$ (semi-quadratiche omogenee) su $\mathbb{F}_q^3$ (dove $q=2^m$ ). Queste funzioni sono indotte da forme semi-quadratiche che soddisfano specifiche proprietà di omogeneità, permettendo loro di indurre mappe ben definite sullo spazio proiettivo $\mathbb{P}^2(\mathbb{F}_q)$ .
Criteri di Biezione: Basandosi su lavori precedenti (Teorema 1.2), il lavoro utilizza una condizione su un polinomio univariato specifico $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ per garantire che la mappa indotta sullo spazio proiettivo sia una biezione.
Analisi dell'Uniformità Differenziale:
- Caso $m/d$ è pari: Gli autori utilizzano il concetto di "nucleo" della funzione (un sottocampo su cui la mappa derivata è lineare) per dimostrare che l'uniformità differenziale è $2d$ , dove $d = \gcd(k, m)$ .
- Caso $m/d$ è dispari: Gli autori introducono strumenti dalla teoria degli anelli di polinomi distorti (anelli di Ore) $\mathbb{F}_q[t; \sigma]$ . Stabiliscono una connessione tra le radici del polinomio $P(X)$ e l'esistenza di divisori destri lineari nell'anello distorto. Estendendo il campo e analizzando il minimo comune multiplo sinistro (lclm) dei polinomi, dimostrano che l'uniformità differenziale rimane $2d$ anche in questo caso più complesso.
Equivalenza e Classificazione: Il lavoro confronta la nuova famiglia con le esistenti funzioni APN trivariate (nello specifico quelle di Li-Kaleyski e Bartoli-Stanica) utilizzando l'equivalenza lineare. Inoltre, dimostra l'inequivalenza rispetto alle funzioni APN di Gold ( $x^{2^i+1}$ ) analizzando i gruppi di automorfismi lineari ( $Aut_L(F)$ ) e mostrando che non possono essere coniugati nel gruppo lineare generale.

Contributi e Risultati Chiave

Costruzione di Permutazioni APN: Il lavoro presenta una grande famiglia di permutazioni APN per spazi vettoriali finiti di dimensione $n=3m$ dove $m$ è dispari. Le funzioni sono definite come:
$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)$
dove $\sigma = 2^k$ , $a, b, c \in \mathbb{F}_q$ , e $a \neq 0$ .
Uniformità Differenziale: Gli autori dimostrano che se l'equazione polinomiale $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$ non ha soluzioni in $\mathbb{F}_q$ , l'uniformità differenziale di $F$ è $2d$ (dove $d = \gcd(k, m)$ ). Di conseguenza, quando $d=1$ e $m$ è dispari, $F$ è una permutazione APN.
Dimensione dell'Insieme Immagine: Il lavoro caratterizza la dimensione dell'insieme immagine di queste funzioni. Se $m/d$ è pari, la funzione è $(2d+1)$ -a-uno su $\mathbb{F}_q^3 \setminus \{0\}$ . Se $m/d$ è dispari, la funzione è bieettiva su $\mathbb{F}_q^3$ .
Unificazione delle Famiglie Esistenti: Gli autori dimostrano che diverse famiglie recentemente scoperte di funzioni APN trivariate (Li-Kaleyski e Bartoli-Stanica) sono linearmente equivalenti a istanze specifiche della loro famiglia proposta (ottenute impostando parametri specifici $a, b, c$ ). Ciò fornisce una spiegazione unificata ed elementare per queste costruzioni, evitando le complesse distinzioni di casi e i calcoli di risultanti assistiti da computer utilizzati nelle prove precedenti.
Inequivalenza rispetto alle Funzioni di Gold: Il lavoro dimostra che per $m > 2$ e $m \neq 6$ , le funzioni APN costruite sono CCZ-inequivalenti alle funzioni APN di Gold. Ciò è stabilito mostrando che i loro gruppi di automorfismi lineari non sono coniugati in $GL(3m, 2)$.

Significato e Affermazioni
Il lavoro afferma di fornire una "grande famiglia" di permutazioni APN in ogni dimensione dispari divisibile per tre, affrontando la questione aperta delle biezioni APN per dimensioni pari. Il significato risiede in:

Generalità: La costruzione produce un numero esponenzialmente grande di funzioni APN a due a due inequivalenti, dimostrabilmente, all'interno della classe delle mappe multiproiettive.
Semplificazione: Le prove sono descritte come "senza computer, molto più brevi e puramente elementari" rispetto ai lavori precedenti, offrendo un quadro unificato per comprendere varie funzioni APN trivariate.
Nuovi Esempi: Si dimostra che la famiglia contiene esempi che sono inequivalenti alle funzioni APN note (incluse le funzioni di Gold), ampliando il panorama conosciuto dei primitivi crittografici.

Gli autori notano che, sebbene gli spettri di Walsh siano noti per il caso in cui $m/d$ è pari, determinare lo spettro di Walsh per le permutazioni APN (dove $m$ è dispari) rimane un problema aperto. Identificano inoltre la classificazione delle funzioni semi-quadratiche omogenee che portano a biezioni proiettive come una direzione naturale per la ricerca futura.