🔢 mathematics

Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$

Il lavoro presenta due nuove famiglie infinite di permutazioni APN su $\mathbb{F}_{2^{3m}}$ ottenute generalizzando le costruzioni di Li-Kaleyski, fornendo criteri esatti per la loro esistenza e dimostrando la loro non-equivalenza CCZ rispetto alle famiglie note e tra loro.

Autori originali: Daniele Bartoli, Pantelimon Stanica

Pubblicato 2026-03-17

📖 4 min di lettura🧠 Approfondimento

CC0 1.0

Autori originali: Daniele Bartoli, Pantelimon Stanica

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 dover costruire una cassaforte digitale perfetta. Per farla funzionare, hai bisogno di un meccanismo di chiusura (una funzione matematica) che abbia due proprietà fondamentali:

Invertibilità (Permutazione): Se inserisci un codice, la cassaforte si apre in modo unico. Non ci sono due codici diversi che aprono la stessa serratura, e non ci sono codici che non aprono nulla. È come se ogni chiave avesse una sola serratura corrispondente.
Resistenza agli attacchi (APN): Se un ladro prova a forzare la serratura facendo piccole modifiche al codice (aggiungendo o togliendo un bit), il risultato deve essere così caotico e imprevedibile che non può dedurre nulla sulla chiave originale. In termini matematici, la funzione deve essere "quasi perfettamente non lineare" (APN).

Costruire funzioni che siano contemporaneamente perfette come chiavi (invertibili) e perfette come scudi (APN) è un incubo per i matematici. È come cercare un unicorno: ne esistono pochissimi, e trovarne di nuovi è estremamente difficile.

Cosa hanno fatto gli autori?

Daniele Bartoli e Pantelimon Stănică in questo articolo hanno scoperto due nuove famiglie infinite di queste "cassaforte perfette".

Ecco come lo spiegano, usando un'analogia semplice:

1. Il problema dei "parametri magici"

Immagina di avere una ricetta per una torta (la funzione matematica). La ricetta è quasi perfetta, ma c'è un ingrediente segreto, chiamiamolo "a", che puoi scegliere a tuo piacimento.

Se scegli il numero sbagliato per "a", la torta viene male (la cassaforte si blocca o è facile da forzare).
Se scegli il numero giusto, la torta è divina (la cassaforte è sicura e apre sempre).

Prima di questo lavoro, si conoscevano solo alcune ricette dove l'ingrediente "a" poteva essere solo 1. Gli autori si sono chiesti: "E se provassimo a usare qualsiasi numero disponibile nel nostro universo matematico (il campo finito $\mathbb{F}_{2^m}$ )?"

2. La scoperta: Il "Test della Radice"

Hanno scoperto che non serve provare a caso milioni di numeri. Hanno trovato un test magico (un criterio basato sulle radici di un polinomio) per capire subito se un numero "a" è buono o no.

L'analogia: Immagina che ogni numero "a" sia un viaggiatore. Per entrare nel club esclusivo delle "Cassaforti Perfette", il viaggiatore deve superare un controllo di sicurezza. Questo controllo è un'equazione matematica. Se l'equazione ha una "radice" (una soluzione) nel mondo dei numeri disponibili, il viaggiatore viene scartato. Se non ha radici, entra nel club!

Grazie a questo test, hanno dimostrato che:

Esistono molti numeri "a" che funzionano (hanno calcolato un numero minimo garantito).
Se un numero "a" funziona per la prima ricetta (chiamata $G_a$ ), funziona automaticamente anche per la seconda ricetta (chiamata $H_a$ ). Sono come due gemelli che rispondono allo stesso codice di sicurezza.

3. Non sono copie: La prova dell'unicità

C'era il rischio che queste nuove cassaforti fossero solo copie vecchie di quelle già scoperte da altri ricercatori (Li e Kaleyski) nel 2024.
Gli autori hanno fatto un'analisi approfondita e hanno detto: "No, sono diverse!".

L'analogia: È come se avessi due macchine sportive che sembrano uguali da fuori. Hanno controllato il motore e hanno scoperto che, a meno che tu non scelga un numero "a" molto specifico (quasi mai), il motore di queste nuove macchine è completamente diverso da quello delle macchine vecchie. Non sono solo "riscritte", sono nuovi modelli con una struttura interna unica.

Perché è importante?

Nel mondo della crittografia (la scienza che protegge i nostri dati, le banche, le comunicazioni militari), abbiamo bisogno di queste funzioni matematiche per creare i "blocchi" che mescolano i dati.

Più ne troviamo di nuove e diverse, più è difficile per gli hacker trovare un punto debole comune.
Questo lavoro ci dà due nuove famiglie infinite di questi blocchi sicuri, che possiamo usare in dimensioni diverse (non solo in casi rari, ma in molti casi possibili).

In sintesi

Gli autori hanno preso due ricette matematiche che funzionavano solo con un ingrediente specifico, hanno scoperto come usarle con qualsiasi ingrediente (seguendo una regola semplice per sceglierlo), e hanno provato che queste nuove combinazioni sono sicure, invertibili e completamente nuove rispetto a tutto ciò che conoscevamo prima. Hanno quindi aperto una nuova miniera di "chiavi digitali" per proteggere il futuro.

Titolo: Famiglie infinite di permutazioni APN in classi trivariate vincolate su $\mathbb{F}_{2^m}$

Autori: Daniele Bartoli e Pantelimon Stănică
Data: 17 marzo 2026 (preprint arXiv)

1. Il Problema

La costruzione di polinomi di permutazione su campi finiti con una struttura algebrica semplice in più variabili è un problema fondamentale nella crittografia e nella teoria dei codici. In particolare, le funzioni APN (Almost Perfect Nonlinear) sono cruciali per la resistenza alla crittanalisi differenziale. Quando una funzione APN è anche una permutazione, costituisce un blocco costruttivo ideale (S-box) per cifrari a blocchi, combinando ottima resistenza differenziale e invertibilità.

Tuttavia, la costruzione di permutazioni APN è notoriamente difficile: sono note solo poche famiglie infinite. Recentemente, Li e Kaleyski (2024) hanno generalizzato due permutazioni APN quadratiche "sporadiche" (scoperte da Beierle e Leander su $\mathbb{F}_{2^9}$ ) in due famiglie infinite di funzioni trivariate con coefficienti scalari in $\mathbb{F}_2$ .

Il problema affrontato in questo lavoro è estendere le famiglie di Li-Kaleyski permettendo al coefficiente scalare di variare liberamente sull'intero campo moltiplicativo $\mathbb{F}_{2^m}^*$ , invece di essere fissato a 1. L'obiettivo è determinare per quali parametri $a$ queste funzioni generalizzate rimangono permutazioni e APN, e studiare la loro equivalenza rispetto alle famiglie originali.

2. Metodologia

Gli autori utilizzano un approccio che combina algebra lineare su campi finiti, teoria dei polinomi e geometria algebrica.

Definizione delle Famiglie: Vengono studiate due famiglie di funzioni trivariate $G_a$ $G_{a}$ e $H_a$ $H_{a}$ su $\mathbb{F}_{2^m}^3$ $F_{2^{m}}^{3}$ , dove $m$ $m$ è dispari, $q=2^i$ $q = 2^{i}$ con $\gcd(i,m)=1$ $g cd (i, m) = 1$ , e $a \in \mathbb{F}_{2^m}^*$ $a \in F_{2^{m}}^{*}$ .
- $G_a(x, y, z) = (x^{q+1} + ax^qz + yz^q, \ x^qz + y^{q+1}, \ xy^q + ay^qz + z^{q+1})$
- $H_a(x, y, z) = (x^{q+1} + axy^q + yz^q, \ xy^q + z^{q+1}, \ x^qz + y^{q+1} + ay^qz)$
Riduzione a Polinomi Univariati: La proprietà di permutazione e la proprietà APN vengono caratterizzate riducendo il problema alla ricerca di radici di specifici polinomi univariati in $\mathbb{F}_{2^m}$ . Viene dimostrato che per entrambe le famiglie, la condizione necessaria e sufficiente è l'assenza di radici in $\mathbb{F}_{2^m}^*$ per un polinomio associato (denominato $Q_a(T)$ per $G_a$ e un polinomio equivalente per $H_a$ ).
Strumenti di Geometria Algebrica: Per stimare il numero di parametri "buoni" (cioè quelli per cui il polinomio non ha radici), gli autori utilizzano il Teorema di Hasse-Weil e il Legame di Lang-Weil su curve algebriche. Analizzano la curva di collisione definita dall'equazione $g(x) = g(y)$ , dove $g(u) = (u^d+1)/u$ e $d=q^2+q+1$ , dimostrando che questa curva è assolutamente irriducibile.
Analisi di Equivalenza: Vengono studiate le equivalenze tra le nuove famiglie e le rappresentative di Li-Kaleyski ( $G_1, H_1$ ) e tra le due famiglie stesse ( $G_a$ vs $H_b$ ). Si utilizzano teoremi sulla restrizione monomiale (Shi et al.) per dimostrare che, sotto certe condizioni, la non-equivalenza diagonale implica la non-equivalenza CCZ (Carlet-Charpin-Zinoviev).

3. Contributi Chiave e Risultati

A. Caratterizzazione delle Proprietà APN e di Permutazione

Il risultato principale è che per la famiglia $G_a$ (e analogamente per $H_a$ ), le proprietà di essere una permutazione e di essere APN sono equivalenti e sono entrambe governate dalla stessa condizione algebrica:

$G_a$ è una permutazione APN se e solo se il polinomio $Q_a(T) = T^{q^2+q+1} + aT + 1$ non ha radici in $\mathbb{F}_{2^m}$ .

Questo riduce un problema complesso su funzioni multivariata a un problema di esclusione di radici per un polinomio univariato.

B. Stima Quantitativa dei Parametri Validi

Gli autori derivano un limite inferiore quantitativo per il numero di parametri $a \in \mathbb{F}_{2^m}^*$ che generano permutazioni APN. Se $d = q^2 + q + 1$ , il numero di tali parametri è almeno:
$\frac{2^m + 1 - (d-1)(d-2)2^{m/2} - d}{d}$
Ciò garantisce l'esistenza di infinite famiglie di permutazioni APN per ogni $m$ dispari sufficientemente grande.

C. Caso Binario ( $q=2$ ) e Recupero del Risultato di Li-Kaleyski

Nel caso specifico $q=2$ (dove $d=7$ ), viene dimostrato che $a=1$ è un parametro valido se e solo se $7 \nmid m$ . Questo recupera la famiglia originale di Li-Kaleyski. Inoltre, per ogni $a \neq 1$ tale che $a^7 \neq 1$ , si ottengono nuove permutazioni APN.

D. Risultati di Non-Equivalenza (CCZ)

Il lavoro stabilisce risultati forti sull'inequivalenza:

Equivalenza Diagonale: $G_a$ $G_{a}$ (o $H_a$ $H_{a}$ ) è diagonalmente equivalente alla rappresentante di Li-Kaleyski ( $G_1$ $G_{1}$ o $H_1$ $H_{1}$ ) se e solo se $a^{q^2+q+1} = 1$ $a^{q^{2} + q + 1} = 1$ .
- Per $q=2$ e $7 \nmid m$ , l'unica soluzione è $a=1$ . Quindi, tutti gli altri parametri validi generano permutazioni CCZ-inequivalenti a quelle note.
Inequivalenza tra Famiglie: Per $m > 4, m \neq 6, 7 \nmid m$ $m > 4, m \neq = 6, 7 ∤ m$ , nessun membro della famiglia $G_a$ $G_{a}$ è CCZ-equivalente a nessun membro della famiglia $H_b$ $H_{b}$ (con lo stesso $q$ $q$ ).
- Questo dimostra che le due famiglie costituiscono sorgenti distinte e genuinamente nuove di permutazioni APN.

4. Significato e Implicazioni

Espansione dello Spazio delle Soluzioni: Il lavoro amplia significativamente la conoscenza delle permutazioni APN, fornendo infinite famiglie parametriche invece di casi sporadici.
Nuove Classi di S-box: Le nuove permutazioni sono CCZ-inequivalenti a tutte le famiglie conosciute precedentemente (inclusi i casi di Li-Kaleyski), offrendo potenziali nuove strutture per la progettazione di cifrari a blocchi più sicuri.
Metodologia Potente: La riduzione del problema trivariato a un criterio di radice univariato, supportato da stime geometriche (Hasse-Weil), fornisce un modello metodologico potente per analizzare altre classi di funzioni su campi finiti.
Risoluzione di Congetture: Il lavoro conferma e generalizza risultati precedenti, risolvendo questioni aperte sulla struttura delle famiglie trivariate e sulla loro equivalenza.

5. Problemi Aperti

Gli autori identificano diverse direzioni future:

Trovare una caratterizzazione algebrica esplicita (es. tramite la norma) per i parametri $a$ validi quando $7 \mid m$ (caso in cui $a=1$ non funziona).
Estendere le costruzioni a dimensioni pari ( $m$ pari), dove il criterio della traccia usato in questo lavoro fallisce.
Generalizzare le costruzioni a $n$ variabili con $n > 3$ .
Investigare se le permutazioni trovate computazionalmente per $m=3$ si estendano a famiglie infinite.

In sintesi, questo articolo rappresenta un avanzamento significativo nella teoria delle funzioni APN, fornendo non solo nuove famiglie di permutazioni, ma anche gli strumenti teorici per classificarle e dimostrarne l'inequivalenza rispetto allo stato dell'arte.