On the Walsh spectra of quadratic APN functions

Sintesi Tecnica: Sugli Spettri di Walsh di Funzioni Quadratiche APN

Enunciato del Problema
Le funzioni Non Lineari Perfettamente Quasi (APN) sono componenti critici nei sistemi crittografici simmetrici, fornendo una resistenza ottimale agli attacchi differenziali. Una proprietà fondamentale di queste funzioni è la loro linearità, determinata dal loro spettro di Walsh. Mentre la distribuzione delle ampiezze (e quindi lo spettro di Walsh) delle funzioni quadratiche APN è completamente caratterizzata per dimensioni $n$ dispari, il caso per $n$ pari rimane in gran parte aperto. L'unica vincolo generale noto per $n$ pari è derivato dal quarto momento della trasformata di Walsh. Questo articolo affronta il vuoto nella comprensione degli spettri di Walsh possibili delle funzioni quadratiche APN $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ dove $n$ è pari, cercando specificamente di derivare condizioni più forti sulle loro distribuzioni di ampiezza.

Metodologia
Gli autori stabiliscono due nuove connessioni geometriche tra funzioni quadratiche APN e geometria finita:

1. Partizioni di Spazio Vettoriale: Il documento dimostra che la distribuzione delle ampiezze di una funzione quadratica APN corrisponde univocamente a una partizione dello spazio vettoriale dello spazio ambiente $\mathbb{F}_2^n$. Nello specifico, le funzioni componenti non banali e non piegate di $F$ sono associate a sottospazi in una partizione in cui la dimensione di ciascun sottospazio è direttamente collegata all'ampiezza della funzione componente corrispondente.
2. Insiemi di Blocco: L'insieme delle componenti non banali e non piegate, denotato $N_F$, è mostrato formare un tipo specifico di insieme di blocco nello spazio proiettivo $PG(n-1, 2)$. Crucialmente, gli autori dimostrano che l'intersezione di $N_F$ con qualsiasi sottospazio di dimensione $n/2$ deve contenere un numero dispari di punti.

Sfruttando teoremi consolidati sulle partizioni di spazi vettoriali e sugli insiemi di blocco (in particolare i risultati riguardanti le "code" delle partizioni e gli insiemi di blocco minimi), gli autori traducono questi vincoli geometrici in limiti algebrici sulle distribuzioni di ampiezza delle funzioni quadratiche APN.

Contributi e Risultati Chiave

• Connessione alle Partizioni di Spazio Vettoriale (Sezione II):

  • Il Teorema II.4 stabilisce che se una funzione componente $F_b$ ha ampiezza $2^{(n+k)/2}$, corrisponde a un sottospazio di dimensione $k$ in una partizione di spazio vettoriale di $\mathbb{F}_2^n$.
  • Questa connessione permette l'applicazione di condizioni di impacchettamento e limiti dimensionali dalla teoria delle partizioni.
  • Teorema II.10: Una funzione quadratica APN può avere al massimo una funzione componente con ampiezza maggiore di $2^{3n/4}$. Se tale componente esiste, tutte le altre devono avere ampiezza al massimo $2^{(2n-l)/2}$, dove $l$ è l'esponente dell'ampiezza massima.
  • Proposizioni II.14–II.16: Nuovi limiti inferiori sul numero di componenti non piegate ($|N_F|$) sono derivati basandosi sulla linearità e sulla presenza di ampiezze specifiche.

• Connessione agli Insiemi di Blocco (Sezione III):

  • Corollario III.3: L'insieme $N_F$ è un insieme di blocco in $PG(n-1, 2)$ rispetto agli spazi di dimensione $(n/2)$, con la proprietà aggiuntiva che ogni tale spazio interseca $N_F$ in un numero dispari di punti.
  • Teorema III.9: Questo è il primo limite superiore non banale e generale sul numero di funzioni componenti piegate per una funzione quadratica APN. Nello specifico, per $n \ge 6$, il numero di componenti non piegate soddisfa $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$. L'uguaglianza è possibile solo se $n=8$. Di conseguenza, il numero di componenti piegate è al massimo $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$.

• Sintesi e Analisi Dimensionale (Sezione IV):

  • Combinando i vincoli delle partizioni e degli insiemi di blocco, gli autori eliminano diverse distribuzioni di ampiezza teoricamente possibili.
  • Teorema IV.1: Le partizioni di spazio vettoriale di tipo $[(n/2)^{2^{n/2+1}}]$ (una $(n/2)$-spalmatura) non corrispondono a nessuna funzione quadratica APN.
  • Teorema IV.5: Per $n=8$, il documento restringe le distribuzioni di ampiezza possibili a un elenco specifico (escludendo la partizione banale e la 4-spalmatura), riducendo il numero di potenziali spettri di Walsh estesi a al massimo 18 tipi distinti.
  • Proposizione IV.4: Il documento confronta la forza dei limiti inferiori derivati su $|N_F|$ attraverso diversi intervalli di parametri, identificando quale limite è dominante in base alla linearità della funzione.

• Equivalenza e Permutazioni (Sezione V):

  • Il documento analizza come queste strutture si comportano sotto l'equivalenza EA e l'equivalenza CCZ.
  • Corollario V.6: Se una funzione quadratica APN è CCZ-equivalente a una permutazione, non può avere poche componenti non piegate; nello specifico, $|N_F| \ge 3(2^{n/2}-1)$, e $N_F$ deve essere un insieme di blocco triplo.

Significato e Affermazioni
Il documento afferma di fornire le prime condizioni generali sugli spettri di Walsh delle funzioni quadratiche APN oltre al ben noto limite del quarto momento. Collegando le proprietà algebriche di queste funzioni alle strutture combinatorie delle partizioni di spazi vettoriali e degli insiemi di blocco, gli autori derivano vincoli forti sulle possibili distribuzioni di ampiezza.

Gli autori affermano esplicitamente che i loro risultati:

1. Dimostrano che una funzione quadratica APN può avere al massimo una componente con ampiezza maggiore di $2^{3n/4}$.
2. Forniscono il primo limite superiore non banale sul numero di componenti piegate.
3. Offrono condizioni per determinare se una funzione è CCZ-equivalente a una permutazione basandosi sul suo numero di componenti piegate.
4. Elenca sistematicamente tutte le possibili distribuzioni di ampiezza per piccole dimensioni pari (specificamente $n=6, 8, 10$), evidenziando quali sono realizzate e quali rimangono problemi aperti.

Il documento conclude elencando problemi aperti, inclusa l'esistenza di funzioni APN con specifiche distribuzioni di ampiezza in dimensione 8 e la ricerca di famiglie infinite di funzioni quadratiche APN con spettri di Walsh non classici. Gli autori mantengono un tono modesto, notando che, sebbene abbiano escluso molte possibilità, la classificazione completa degli spettri di Walsh per le funzioni quadratiche APN rimane una sfida aperta.