Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

Riepilogo Tecnico: Derandomizzazione Parziale per la Condivisione del Segreto di Shamir Resiliente alle Fughe di Informazioni su Campi di Ordine Composto

1. Definizione del Problema

Il documento affronta la costruzione di luoghi di valutazione espliciti per schemi di condivisione del segreto di Shamir (SSS) che siano resilienti contro la fuga di bit fisici (physical-bit leakage) su campi di ordine composto ($\mathbb{F}_{p^d}$ dove $d \ge 2$).

Nello schema SSS standard, un segreto è condiviso tra $n$ parti tali che qualsiasi gruppo di $k$ possa ricostruirlo. Le costruzioni randomizzate (scegliendo i luoghi di valutazione uniformemente a caso) sono note per essere statisticamente sicure contro la fuga locale, ma richiedono una sorgente di casualità pubblica affidabile. Nella pratica, un avversario potrebbe influenzare il seme casuale, indirizzando lo schema verso luoghi di valutazione vulnerabili.

Il lavoro precedente ha stabilito che:

• Su campi primi ($\mathbb{F}_p$), i luoghi di valutazione scelti casualmente garantiscono la resilienza alle fughe con alta probabilità.
• Su campi composti ($\mathbb{F}_{p^d}$), Nguyen (EUROCRYPT 2025) ha stabilito una dicotomia perfetta: qualsiasi schema di condivisione del segreto basato su codici lineari è o perfettamente sicuro (distanza statistica 0) o completamente insicuro contro la fuga di bit fisici.
• Tuttavia, per i campi composti, non era nota alcuna famiglia esplicita e deterministica di luoghi di valutazione per $k > 2$ o per regimi di blocco multiplo generali. Le esistenti costruzioni esplicite per campi primi si basavano su proprietà di estrazione di bit non lineari che non si applicano alle mappe di coordinate lineari dei campi composti.

La sfida centrale è derandomizzare la scelta dei luoghi di valutazione (riducendo l'entropia necessaria per specificarli) mantenendo al contempo la perfetta sicurezza contro la fuga di bit fisici nel contesto dei campi composti.

2. Metodologia e Costruzione

L'autore propone una strategia di derandomizzazione parziale. Invece di selezionare $n$ punti di valutazione indipendenti e casuali, costruisce i luoghi di valutazione come le iterazioni di una funzione razionale $\Phi$ applicata a un punto base scelto casualmente $x_0$.

La Costruzione:

• Configurazione del Campo: Sia $\mathbb{F} = \mathbb{F}_{p^d}$ con un elemento primitivo $\alpha$.
• Operatore di Passo: Definire la trasformazione di Möbius $\Phi(x) = \frac{\alpha x}{x + 1}$.
• Luoghi di Valutazione: I $n$ luoghi di valutazione sono definiti come $x_j = \Phi^j(x_0)$ per $j = 0, \dots, n-1$, dove $x_0 \in \mathbb{F}^*$ è un punto base scelto casualmente.
• Riduzione dell'Entropia: Specificare lo schema richiede solo $d \log p$ bit (per scegliere $x_0$), una riduzione significativa rispetto ai $nd \log p$ bit richiesti per $n$ punti casuali indipendenti.

Intuizione Strutturale Chiave:
L'analisi della sicurezza si basa sui poli distinti delle iterazioni di $\Phi$.

• $\Phi^0(x) = x$ ha un polo in $\infty$.
• Per $j \ge 1$, $\Phi^j(x)$ ha un polo in un punto finito distinto in $\mathbb{F}^*$.
• Questa "distintività dei poli" è cruciale. L'autore la mette a confronto con il candidato $\Psi(x) = \alpha x$ (pura dilatazione), dove tutte le iterazioni condividono lo stesso polo in $\infty$, causando il collasso dell'argomento di sicurezza.

3. Approccio Tecnico

La dimostrazione procede in tre fasi, sfruttando la dicotomia perfetta stabilita da Nguyen (2025):

1. La Dicotomia Perfetta (Fase 1):
   Il documento utilizza il fatto che l'estrazione delle coordinate in $\mathbb{F}_{p^d}$ è $\mathbb{F}_p$-lineare. Di conseguenza, la mappa di fuga è lineare. Ciò implica che la distanza statistica tra le distribuzioni di fuga per diversi segreti è o 0 o 1. La perfetta sicurezza è raggiunta se e solo se la mappa di fuga è suriettiva. Questa condizione è equivalente al fatto che una matrice di test $\Theta_{\vec{i}}$ (derivata dai luoghi di valutazione e dal pattern di fuga) abbia rango pieno su $\mathbb{F}_p$.

2. Non degenerazione della frazione parziale (Fase 2):
   Per dimostrare che la matrice di test ha rango pieno, l'autore deve mostrare che nessuna combinazione lineare non banale delle potenze dei luoghi di valutazione si annulla. Definiscono una funzione razionale $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$.
   Utilizzando la decomposizione in frazioni parziali, sfruttano i poli distinti di $\Phi^j$. Poiché i poli sono distinti, il residuo di $G_\ell$ in un polo specifico è determinato da un singolo termine della somma. Se $G_\ell$ fosse identicamente zero, tutti i coefficienti dovrebbero annullarsi. Questo argomento di "non degenerazione" limita il numero di punti base "cattivi" $x_0$ che causano il fallimento della condizione di rango.

3. Estensione a blocchi multipli (Fase 3):
   L'argomento viene esteso alla fuga a blocchi multipli (dove vengono estratti più coordinate per ogni quota). L'autore gestisce i coefficienti di campo derivanti dalle combinazioni lineari all'interno delle quote, dimostrando che l'argomento della frazione parziale rimane valido a patto che il pattern di fuga sia "ammissibile" (posizioni di blocco distinte per ogni quota).

4. Risultati Chiave

Teorema 1.1 (Sicurezza Perfetta contro la Fuga a Blocco Singolo):
Per parametri $n = O(d / \log_p d)$ e per qualsiasi soglia $k \ge 2$, esiste un insieme di "punti base cattivi" $Bad \subset \mathbb{F}^*$ la cui dimensione è $|Bad| \le n + n(dp)^n$. Per ogni $x_0 \notin Bad$, lo schema che utilizza i luoghi di valutazione $x_j = \Phi^j(x_0)$ è perfettamente sicuro (distanza statistica esattamente 0) contro qualsiasi pattern di fuga a blocco singolo.

• Ciò implica la perfetta sicurezza contro la fuga di un singolo bit fisico per quota per qualsiasi numero primo $p$.
• Un buon $x_0$ è garantito quando $d > n(1 + \log_p d) + \log_p(2n)$.

Teorema 1.2 (Fuga a Blocchi Multipli):
Per un pattern di fuga ammissibile fissato con $M$ blocchi totali estratti, la dimensione del insieme cattivo è limitata da $n + n \cdot p^M$. Un buon $x_0$ esiste se $M < d - \log_p(2n)$.

• Per la sicurezza universale contro tutti i pattern con $\le M$ blocchi, il limite è $|Bad| \le n + n(dpe)^M$, con esistenza garantita quando $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$.

Classificatore:
Il documento fornisce un classificatore esplicito (Algoritmo 1) che, dato un candidato $x_0$, verifica la condizione di rango pieno per tutti i pattern di fuga. Questo funge da test solido per certificare la sicurezza della costruzione strutturata.

5. Significato e Confronto

Il documento rivendica i seguenti contributi e distinzioni:

• Sicurezza Perfetta vs. Sicurezza Statistica: A differenza delle precedenti costruzioni randomizzate su campi composti che offrivano sicurezza statistica ($\epsilon = 2^{-\Omega(d)}$), questa costruzione raggiunge la sicurezza perfetta (distanza statistica 0) per un regime ristretto di parametri.
• Derandomizzazione: Riduce la casualità necessaria per specificare lo schema da $nd \log p$ bit a $d \log p$ bit, limitando i luoghi di valutazione a una famiglia a un solo parametro (l'orbita di $\Phi$).
• Costruzione Esplicita: Fornisce la prima famiglia esplicita di luoghi di valutazione per $k > 2$ su campi composti che resiste alla fuga di bit fisici, andando oltre il paradigma dei "luoghi casuali".
• Limitazioni e Compromessi:
  • Il numero di parti $n$ è limitato a $O(d / \log_p d)$, mentre le costruzioni randomizzate supportano $O(dk / \log_p d)$. L'autore ipotizza che questa perdita del fattore-$k$ sia inerente alle costruzioni a singolo parametro.
  • L'universalità per blocchi multipli è attualmente limitata da un collo di bottiglia nella enumerazione dei pattern, che risulta in limiti esponenziali per il set cattivo in $M$.
  • La costruzione si basa sulla specifica struttura algebrica della trasformazione di Möbius $\Phi(x) = \alpha x / (x+1)$; l'alternativa dilatazione $\alpha x$ fallisce nel fornire sicurezza.

Il lavoro non pretende di risolvere il problema della derandomizzazione per tutti i regimi di parametri o di fornire un limite polinomiale per l'universalità a blocchi multipli, identificandoli come problemi aperti. Il contributo primario è una derandomizzazione parziale rigorosa che raggiunge la perfetta sicurezza in un regime specifico e praticamente rilevante, sfruttando i poli distinti delle iterazioni razionali.