Secret sharing with additive access structures from correlated random variables

Sintesi Tecnica: Condivisione di Segreti con Strutture di Accesso Additive da Variabili Casuali Correlate

Enunciato del Problema
Il documento affronta il problema della condivisione di segreti in un ambiente dinamico in cui l'insieme dei partecipanti autorizzati (la struttura di accesso) evolve nel tempo. I modelli tradizionali di condivisione dei segreti tipicamente assumono una struttura di accesso fissa; se la struttura cambia, i segreti devono essere ridistribuiti, portando a inefficienze. Mentre il modello "Evolving Access Structure" (EAS) permette una crescita monotona, esso assume che i partecipanti si uniscano sequenzialmente e ricevano i segreti tramite canali privati.

Questo lavoro introduce il modello Additive Access Structure (AAS), che differisce dall'EAS in due modi fondamentali:

1. Inizializzazione Simultanea: Tutti i partecipanti sono presenti inizialmente.
2. Fonte di Casualità Correlata: I segreti vengono generati simultaneamente da una fonte di casualità correlata (ad esempio, misurazioni del guadagno del canale nelle reti wireless) piuttosto che essere distribuiti su canali privati.
3. Comunicazione Pubblica: Il dealer comunica con i partecipanti tramite un canale pubblico, privo di rumore e autenticato. Il dealer apprende i cambiamenti alla struttura di accesso (nuovi gruppi autorizzati) solo al momento in cui si verificano e deve adattare la strategia di condivisione dei segreti in modo iterativo.

L'obiettivo è determinare una strategia di condivisione dei segreti che permetta ai gruppi autorizzati di recuperare un segreto con alta affidabilità, garantendo al contempo che i gruppi non autorizzati apprendano informazioni trascurabili, il tutto massimizzando il tasso del segreto (la dimensione del segreto condiviso normalizzata rispetto al numero di osservazioni della sorgente).

Metodologia
Gli autori propongono una strategia di condivisione dei segreti basata sul random binning (binning casuale) adattata per un contesto dinamico. Il nucleo della metodologia prevede:

• Quantized Random Binning: Il dealer osserva una sequenza $Y^n$ da una sorgente correlata $(Y, X_L)$. Per ogni istante temporale $t$, il dealer e i partecipanti utilizzano funzioni di random binning predeterminate ($g_i$ e $h_j$) che mappano le sequenze della sorgente in indici.
• Codifica Iterativa: Ad ogni istante temporale $t$, il dealer determina il numero di indici di binning ($k_t$) da includere nel messaggio pubblico e il numero di indici ($\sigma_t$) da destinare al segreto. Questi conteggi sono scelti in base all'attuale insieme autorizzato $A_t$ e all'insieme non autorizzato $U_t$.
• Specificazione della Strategia A Priori: Un aspetto innovativo della dimostrazione è l'introduzione di un numero quantizzato di binning. Ciò consente la costruzione di una singola strategia di condivisione dei segreti che è interamente specificata a priori. Fondamentalmente, questa strategia non dipende dalla conoscenza di come l'AAS evolverà nei passi temporali futuri; il dealer deve conoscere solo la struttura di accesso corrente per determinare il messaggio e il segreto per quel particolare step.
• Decodifica: I partecipanti autorizzati utilizzano le loro osservazioni locali ($X^n_A$), i messaggi pubblici accumulati e le funzioni di binning per identificare l'unica sequenza della sorgente coerente con i vincoli di tipicità e gli indici di bin ricevuti.

Contributi Chiave e Risultati
Il documento stabilisce i seguenti risultati teorici:

1. Raggiungibilità dei Tassi a Struttura Fissa: Gli autori dimostrano che esiste una strategia per il modello AAS in cui il tasso di segreto raggiungibile in qualsiasi istante $t$ è indipendente dalle strutture di accesso in tutti gli altri istanti temporali. Nello specifico, il tasso raggiungibile $R_t$ corrisponde al miglior tasso noto raggiungibile per un modello a struttura fissa:
   $$R_t = \min_{U \in U_t} H(Y | X_U) - \max_{A \in A_t} H(Y | X_A)$$
   Questo risultato implica che la natura dinamica della struttura di accesso non degrada intrinsecamente il tasso del segreto rispetto a uno scenario statico.

2. Capacità per Strutture di Accesso a Soglia: Il documento dimostra che quando la struttura di accesso in un dato istante forma una Struttura di Accesso a Soglia (dove qualsiasi gruppo di dimensione $\ge f_1(t)$ è autorizzato e qualsiasi gruppo di dimensione $\le f_2(t)$ è non autorizzato), la strategia proposta raggiunge la capacità. Per un caso specifico in cui il dealer condivide chiavi private indipendenti con i partecipanti, la capacità è mostrata essere:
   $$R_t = H(X)(f_1(t) - f_2(t))$$

3. Onniscienza vs. Causalità: Un risultato significativo è che, per il caso AAS a soglia, un dealer onniscente (che conosce l'intera sequenza futura delle strutture di accesso) non ottiene alcun vantaggio rispetto a un dealer causale (che conosce solo la struttura corrente) in termini di tassi di segreto raggiungibili.

Significato e Rivendicazioni
Il documento sostiene di generalizzare i modelli di condivisione dei segreti basati sulla casualità correlata da strutture di accesso additive fisse a dinamiche. Il significato primario risiede nel dimostrare che l'adattabilità dinamica non comporta un costo in termini di efficienza del tasso del segreto. Gli autori mostrano che è possibile raggiungere i limiti di prestazione delle migliori strategie statiche senza richiedere la conoscenza preventiva dell'evoluzione del sistema.

Il lavoro evidenzia come il risultato "sorprendente" sia l'indipendenza del tasso raggiungibile al tempo $t$ dalla storia o dal futuro della struttura di accesso. Sebbene il documento fornisca una dimostrazione di esistenza non costruttiva per il caso generale AAS (facendo affidamento sul metodo probabilistico per dimostrare l'esistenza di funzioni di binning idonee), esso nota esplicitamente che fornire una dimostrazione di raggiungibilità costruttiva per l'AAS generale rimane un problema aperto, distinguendolo dalle esistenti dimostrazioni costruttive per le strutture fisse.

Il documento conclude che, per le strutture dinamiche basate su soglia, la capacità è completamente caratterizzata e la mancanza di lungimiranza riguardo ai futuri cambiamenti della struttura di accesso non penalizza le prestazioni del sistema.