Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

Titolo: Crittanalisi della Funzione Pseudo-Random di Legendre su Campi di Estensione

1. Il Problema

La Funzione Pseudo-Random (PRF) basata sul simbolo di Legendre è un primitivo crittografico altamente efficiente, ampiamente utilizzato nei protocolli di Calcolo Multi-Parte (MPC) e nelle Prove a Conoscenza Zero (ZKP) grazie alla sua bassa complessità moltiplicativa.
Mentre la sicurezza della PRF di Legendre sui campi primi $\mathbb{F}_p$ è stata ampiamente studiata, l'interesse recente si è spostato verso la sua istanziazione su campi di estensione $\mathbb{F}_{p^r}$ per ottimizzare il throughput.
Il problema centrale affrontato da questo lavoro è la sicurezza della versione monodimensionale (grado $d=1$) della PRF di Legendre su $\mathbb{F}_{p^r}$. Gli autori ipotizzano che le proprietà algebriche uniche dell'aritmetica polinomiale in questi campi, in particolare l'assenza di "riporto" (carry) nell'addizione, possano creare vulnerabilità strutturali non presenti nei campi primi, rendendo la chiave segreta recuperabile attraverso attacchi passivi e attivi.

2. Metodologia

L'analisi si basa su una rigorosa modellazione matematica e su due modelli di minaccia distinti:

• Modellazione dell'Input: Gli interi sequenziali (contatori) sono mappati in elementi polinomiali di $\mathbb{F}_{p^r}$ tramite una codifica in base-$p$. A differenza dell'aritmetica intera, l'addizione polinomiale in $\mathbb{F}_{p^r}$ avviene coefficiente per coefficiente senza propagazione di riporto verso gradi superiori.
• Modello di Minaccia Passivo: L'attaccante osserva un flusso di bit generato da query additive sequenziali (contatori incrementali).
• Modello di Minaccia Attivo (Chosen-Query): L'attaccante ha accesso a un oracolo e può scegliere le query da inviare al server.
• Strumenti Matematici:
  • Analisi delle proprietà di differenziazione polinomiale.
  • Utilizzo del limite di Hasse-Weil per dimostrare l'assenza di bias statistici, costringendo l'attacco a basarsi sulla struttura algebrica.
  • Sfruttamento dell'omomorfismo moltiplicativo del gruppo $\mathbb{F}^*_{p^r}$ tramite sequenze geometriche.

3. Contributi Chiave

A. Analisi Strutturale e "Frattura Senza Riporto" (No-Carry Fracture)
Gli autori dimostrano che la mappatura polinomiale rompe la continuità delle progressioni aritmetiche. Mentre in $\mathbb{F}_p$ la differenza tra input consecutivi è costante ($\Delta = 1$), in $\mathbb{F}_{p^r}$ la differenza $\Delta_n = X_{n+1} \oplus X_n$ non è costante ma dipende dalla valutazione $p$-adica di $n+1$. Questo crea una serie di "fratture" asincrone che neutralizzano gli attacchi classici a collisione con finestra scorrevole.

B. Attacco Passivo: "Differential Signature" (Firma Differenziale)
Nonostante la frattura, la sequenza delle differenze è deterministicamente periodica.

• Tecnica: Gli autori introducono una tecnica di "bucketing" (raggruppamento) basata sulle "firme differenziali". Un attaccante può raggruppare finestre di sequenze fratturate in base alla loro forma strutturale (il pattern delle differenze).
• Risultato: Questo permette di bypassare la difesa del "no-carry". L'attaccante può recuperare la chiave segreta passivamente con una complessità di $O(U \cdot p^r / M)$, dove $U$ è la distanza di unicità e $M$ il numero di bit osservati.

C. Attacco Attivo: Sequenze Geometriche e Omomorfismo
Questa è la scoperta più devastante per la sicurezza della PRF monodimensionale.

• Tecnica: Un attaccante attivo abbandona l'addizione e interroga il PRF utilizzando una sequenza geometrica generata da un polinomio primitivo $g(x)$ (cioè $X_i = g^i$).
• Meccanismo: Il simbolo di Legendre generalizzato è completamente moltiplicativo. Questo permette di fattorizzare l'output:
  $$L(g^i + K) = L(K) \cdot L(g^{i+j} + 1)$$
  dove $j$ è un logaritmo discreto legato alla chiave $K$.
• Risultato: L'attacco trasforma il problema in uno spostamento di indice (shift) su una sequenza di riferimento universale. Utilizzando un attacco a collisione su tabelle generalizzato, la chiave può essere estratta con complessità puramente $O(p^r / M)$, eliminando completamente la protezione offerta dalla struttura del campo di estensione.

D. Implicazioni per Varianti di Grado Superiore ($d \ge 2$)
Il lavoro dimostra che la versione monodimensionale ($d=1$) è fondamentalmente insicura. Tuttavia, l'analisi suggerisce che l'uso di polinomi di grado superiore ($d \ge 2$) per la chiave (es. $x^2 + K_1x + K_0$) impedisce la fattorizzazione algebrica utilizzata nell'attacco geometrico, rendendo l'attacco a collisione diretto inefficace.

4. Risultati

• Rottura Completa: La PRF di Legendre monodimensionale ($d=1$) su campi di estensione $\mathbb{F}_{p^r}$ è stata dimostrata insicura sia in modelli passivi che attivi.
• Complessità di Attacco:
  • Passivo: $O(U \cdot p^r / M)$
  • Attivo: $O(p^r / M)$
    Questi complessi sono significativamente inferiori alla sicurezza esponenziale attesa, riducendo la sicurezza al limite teorico inferiore.
• Necessità di Grado Superiore: È stato formalmente stabilito che per ottenere sicurezza esponenziale contro riduzioni strutturali in campi di estensione, è assolutamente necessario utilizzare varianti con grado della chiave $d \ge 2$ (e preferibilmente $d \ge 3$ o $4$ per margini di sicurezza robusti).

5. Significato e Impatto

Questo studio è fondamentale per la comunità crittografica che lavora su MPC e ZKP:

1. Avvertimento Critico: Sconsiglia vivamente l'uso della PRF di Legendre monodimensionale su campi di estensione, nonostante la sua efficienza computazionale, poiché la sicurezza è compromessa da proprietà algebriche intrinseche.
2. Nuovi Vettori di Attacco: Introduce concetti innovativi come le "firme differenziali" per attacchi passivi e lo sfruttamento dell'omomorfismo moltiplicativo tramite sequenze geometriche per attacchi attivi, che potrebbero essere applicati ad altri schemi basati su simboli di carattere.
3. Guida per Progettazione Futura: Fornisce una base matematica solida per la progettazione di PRF sicure in contesti di estensione di campo, indicando che l'aumento del grado del polinomio chiave è l'unica via percorribile per mitigare queste vulnerabilità strutturali.
4. Riproducibilità: Il codice sorgente per tutti gli attacchi descritti è stato reso pubblico, permettendo la verifica indipendente e lo sviluppo di contromisure.

In conclusione, il paper dimostra che l'ottimizzazione delle prestazioni tramite l'uso di campi di estensione non deve avvenire a scapito della sicurezza strutturale, e che la transizione da $\mathbb{F}_p$ a $\mathbb{F}_{p^r}$ richiede una revisione fondamentale dei parametri di sicurezza, in particolare passando da chiavi lineari a chiavi polinomiali di grado superiore.