The combinatorial structure and value distributions of plateaued functions

Titolo e Contesto

Titolo: La struttura combinatoria e le distribuzioni di valore delle funzioni a plateau.
Autori: Lukas Kolsch (University of South Florida) e Alexandr Polujan (Otto-von-Guericke-Universität Magdeburg).
Data: Marzo 2026 (versione arXiv).

1. Problema e Obiettivo

Le funzioni a plateau (plateaued functions) costituiscono una generalizzazione delle funzioni quadratiche e delle funzioni piegate (bent functions). Sono fondamentali nella crittografia perché molte primitive crittografiche, inclusi la maggior parte dei noti funzioni APN (Almost Perfect Nonlinear) e funzioni quadratiche, rientrano in questa classe.

Il problema centrale affrontato dagli autori è la comprensione delle distribuzioni di valore (value distributions) di queste funzioni, ovvero le dimensioni degli insiemi di preimmagine $F^{-1}(\beta)$. In particolare, il lavoro si concentra su:

• La relazione tra la trasformata di Walsh, la linearità e le proprietà differenziali delle funzioni a plateau.
• L'analisi delle funzioni "quasi bilanciate" (almost balanced), dove tutti i preimmagini hanno la stessa dimensione tranne uno.
• La caratterizzazione delle funzioni $d$-to-1 (dove ogni immagine ha esattamente $d$ preimmagini, tranne una che ne ha 1) e delle funzioni monomiali.
• La struttura combinatoria delle funzioni APN a plateau, con un focus sui limiti della loro distribuzione di valore.

2. Metodologia

Gli autori sviluppano un approccio teorico basato principalmente sulla trasformata di Walsh valutata in $a=0$. A differenza di approcci precedenti che si basavano sulle proprietà differenziali, questo metodo utilizza le proprietà spettrali per derivare informazioni sulle dimensioni degli insiemi di preimmagine.

Gli strumenti matematici chiave includono:

• Relazioni di ortogonalità dei caratteri: Per collegare la trasformata di Walsh alla cardinalità degli insiemi di preimmagine.
• Momenti della trasformata di Walsh: In particolare il secondo momento (relazionato alla somma dei quadrati delle dimensioni delle preimmagini) e il quarto momento (relazionato alla uniformità differenziale).
• Disuguaglianza di Cauchy-Schwarz: Utilizzata per derivare limiti superiori e inferiori per le dimensioni delle preimmagini in funzione dell'imbalance ($N_bF$).
• Teoria dei campi ciclotomici: Utilizzata nel caso di $p$ dispari per dimostrare che certi coefficienti di Walsh devono essere interi.

3. Contributi Chiave e Risultati

A. Limiti Generali e Funzioni Quasi Bilanciate

• Teorema 3.3: Vengono stabiliti limiti superiori e inferiori per la dimensione di ogni insieme di preimmagine $|F^{-1}(\beta)|$ in funzione della dimensione dell'immagine $|Im(F)|$ e dell'imbalance $N_bF$.
• Definizione 3.7: Vengono introdotte le funzioni quasi bilanciate come quelle che raggiungono l'uguaglianza in questi limiti. Queste funzioni sono caratterizzate dal fatto che tutte le preimmagini, tranne una, hanno la stessa dimensione.
• Teorema 4.1: Viene stabilita una connessione forte tra la trasformata di Walsh e l'imbalance per le funzioni surgettive quasi bilanciate. Si dimostra che per tali funzioni, i coefficienti di Walsh $W_F(b, 0)$ sono uguali in modulo per tutti i $b \neq 0$.
• Teorema 4.6: Viene dimostrato che se la dimensione di uscita $m$ è sufficientemente piccola ($m \le n/2$), ogni funzione è equivalente (tramite un'applicazione lineare additiva) a una funzione surgettiva.

B. Funzioni $d$-to-1 e Monomi

• Teorema 5.2: Questo è uno dei risultati principali. Viene dimostrato che una funzione vettoriale $d$-to-1 può essere a plateau solo per valori molto specifici di $d$. Nello specifico, se $F$ è $d$-to-1 e a plateau, allora $d$ deve essere della forma $p^t + 1$ (con $t \ge 1$ e $t | n/2$).
  • Le componenti della funzione sono o "bent" (con ampiezza $p^{n/2}$) o hanno ampiezza $p^{n/2+t}$.
  • La linearità della funzione è determinata esattamente da $L(F) = p^{n/2+t}$.
• Corollario 5.4: Per le funzioni monomiali $F(x) = x^d$, se sono a plateau, allora o sono permutazioni ($\gcd(d, p^n-1)=1$) o sono $(p^t+1)$-to-1.
• Teoremi 5.5 e 5.6: Vengono derivati limiti inferiori per l'uniformità differenziale $\delta$. Per una funzione a plateau che è $(p^t+1)$-to-1, $\delta \ge p^t$. L'uguaglianza $\delta = p^t$ vale se e solo se la funzione è "differenzialmente a due valori" (differentially 2-valued), cioè l'equazione differenziale ha 0 o $p^t$ soluzioni.

C. Costruzioni di Funzioni Quasi Bilanciate

Gli autori forniscono costruzioni esplicite di funzioni a plateau quasi bilanciate:

• Teorema 5.8: Analisi di funzioni monomiali della forma $F(x) = Tr(x^{2^r+1})$ su campi di caratteristica 2, dimostrando che sono quasi bilanciate con dimensioni di preimmagine specifiche.
• Proposizioni 5.9 e 5.10: Analisi delle funzioni di tipo Maiorana-McFarland. Viene mostrato come la scelta appropriata dei blocchi costitutivi (permutazioni e funzioni ausiliarie) possa generare funzioni bilanciate o quasi bilanciate.

D. Struttura delle Funzioni APN a Plateau

• Proposizione 6.3: Vengono stabiliti limiti inferiori e superiori per l'imbalance delle funzioni APN a plateau. Il limite inferiore è raggiunto solo se la funzione ha un numero specifico di componenti bent e bilanciate.
• Teorema 6.7: Risolvendo un problema aperto, gli autori dimostrano che non esistono funzioni APN a plateau con la seconda distribuzione di valore elencata nella classificazione delle funzioni APN con immagine minima (quella con due preimmagini di dimensione 2 e il resto di dimensione 3).
• Teorema 6.8: Viene dimostrato che le funzioni APN a plateau con immagine minima non possono avere componenti bilanciate.

4. Significato e Implicazioni

Questo lavoro è significativo per diversi motivi:

1. Unificazione Teorica: Fornisce un quadro unificato che collega la trasformata di Walsh, l'imbalance e la struttura combinatoria, estendendo risultati noti sulle funzioni bent e quadratiche alla classe generale delle funzioni a plateau.
2. Restrizioni Strutturali: Dimostra che le funzioni a plateau $d$-to-1 sono estremamente rare e soggette a vincoli aritmetici severi (la forma $p^t+1$), il che limita le possibili costruzioni di primitive crittografiche basate su monomi.
3. Risultati Negativi: La dimostrazione dell'impossibilità di certe distribuzioni di valore per le funzioni APN a plateau (Teorema 6.7) restringe lo spazio di ricerca per la costruzione di nuove permutazioni APN, un problema aperto noto come "Big APN problem".
4. Applicazioni Crittografiche: I risultati sono rilevanti per la progettazione di algoritmi crittografici (come cifrari a blocchi e funzioni hash per prove a conoscenza zero, es. Poseidon, Rescue-Prime) che utilizzano funzioni a plateau come mattoni fondamentali, fornendo criteri per valutare la loro sicurezza e le loro proprietà di bilanciamento.

In sintesi, il paper offre strumenti analitici potenti per investigare la struttura interna delle funzioni crittografiche, collegando proprietà spettrali (Walsh) a proprietà combinatorie (distribuzione di valore) e differenziali, con risultati che escludono intere classi di funzioni candidate e ne caratterizzano rigorosamente altre.