Sugli spettri di Walsh delle funzioni APN quadratiche

Informazioni Fondamentali

• ID Articolo: 2510.12008
• Titolo: On the Walsh spectra of quadratic APN functions
• Autori: Sophie Hannah Bénéteau (University of Florida), Nicolas Goluboff (University of Massachusetts Amherst), Lukas Kölsch (University of South Florida), Divyesh Vaghasiya (University of South Florida)
• Classificazione: math.CO cs.IT math.IT
• Data di Pubblicazione: 15 ottobre 2025 (preprint arXiv)
• Link dell'Articolo: https://arxiv.org/abs/2510.12008

Riassunto

Le funzioni APN (Almost Perfect Nonlinear) svolgono un ruolo centrale nella progettazione di cifrari a blocchi, rappresentando le funzioni ottimali per resistere agli attacchi differenziali. Una delle proprietà più importanti delle funzioni APN è la loro linearità, direttamente correlata allo spettro di Walsh della funzione. Questo articolo stabilisce due nuovi collegamenti che consentono di derivare condizioni forti sullo spettro di Walsh delle funzioni APN quadratiche. L'articolo dimostra che la trasformata di Walsh di una funzione APN quadratica $F$ operante su $n=2k$ bit è univocamente associata a una partizione dello spazio vettoriale di $\mathbb{F}_2^n$ e a specifici insiemi bloccanti nello spazio proiettivo corrispondente $PG(n-1,2)$. Questi collegamenti consentono di provare molteplici risultati sullo spettro di Walsh di $F$, ad esempio dimostrando che $F$ può avere al massimo una funzione componente con ampiezza maggiore di $2^{\frac{3}{4}n}$, e trovando il primo limite non banale sul numero di funzioni componenti piegate delle funzioni APN quadratiche.

Contesto di Ricerca e Motivazione

Importanza del Problema

1. Applicazioni Crittografiche: Le funzioni APN sono blocchi costruttivi fondamentali nella progettazione di sistemi crittografici simmetrici, in particolare nelle reti di sostituzione-permutazione (SPN) dei cifrari a blocchi, fornendo resistenza ottimale agli attacchi differenziali.
2. Sfide Teoriche: Sebbene la distribuzione dell'ampiezza delle funzioni APN quadratiche nel caso di dimensione dispari sia stata completamente determinata (tutte le componenti non banali hanno ampiezza $2^{\frac{n+1}{2}}$), il caso di dimensione pari rimane un problema aperto.
3. Limitazioni Attuali:
   • Per $n$ pari, i soli vincoli noti sull'ampiezza provengono dalla caratterizzazione del momento di quarto ordine della trasformata di Walsh
   • Mancanza di limiti non banali sul numero di funzioni componenti piegate delle funzioni APN quadratiche
   • Comprensione insufficiente della struttura profonda dello spettro di Walsh

Motivazione della Ricerca

Questo articolo mira a approfondire la comprensione delle proprietà strutturali dello spettro di Walsh stabilendo nuovi collegamenti tra funzioni APN quadratiche e oggetti geometrici (partizioni di spazi vettoriali e insiemi bloccanti), derivando così condizioni di vincolo più forti.

Contributi Principali

1. Stabilimento del Collegamento con Partizioni di Spazi Vettoriali: Dimostra l'esistenza di una corrispondenza univoca tra la distribuzione dell'ampiezza di una funzione APN quadratica $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ ($n$ pari) e una partizione dello spazio vettoriale di $\mathbb{F}_2^n$.
2. Costruzione della Teoria degli Insiemi Bloccanti: Dimostra che l'insieme delle funzioni componenti non banali non piegate $N_F$ forma un insieme bloccante speciale nello spazio proiettivo $PG(n-1,2)$.
3. Derivazione di Nuove Condizioni di Vincolo:
   • Dimostra che $F$ può avere al massimo una funzione componente con ampiezza maggiore di $2^{\frac{3}{4}n}$
   • Stabilisce il primo limite non banale sul numero di funzioni componenti piegate
   • Fornisce condizioni necessarie affinché la funzione sia CCZ-equivalente a una permutazione
4. Analisi Completa per Piccole Dimensioni: Esegue un'analisi completa per le dimensioni 6, 8 e 10, determinando tutte le possibili distribuzioni di ampiezza.

Dettagli Metodologici

Definizione del Compito

Studiare la struttura dello spettro di Walsh di funzioni APN quadratiche $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ ($n$ pari), dove:

• Input: Funzione APN quadratica $F$
• Output: Condizioni di vincolo e proprietà strutturali dello spettro di Walsh
• Obiettivo: Comprendere le possibilità e i limiti della distribuzione dell'ampiezza

Quadro Teorico Fondamentale

1. Teoria delle Partizioni di Spazi Vettoriali

Definizione della Funzione Differenziale: Per un elemento non nullo $a \in \mathbb{F}_2^n$, si definisce $D_{F,a}(x) = F(x) + F(x+a)$.

Costruzione dello Spazio Vettoriale: Si definiscono

• $T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}$
• $\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}$
• $V_b = T_b \cup \overline{T_b}$

dove $H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}$.

Teorema Principale (Teorema 2.4): L'ampiezza di $F_b$ è $2^{\frac{n+\dim(V_b)}{2}}$.

2. Teoria degli Insiemi Bloccanti

Proprietà degli Insiemi Bloccanti: L'insieme delle funzioni componenti non banali non piegate $N_F$ forma un insieme bloccante rispetto agli spazi $(n/2)$-dimensionali in $PG(n-1,2)$, con intersezione di cardinalità dispari con ogni spazio $(n/2)$-dimensionale.

Risultato Chiave: Utilizzando il teorema di Govaerts-Storme sulla dimensione minima degli insiemi bloccanti non banali, si ottiene un limite superiore sul numero di funzioni componenti piegate.

Punti di Innovazione Tecnica

1. Metodo Geometrico: Trasforma per la prima volta il problema dello spettro di Walsh delle funzioni APN quadratiche in un problema geometrico di partizioni di spazi vettoriali e insiemi bloccanti.
2. Caratterizzazione Strutturale: Determina direttamente l'ampiezza della funzione componente $F_b$ attraverso $\dim(V_b)$, stabilendo un collegamento diretto tra la struttura algebrica e le proprietà spettrali.
3. Applicazione Interdisciplinare: Applica abilmente la teoria profonda delle partizioni di spazi vettoriali e degli insiemi bloccanti dalla geometria finita.

Configurazione Sperimentale

Metodi di Verifica Teorica

Questo articolo è principalmente una ricerca teorica, verificando i risultati attraverso:

1. Analisi Completa per Piccole Dimensioni:
   • Dimensione 6: Verifica che tutti i tipi possibili di partizioni di spazi vettoriali corrispondono a funzioni APN quadratiche note
   • Dimensione 8: Determina 18 possibili distribuzioni di ampiezza
   • Dimensione 10: Analizza tutti i casi teoricamente possibili
2. Verifica su Funzioni Note:
   • Verifica di funzioni con spettro di Walsh classico
   • Analisi di funzioni con linearità massima
   • Verifica delle proprietà degli insiemi bloccanti della funzione $x^3$

Strumenti Computazionali

L'articolo utilizza verifiche assistite da computer per:

• Enumerare tutte le possibili partizioni di spazi vettoriali per piccole dimensioni
• Verificare la coerenza dei risultati teorici con funzioni APN note

Risultati Sperimentali

Risultati Teorici Principali

1. Vincoli di Ampiezza (Teorema 2.10)

Risultato: Sia $n$ pari, $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ una funzione APN quadratica con linearità $L(F) = 2^{\frac{n+l}{2}}$ e $l > n/2$, allora:

• $F$ ha esattamente una funzione componente con ampiezza $2^{\frac{n+l}{2}}$
• Tutte le altre componenti hanno ampiezza al massimo $2^{\frac{2n-l}{2}}$
• In particolare, qualsiasi funzione APN quadratica ha al massimo una funzione componente con ampiezza maggiore di $2^{\frac{3n}{4}}$

2. Limite Superiore sulle Funzioni Componenti Piegate (Teorema 3.9)

Risultato: Sia $n \geq 6$ pari, $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ una funzione APN quadratica, allora: $|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ dove l'uguaglianza è possibile solo quando $n=8$.

3. Classificazione Completa per Dimensione 8 (Teorema 4.5)

Per $F: \mathbb{F}_2^8 \to \mathbb{F}_2^8$ funzione APN quadratica, le possibili distribuzioni di ampiezza sono:

• $[0^{190}, 2^{64}, 6^1]$
• $[0^{238-4i}, 2^{5i}, 4^{17-i}]$, dove $1 \leq i \leq 17$

Analisi di Ablazione

1. Confronto dei Limiti (Proposizione 4.4)

Confronta tre diversi limiti inferiori per $|N_F|$:

• Limite della Partizione di Spazi Vettoriali: Più forte quando $k < n/2$
• Limite dell'Insieme Bloccante: Più forte quando $k = n/2$
• Limite della Dimensione: Più forte quando $k > n/2$

2. Analisi di Equivalenza

Dimostra che sotto equivalenza EA:

• Le partizioni di spazi vettoriali mantengono l'equivalenza (Teorema 5.2)
• Gli insiemi bloccanti mantengono l'equivalenza (Teorema 5.1)

Scoperte Importanti

1. Vincoli Strutturali: Lo spettro di Walsh delle funzioni APN quadratiche è soggetto a vincoli geometrici rigorosi, non è arbitrario.
2. Effetto della Dimensione: Con l'aumento della dimensione, le possibili distribuzioni di ampiezza diminuiscono drasticamente.
3. Condizioni di Equivalenza CCZ: Se una funzione quadratica è CCZ-equivalente a una permutazione, allora $|N_F| \geq 3(2^{n/2} - 1)$.

Lavori Correlati

Principali Direzioni di Ricerca

1. Classificazione delle Funzioni APN: Lavori di Carlet, Charpin, Zinoviev e altri
2. Teoria dello Spettro di Walsh: Metodo del momento di quarto ordine e limiti di linearità
3. Partizioni di Spazi Vettoriali: Teoria costruttiva di Heden, Bu e altri
4. Teoria degli Insiemi Bloccanti: Limiti ottimali di Govaerts-Storme

Vantaggi di Questo Articolo

• Stabilisce per la prima volta un collegamento diretto tra lo spettro di Walsh e gli oggetti geometrici
• Fornisce condizioni di vincolo più forti rispetto al classico metodo del momento di quarto ordine
• Unifica i punti di vista algebrico e geometrico

Conclusioni e Discussione

Conclusioni Principali

1. Lo spettro di Walsh delle funzioni APN quadratiche possiede una struttura geometrica profonda
2. Le partizioni di spazi vettoriali e gli insiemi bloccanti forniscono strumenti potenti per comprendere lo spettro di Walsh
3. La maggior parte delle distribuzioni di ampiezza teoricamente possibili non può essere realizzata in pratica

Limitazioni

1. Problemi Costruttivi: La teoria esclude molte possibilità, ma non fornisce nuovi metodi costruttivi
2. Restrizione Dimensionale: I risultati principali si concentrano su dimensioni pari
3. Complessità Computazionale: L'analisi completa per dimensioni elevate rimane difficile

Direzioni Future

L'articolo propone 6 problemi aperti, inclusi:

1. Trovare esempi di distribuzioni di ampiezza mancanti in dimensione 8
2. Migliorare i limiti su $|N_F|$
3. Trovare più tipi di partizioni di spazi vettoriali non realizzabili

Valutazione Approfondita

Punti di Forza

1. Innovazione Teorica: Stabilisce una prospettiva geometrica completamente nuova per comprendere lo spettro di Walsh
2. Sistematicità del Metodo: Studia sistematicamente da due angolazioni: partizioni di spazi vettoriali e insiemi bloccanti
3. Profondità dei Risultati: Ottiene molteplici limiti non banali per la prima volta
4. Completezza dell'Analisi: Esegue un'analisi esaustiva per piccole dimensioni

Insufficienze

1. Mancanza di Costruzioni: I risultati sono principalmente di esclusione, mancano nuove costruzioni di funzioni APN
2. Verifica Computazionale: Alcuni risultati dipendono dalla verifica al computer, le prove teoriche non sono completamente rigorose
3. Limitazioni Applicative: Principalmente contributi teorici, il valore applicativo nella crittografia pratica rimane da verificare

Impatto

1. Valore Accademico: Fornisce nuovi strumenti e prospettive di ricerca per la teoria delle funzioni APN
2. Contributo Metodologico: Il metodo geometrico potrebbe ispirare la ricerca su altri problemi crittografici
3. Problemi Aperti: I problemi proposti indicano direzioni per ricerche future

Scenari Applicabili

• Analisi teorica di funzioni APN quadratiche
• Progettazione e analisi di S-box nella crittografia
• Ricerca sull'applicazione della geometria finita alla crittografia
• Studio della struttura dello spettro di Walsh di funzioni booleane

Bibliografia

L'articolo cita 25 importanti riferimenti che coprono molteplici campi quali la teoria delle funzioni APN, le partizioni di spazi vettoriali e la teoria degli insiemi bloccanti, riflettendo le caratteristiche della ricerca interdisciplinare. I riferimenti chiave includono il trattato sulle funzioni booleane di Carlet, il lavoro sugli insiemi bloccanti di Govaerts-Storme, e la ricerca sulle partizioni di spazi vettoriali di Heden e altri.