🔢 mathematics

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

Questo articolo presenta una ricerca computazionale ibrida che combina il campionamento casuale e l'enumerazione di basi di Gröbner all'interno di un particolare sottospazio di auto-equivalenza a 40 dimensioni per scoprire 566 funzioni APN quadratiche in dimensione 8, incluse tre classi di equivalenza CCZ precedentemente sconosciute che erano state trascurate da precedenti database esaustivi.

Autori originali: Oleksandr Kuznetsov

Pubblicato 2026-06-11

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Oleksandr Kuznetsov

Articolo originale sotto licenza CC BY 4.0 (http://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

Immagina di cercare un tipo di grimaldello incredibilmente raro (chiamato funzione APN) all'interno di un enorme magazzino buio. Questo magazzino rappresenta tutte le possibili funzioni matematiche di una certa dimensione. Il problema è che il magazzino è così vasto (contiene più possibilità di quante siano gli atomi nell'universo) che se iniziassi semplicemente a camminare a caso, probabilmente non troveresti nemmeno un singolo grimaldello in tutta la tua vita.

Questo articolo descrive una nuova e intelligente strategia per trovare questi rari grimaldetti usando una "torcia" e un "magnete" per navigare in una specifica, più piccola sezione del magazzino che prima era stata ritenuta vuota.

Ecco la suddivisione della loro scoperta utilizzando semplici analogie:

1. Il Problema: L'Ago nel Pagliaio Cosmico

Nel mondo della crittografia (la scienza dei codici segreti), questi "grimaldelli" sono strumenti matematici speciali usati per cifrare i dati in modo che non possano essere decifrati dagli hacker. Per molto tempo, i matematici hanno cercato di trovarne di nuovi, migliori, per una specifica dimensione di dati (8 bit).

Il Vecchio Metodo: Ricercatori precedenti hanno cercato di trovarli costruendo un enorme albero di possibilità, controllando ramo per ramo. Hanno guardato una sezione specifica e organizzata del magattino (uno "spazio sottostante di auto-equivalenza") e hanno concluso: "Qui non c'è nulla". Hanno smesso di cercare.
La Realtà: Gli autori di questo articolo dicono: "Aspetta un momento. Quella sezione non è vuota. Avete solo mancato gli oggetti perché il vostro metodo di scalata dell'albero era troppo rigido".

2. La Nuova Strategia: La Torcia e il Magnete

Gli autori hanno sviluppato un processo in due fasi per trovare questi grimaldetti nascosti:

Fase 1: La Torcia (Campionamento Casuale in una Zona Strutturata)
Inve invece di cercare in tutto l'universo, si sono concentrati su una specifica, organizzata "stanza" a 40 dimensioni all'interno del magazzino. Si sono resi conto che, sebbene questa stanza sia minuscola rispetto all'intero magazzino, i "grimaldetti" sono in realtà molto più comuni all'interno di questa stanza specifica che altrove.
Hanno usato una mappa speciale (chiamata parametrizzazione RREF) per attraversare questa stanza casualmente. Hanno trovato centinaia di grimaldetti "centrali" che erano lì, in attesa di essere scoperti.
Fase 2: Il Magnete (La Ricerca della Base di Gröbner)
Questo è il trucco magico. Una volta trovato un grimaldello "centrale", non si sono fermati. Hanno usato uno strumento matematico potente chiamato base di Gröbner (pensa a un super-magnete) per scansionare il vicinato immediato attorno a quel centro.

Ecco la parte sorprendente: il magnete non ha solo trovato altri grimaldetti nella stessa stanza. Ha estratto nuovi grimaldetti che si nascondevano nelle stanze adiacenti, fuori dalla sezione organizzata in cui avevano iniziato.

Analogia: Immagina di trovare una moneta rara in un cassetto specifico. Usi un magnete per scansionare il cassetto e, improvvisamente, il magnete tira fuori altre tre monete rare che erano rimaste incastrate sul fondo del cassetto, anche se quelle monete appartengono tecnicamente a un cassetto diverso.

3. La Scoperta: Nuove Classi di Tesori

Usando questo metodo, il team ha trovato 566 nuovi grimaldetti. Li ha divisi in sei gruppi (classi):

Due gruppi erano tipi "noti" (come le famose funzioni Gold). Questi fungevano da portali. Quando gli autori hanno usato questi tipi noti come punto di partenza, il "magnete" ha tirato fuori i nuovi tipi sconosciuti.
Quattro gruppi erano completamente nuovi. Non erano mai stati visti prima.
- Un gruppo (Classe A) è stato trovato direttamente all'interno della stanza organizzata.
- Tre gruppi (Classi B, C e D) sono stati trovati fuori dalla stanza, ma erano scopribili solo perché il "magnete" era attaccato ai noti grimaldetti "portale" all'interno della stanza.

4. La Prova: Perché è Importante

Gli autori non si sono limitati a ipotizzare che fossero nuovi. Hanno usato un sistema di "impronta digitale" (chiamato invariante della derivata ortogonale) per controllare le loro scoperte contro i più grandi database del mondo, che contengono milioni di grimaldetti noti.

Risultato: I loro quattro nuovi gruppi non corrispondevano a nessuna delle milioni di voci esistenti. Sono genuinamente nuovi.
Il Mito della "Stanza Vuota": Hanno dimostrato che i ricercatori precedenti avevano torto nel dire che la stanza fosse vuota. La stanza non era vuota; il precedente metodo di ricerca semplicemente non riusciva a vedere gli oggetti perché li guardava uno alla volta, mentre questo nuovo metodo guarda l'intero vicinato contemporaneamente.

5. La Grande Lezione: Il Fenomeno del "Portale"

La lezione più importante non è solo l'aver trovato i nuovi grimaldetti, ma come sono stati trovati.
Gli autori hanno scoperto che non puoi semplicemente scegliere un grimaldello casuale e sperare di trovarne altri nelle vicinanze. Devi partire da un tipo molto specifico e strutturato (le funzioni "Gold" all'interno della stanza organizzata).

L'Analogia: Se provi a usare un magnete su un pezzo di spazzatura casuale nel magazzino, non succede nulla. Ma se usi il magnete su un oggetto "portale" specifico, esso rivela un intero mondo nascosto di nuovi oggetti che prima erano invisibili.

Riassunto

Questo articolo parla di trovare tesori matematici nascosti in un luogo che tutti credevano vuoto. Usando una mappa più intelligente per trovare un punto di partenza e un potente "magnete" matematico per scansionare i dintorni, gli autori hanno trovato 566 nuovi strumenti crittografici, inclusi quattro intere famiglie che nessuno aveva mai visto prima. Hanno dimostrato che a volte, per trovare il nuovo, devi stare sulle spalle del noto, ma hai bisogno degli strumenti giusti per vedere cosa si nasconde proprio oltre il confine.

Sintesi Tecnica: Funzioni APN Quadratiche in Dimensione 8 tramite Ricerca di Base di Gröbner in un Sottospazio di Auto-equivalenza

Enunciato del Problema
La classificazione delle funzioni Almost Perfect Nonlinear (APN) su $\mathbb{F}_{2^n}$ fino all'equivalenza CCZ è un problema centrale in crittografia, particolarmente per $n=8$ . Mentre la classificazione è completa per $n \leq 6$ , per $n=8 rimane parziale. Lo spazio di ricerca per le funzioni APN quadratiche è vastissimo ( $2^{224}$ possibili vettori di coefficienti), rendendo l'esecuzione di una ricerca casuale globale impraticabile a causa di una densità stimata di funzioni APN di circa $2^{-n}$ . Gli sforzi sistematici precedenti, come la ricerca ad albero ricorsiva di Beierle, Brinkmann e Leander (BBL2021), hanno esplorato sottospazi algebrici strutturati definiti da vincoli di auto-equivalenza. Nello specifico, BBL2021 ha riportato il ritrovamento di zero funzioni APN all'interno del sottospazio di auto-equivalenza di 40 dimensioni $V_A$ associato a un automorfismo lineare $A$ di ordine 5 (indice di classe 22). Questo articolo investiga se tale sottospazio contenga effettivamente nessuna funzione APN o se il precedente metodo di ricerca non sia riuscito a individuarle.

Metodologia
Gli autori propongono una pipeline computazionale a due fasi che combina il campionamento casuale con l'enumerazione algebrica per esplorare $V_A$ in modo più efficace rispetto alla precedente ricerca ad albero.

Fase 1: Campionamento Casuale tramite Parametrizzazione RREF
Gli autori costruiscono una parametrizzazione esplicita in Forma Echelonata Ridotta per Righe (RREF) del sottospazio di 40 dimensioni $V_A = \{F : F \circ A = A \circ F\}$ . Ciò riduce lo spazio di ricerca da $2^{224}$ a $2^{40}$ . All'interno di questo sottospazio, la densità empirica delle funzioni APN è stata trovata essere circa $10^{-4}$ (circa 1 funzione APN ogni 11.000 campioni casuali), rendendo il campionamento mirato fattibile. Gli autori eseguono un campionamento casuale per identificare i "centri APN" (funzioni in $V_A$ che sono APN).
Fase 2: Calcolo della Fetta di Base di Gröbner
Per ogni centro APN trovato nella Fase 1, gli autori definiscono un iperpiano affine di 24 dimensioni (una "fetta NL=4") che passa per quel centro. Ciò viene ottenuto fissando 200 dei 224 coefficienti della Forma Normale Algebrica (ANF) (specificamente quelli corrispondenti a coppie con indici $p \leq 4$ ) ai valori del centro, lasciando 24 coefficienti come incognite.
La condizione APN per le 255 differenze non nulle viene codificata come un sistema di equazioni polinomiali sull'anello booleano. Gli autori utilizzano il sistema di algebra computazionale Magma per calcolare una base di Gröbner per questo sistema.

Se il sistema è incompatibile, la fetta non contiene altre funzioni APN.
Se il sistema ha soluzioni, l'enumerazione tramite base di Gröbner trova tutte le funzioni APN all'interno di quella specifica iperpiano di 24 dimensioni.
Fondamentalmente, mentre il centro è garantito essere in $V_A$ , le soluzioni trovate dal passaggio della base di Gröbner non sono vincolate a $V_A$ ; esse possono trovarsi al di fuori del sottospazio di auto-equivalenza.

Classificazione e Verifica
Le funzioni trovate vengono classificate utilizzando l'invariante dell'orto-derivata $\sigma(F)$ , che è stato dimostrato essere un invariante CCZ completo per le funzioni APN quadratiche (tramite il teorema di Yoshiara e i risultati di Canteaut et al.). Gli autori eseguono confronti in streaming delle loro firme contro tre database principali: la compilazione pre-2020 di BBL2021, il database Beierle et al. 2025 (che contiene circa 3,8 milioni di funzioni) e le funzioni Gold classiche.

Risultati Chiave
Gli autori hanno eseguito la pipeline su 428 distinte fette di 24 dimensioni (lo 0,65% del totale di $2^{16}$ possibili fette in $V_A$ ).

Scoperta di Nuove Classi: La ricerca ha prodotto 566 funzioni APN quadratiche uniche appartenenti a sei classi di equivalenza CCZ.
- Quattro Nuove Classi (A, B, C, D): Queste 500 funzioni (362 nella Classe A, 72 in B, 36 in C, 30 in D) non sono presenti nel database Beierle 2025, nel database BBL2021 pre-2020 o nelle famiglie Gold classiche.
- Due Classi Note (E, F): Queste corrispondono alle funzioni Gold $x^3$ e $x^9$ (e le loro orbite di Frobenius), fungendo da controlli per validare la pipeline.
Risultati Strutturali:
- Appartenenza al Sottospazio: Un test di appartenenza ( $F \circ A = A \circ F$ ) ha rivelato che la Classe A, E e F giacciono interamente in $V_A$ . Tuttavia, le Classi B, C e D giacciono interamente fuori da $V_A$ .
- Il Fenomeno del "Gateway": Le 138 funzioni nelle nuove classi esterne (B, C, D) sono state trovate esclusivamente in fette centrate su funzioni Gold (Classi E e F) che risiedono in $V_A$ . Le fette centrate su funzioni della Classe A non hanno prodotto vicini al di fuori di $V_A$ .
- Fallimento di Semi Alternativi: Esperimenti comparativi utilizzando 532 funzioni APN dal database Beierle 2025 (che sono al di fuori di $V_A$ ) come centri di fetta hanno prodotto zero vicini APN trovati. Ciò suggerisce che la capacità di "gateway" per scoprire nuove classi tramite la fetta di base di Gröbner è specifica delle funzioni all'interno del sottospazio di auto-equivalenza, non una proprietà generica di tutte le funzioni APN.

Significatività e Rivendicazioni
L'articolo rivendica diversi contributi significativi al campo della classificazione delle funzioni APN quadratiche:

Correzione di Risultati Precedenti: Gli autori dimostrano che il sottospazio di auto-equivalenza $V_A$ (indice di classe 22), precedentemente riportato da BBL2021 come privo di funzioni APN, contiene in realtà almeno quattro classi CCZ di funzioni APN quadratiche. Il fallimento della ricerca ad albero di BBL2021 è attribuito alla sua strategia di potatura dei rami, che potrebbe aver eliminato soluzioni valide in questo sottospazio strutturato, mentre l'approccio della base di Gröbner esegue un'enumerazione completa in ogni fetta.
Scoperta di Nuove Funzioni: Il lavoro fornisce una prova rigorosa (tramite l'invariante dell'orto-derivata) che esistono quattro nuove classi CCZ di funzioni APN quadratiche per $n=8$ , distinte dai circa 3,8 milioni di funzioni nel più grande database noto.
Innovazione Metodologica: Il lavoro introduce un meccanismo di "navigazione GB". Esso postula che, sebbene la ricerca globale sia impossibile, si possa sfruttare sottospazi strutturati con una densità APN più elevata per trovare funzioni "seme". Il passaggio della base di Gröbner agisce quindi come un enumeratore locale, capace di uscire dal sottospazio per trovare nuove classi. Gli autori sottolineano che questo meccanismo non è generico; esso dipende dalla specifica struttura algebrica del sottospazio di auto-equivalenza, come dimostrato dal fallimento delle funzioni non appartenenti al sottospazio nell'agire come semi produttivi.
Completezza dell'Orto-Derivata: Il lavoro rafforza l'utilità della firma dell'orto-derivata come invariante CCZ esatto per le funzioni quadratiche, permettendo una classificazione rigorosa senza test a coppie esaustivi.

Gli autori concludono che il loro approccio offre un programma sistematico per estendere la classificazione delle funzioni APN quadratiche esplorando altri indici di classe di BBL2021 e utilizzando la tecnica di fatiamento della base di Gröbner per navigare nel panorama APN.