Riepilogo Tecnico: Resilienza alla Fuga Quantistica dello Shamir Secret Sharing

Definizione del Problema

Il documento investiga la resilienza alla fuga quantistica dello schema standard, non modificato, di Shamir secret sharing su campi primi $\mathbb{F}_p$. Sebbene lo schema di Shamir sia ampiamente utilizzato nella crittografia a soglia e nel calcolo multipartitico sicuro, le sue garanzie di sicurezza assumono tradizionalmente che i set non autorizzati non apprendano nulla sul segreto. Nella pratica, tuttavia, informazioni parziali (leakage) possono essere esposte attraverso canali laterali.

Gli autori estendono lo studio della resilienza alla fuga locale dal contesto classico (dove un avversario ottiene un output classico breve, ad esempio un bit, da ogni share) al contesto quantistico. In questo modello, il dispositivo di ogni parte riceve uno share classico e produce un singolo qubit (o un piccolo numero di qubit) verso un avversario che può eseguire misurazioni congiunte. Lo studio esplora inoltre come la pre-condivisione di entanglement tra i dispositivi di fuga, o tra i dispositivi e l'avversario, impatti la sicurezza.

Metodologia

Il documento impiega una combinazione di analisi di Fourier su campi finiti e proprietà dei codici Maximum Distance Separable (MDS) per limitare il vantaggio di distinzione tra due stati del segreto.

1. Riduzione Pauli-Fourier:

   • La fuga da ogni share è modellata come una matrice di densità $\rho_i(y_i)$. Gli autori la espandono nella base di Pauli: $\rho_i(y) = \frac{1}{2}(I + r_{i,X}(y)X + r_{i,Y}(y)Y + r_{i,Z}(y)Z)$.
   • Definiscono un "budget di Fourier" $W_i(a)$ basato sui valori quadratici delle ampiezze dei coefficienti di Fourier delle funzioni dei coefficienti di Pauli.
   • Utilizzando l'identità di Parseval e l'ortogonalità degli operatori di Pauli, il vantaggio di distinzione è limitato da una somma sul codice duale di Shamir $C^\perp_0$:
     $$\text{Adv} \leq \sum_{a \in C^\perp_0 \setminus \{0\}} \prod_{i=1}^n \sqrt{W_i(a_i)}$$
   • Ciò riduce il problema della sicurezza quantistica al controllo di una somma pesata sul codice duale, simile alle dimostrazioni di fuga classica, ma complicato dalla natura matriciale dei coefficienti.

2. Gestione di Entanglement e Blocchi:

   • Blocchi Disgiunti: Per i dispositivi che condividono entanglement all'interno di blocchi disgiunti (ma non tra i blocchi o con l'avversario), gli autori applicano una disuguaglianza di Brascamp-Lieb MDS a blocchi. Ciò consente di limitare la somma dei prodotti delle norme di traccia dei coefficienti di Fourier per gli output a blocchi.
   • Entanglement con l'Avversario: Per un insieme di dispositivi $E$ che condividono un entanglement arbitrario con l'avversario, gli autori utilizzano un argomento di riduzione. Dimostrano che se l'avversario apprende gli share classici di $E$, la sicurezza del sistema rimanente si riduce a uno schema di Shamir non entangled con $n-r$ parti e soglia $t-r$.

3. Risultati Negativi (Attacchi):

   • Il documento costruisce un attacco specifico utilizzando uno stato GHZ condiviso tra $t$ dispositivi. Applicando spostamenti di fase dipendenti dai loro share e misurando nella base Pauli-X, i dispositivi possono distinguere tra segreti con un alto vantaggio, anche se producono solo un bit classico ciascuno.

Contributi Chiave e Risultati

1. Fuga Quantistica Non Entangled

Gli autori dimostrano che lo Shamir secret sharing è sicuro contro la fuga locale non entangled di un singolo qubit, a condizione che il tasso di soglia $\tau = t/n$ superi una costante specifica $\tau^\star \approx 0.73339$.

• Risultato: Se $\tau > \tau^\star + \eta$ (per un $\eta > 0$ fissato), il vantaggio di distinzione è esponenzialmente piccolo ($2^{-\Omega(n)}$).
• Tecnica: Questo è derivato dalla disuguaglianza di Brascamp-Lieb MDS a blocchi con dimensione del blocco $b=1$.

2. Blocchi Entangled Disgiunti

La sicurezza è estesa a scenari in cui i dispositivi sono partizionati in blocchi disgiunti di dimensione massima fissa $b$, dove i dispositivi all'interno di un blocco possono condividere entanglement e eseguire calcoli congiunti, ma i blocchi sono indipendenti l'uno dall'altro e dall'avversario.

• Risultato: La sicurezza è mantenuta per un tasso di soglia sufficientemente elevato $\tau > \tau^\star(b)$, dove $\tau^\star(b) < 1$. All'aumentare della dimensione del blocco $b$, il tasso di soglia richiesto si avvicina a 1.
• Dettagli: La Tabella 1 nel documento elenca le soglie sufficienti per dimensioni di blocco uguali (ad esempio, per $b=2$, $\tau \approx 0.933$; per $b=3$, $\tau \approx 0.987$).

3. Fuga con Entanglement dell'Avversario

Il documento analizza il caso in cui un numero lineare di dispositivi ($r = \delta n$) condivide un entanglement arbitrario tra loro e con l'avversario.

• Risultato: La sicurezza è garantita se il tasso "residuo" soddisfa:
  $$\frac{\tau - \delta}{1 - \delta} > \tau^\star$$
  Ciò implica che, per un tasso di soglia fisso $\tau > \tau^\star$, la sicurezza è mantenuta anche se una frazione lineare di dispositivi ($\delta < \frac{\tau - \tau^\star}{1 - \tau^\star}$) condivide l'entanglement con l'avversario.

4. Risultato Negativo: Attacco GHZ

Gli autori dimostrano che se $t$ dispositivi condividono uno stato GHZ, lo schema diventa insicuro anche sotto una fuga classica a singolo bit.

• Meccanismo: $t$ dispositivi condividono uno stato GHZ. Ognuno applica una fase basata sul proprio share e misura nella base X; il prodotto dei risultati rivela il segreto con un vantaggio $\cos^2(\pi/(2p)) \approx 1 - O(p^{-2})$.
• Implicazione: Questo attacco non richiede entanglement con l'avversario, solo tra i $t$ dispositivi di fuga. Stabilisce che il numero massimo di dispositivi che possono condividere un entanglement arbitrario preservando la sicurezza è lineare in $n$ (fino a costanti), ma la frazione ottimale rimane un problema aperto.

Significato e Rivendicazioni

Il documento afferma di iniziare lo studio della resilienza alla fuga quantistica per lo schema di Shamir secret sharing ampiamente utilizzato e non modificato.

• Robustezza degli Schemi Standard: I risultati mostrano che lo schema di Shamir standard mantiene forti garanzie di sicurezza contro la fuga quantistica senza richiedere nuovi algoritmi di condivisione o cambiamenti ai protocolli, a condizione che il tasso di soglia sia sufficientemente elevato (sopra $\approx 0.733$).
• Ruolo dell'Entanglement: Il lavoro evidenzia una distinzione critica: mentre la fuga quantistica non entangled è gestibile con soglie elevate, la presenza di entanglement arbitrario tra i dispositivi di fuga (specificamente uno stato GHZ tra $t$ dispositivi) può rompere la sicurezza anche per output classici.
• Ottimalità: Gli autori sono modesti riguardo l'ottimalità dei loro limiti. Notano che la soglia sufficiente $\tau^\star \approx 0.733$ è superiore al limite classico noto ($\approx 0.668$) e pongono la questione se tale divario possa essere colmato. Allo stesso modo, la determinazione della frazione esatta di dispositivi entangled compatibile con la sicurezza è lasciata come problema aperto.

Il documento conclude che la resilienza alla fuga quantistica dipende fondamentalmente sia dalla dimensione degli output rilasciati che dalla struttura di entanglement disponibile ai dispositivi di fuga.