Plausible Deniability in Fully Homomorphic Computation

Sintesi Tecnica: Negabilità Plausibile nella Computazione Omomorfica Totale (PD-FHC)

1. Definizione del Problema

L'esternalizzazione della computazione a fornitori di servizi cloud non fidati espone gli utenti a due minacce distinte che le tecnologie esistenti non riescono ad affrontare simultaneamente:

1. Privacy Computazionale: Proteggere i dati da fornitori "onesti ma curiosi" (affrontata dalla Crittografia Omomorfica Totale (FHE) e dagli Ambienti di Esecuzione Affidabili (TEE)).
2. Negabilità Plausibile: La capacità di negare credibilmente l'esistenza o l'intento di una computazione quando si è costretti da un avversario potente.

Le soluzioni attuali presentano lacune critiche:

• FHE: Sebbene nasconda i valori dei dati, la trasmissione dei ciphertext è vistosa. Un avversario coercitivo può esigere le chiavi di decrittazione, e il solo uso di FHE conferma che sta avvenendo una computazione privata.
• TEE: Producono log di attestazione che fungono da prova inconfutabile dell'esecuzione. Inoltre, sono vulnerabili a perdite tramite canali laterali (side-channel).
• Multi-Party Computation (MPC): Sebbene sia robusta contro la rivelazione della singola quota di una parte, non permette ai partecipanti di negare che la computazione sia avvenuta o di sostituire una diversa computazione.
• Crittografia/Archiviazione Negabile: Queste affrontano i dati statici (messaggi o file) ma non si estendono all'intento computazionale dinamico.

Il documento identifica una lacuna in cui un utente ha bisogno di esternalizzare una computazione booleana mantenendo al contempo la capacità di negare cosa è stato computato e, per un osservatore esterno, che una computazione sia avvenuta affatto.

2. Metodologia

Gli autori propongono PD-FHC, un framework che incorpora computazioni booleane in un mezzo di copertura (specificamente immagini RGB) utilizzando porte di Fredkin e la steganografia del bit meno significativo (LSB - Least Significant Bit).

Meccanismo Core:

• Cablaggio Condiviso, Semantica Variabile: Il framework utilizza un cablaggio unico e fisso di porte di Fredkin universali. Una porta di Fredkin è una porta reversibile a 3 ingressi/3 uscite in cui un bit di controllo determina se i due bit di dati vengono scambiati.
  • Se il bit di controllo è 0, la porta agisce come un passaggio diretto (pass-through).
  • Se il bit di controllo è 1, la porta scambia i due bit di dati.
  • Impostando i bit di controllo tramite dati incorporati, lo stesso cablaggio fisico può implementare diverse funzioni logiche (ad es., AND, OR, NOT o circuiti complessi) in posizioni diverse.
• Embedding Multi-Posizione: L'utente (Alice) incorpora un circuito "reale" e $L-1$ circuiti "esca" (decoy) nei LSB di un'immagine.
  • Circuito Reale: Incorporato in un set di posizioni segrete $\Lambda_{j^*}$.
  • Circuiti Esca: Incorporati in altri set di posizioni disgiunte $\Lambda_j$.
  • Bit di Riempimento (Fill Bits): Tutte le restanti posizioni LSB sono riempite con bit tratti da una specifica distribuzione $\pi$.
• Elaborazione Uniforme: Il fornitore cloud (Carol) riceve l'immagine e la specifica del cablaggio ($C_{obf}$). Essa applica la porta di Fredkin uniformemente a ogni posizione di pixel in parallelo. Carol non sa quali posizioni contengano dati reali, dati esca o rumore di riempimento.
• Risposta alla Coercizione: Se costretta, Alice rivela i set di posizioni, gli input e gli output per un circuito esca. Poiché il cablaggio è identico e il circuito esca produce risultati verificabili coerenti con l'output del cloud, l'avversario non può distinguere il circuito esca dal circuito reale.

Fondamenti Teorici:

• Deniable Computation Medium (DCM): Un framework astratto che definisce un mezzo con posizioni di bit indirizzabili, capacità di lettura/scrittura e una famiglia di porte che si applica uniformemente.
• Condizione di Marginalità Corrispondente (Matched-Marginal Condition): Per la sicurezza informazionale, i bit nelle posizioni reali, nelle posizioni esca e nelle posizioni di riempimento devono essere tratti dalla stessa legge di probabilità per posizione $\pi$. Sotto questa condizione, il piano LSB è "scambiabile", il che significa che la distribuzione statistica dell'immagine è invariante rispetto alla permutazione delle posizioni.

3. Contributi Chiave

1. Framework Astratto: Definizione di un Deniable Computation Medium (DCM) e di uno Deniable Computation Scheme (DCS) che separano il modello di sicurezza dal mezzo di copertura specifico (ad es., immagini, audio, pacchetti).
2. Formalizzazione del Modello di Minaccia: Un modello a due fasi che distingue tra:
   • Cloud Onesto-ma-Curioso (HBC): Interessato alla privacy computazionale (nascondere i dati).
   • Avversario Coercitivo: Interessato alla negabilità plausibile (nascondere l'esistenza e l'intento della computazione).
     Gli autori definiscono nuovi giochi di coercizione multi-round che misurano la "distinguibilità dell'esistenza" (l'avversario può provare che esistono circuiti nascosti?) e la "scoperta del circuito" (l'avversario può identificare il circuito reale tra i decoy rivelati?).
3. Istanziazione Basata su Immagini: Un'implementazione concreta utilizzando immagini RGB e porte di Fredkin.
   • Prova della Privacy di Posizione: Sotto la condizione di marginalità corrispondente, il paper dimostra che il fornitore cloud ottiene un vantaggio zero (informazionale) nel localizzare le posizioni del circuito reale rispetto al caso casuale, indipendentemente dalla distribuzione $\pi$.
   • Occultamento Parziale del Circuito: Il cablaggio è visibile, ma la semantica della porta è nascosta. Il paper dimostra che senza la conoscenza dei bit di controllo, il cablaggio non rivela nulla su quale funzione venga computata.
4. Implementazione e Benchmark: Un'implementazione in Python testata su dimensioni di circuiti (da 5 a 302 porte) e dimensioni di immagini ($128^2$ a $512^2$).

4. Risultati

• Garanzie di Sicurezza:
  • Privacy Computazionale: Il cloud non apprende nulla sui valori segreti dei dati o sulla specifica funzione computata, a condizione che la famiglia di porte preservi la distribuzione statistica delle posizioni non segrete (una proprietà che le porte di Fredkin soddisfano tramite la permutazione dei bit).
  • Occultamento dell'Esistenza: Sotto la condizione di marginalità corrispondente, il vantaggio di esistenza è esattamente zero. Un avversario non può distinguere tra un'immagine contenente solo bit di riempimento e una contenente circuiti nascosti.
  • Scoperta del Circuito: Il vantaggio nell'identificare il circuito reale tra i decoy non rivelati è limitato dalla plausibilità semantica dei decoy e dalle perdite tramite canali laterali. Il vettore di posizione e quello di cablaggio contribuiscono con zero al vantaggio dell'avversario.
• Performance: L'implementazione mostra prestazioni competitive con TFHE (una libreria FHE leader) per circuiti booleani, fornendo al contempo una negabilità che FHE non può offrire.
• Impercettibilità Visiva: La modifica dei LSB risulta in uno spostamento massimo di $\pm 1$ per canale, producendo un PSNR > 50 dB, rendendo le modifiche visivamente impercettibili.

5. Significato e Rivendicazioni

Il paper sostiene di essere il primo framework a soddisfare simultaneamente la privacy computazionale, l'occultamento dell'esistenza (contro osservatori esterni) e l'occultamento parziale del circuito (contro il fornitore cloud).

Rivendicazioni Modeste e Limitazioni:

• Ambito della Plausibilità del Copertura: Gli autori dichiarano esplicitamente che PD-FHC non funziona per qualsiasi immagine (ad es., scatti fotografici di vacanze). Il servizio di copertura deve legittimamente aspettarsi input LSB ad alta entropia (ad es., dithering, iniezione di rumore o elaborazione in dominio crittografico). Se il servizio dichiarato prevede immagini naturali, il piano LSB uniforme richiesto per la sicurezza diventerebbe rilevabile.
• Vincoli degli Input Reali: La garanzia di vantaggio zero informazionale tiene esattamente solo se i bit di input reale dell'utente seguono la stessa distribuzione $\pi$ dei bit esca e di riempimento. Per input reali strutturati, il vantaggio è limitato dalla distanza statistica ($\Delta$) tra la distribuzione dell'input reale e $\pi$.
• Plausibilità Semantica: La sicurezza contro la scoperta del circuito si basa sulla $\epsilon$-plausibilità dei circuiti esca. Il paper ammette che la costruzione di circuiti esca semanticamente credibili (ad es., un controllo di luminosità rispetto a un hash crittografico) è un compito manuale e specifico del dominio, non ancora automatizzato.
• Attacchi Attivi: Il framework assume un cloud onesto-ma-curioso e osservatori esterni passivi. Non protegge da attaccanti attivi che potrebbero modificare l'immagine o rifiutarsi di computare.
• Assenza di Obfuscazione Crittografica: Il paper evita esplicitamente di rivendicare l'offuscamento crittografico del circuito (soggetto a risultati di impossibilità). L'"offuscamento" è puramente steganografico, basandosi sui bit di controllo nascosti per variare la semantica delle porte.

In sintesi, PD-FHC offre un approccio innovativo per l'esternalizzazione della computazione in cui l'utente può negare credibilmente l'intento specifico della computazione presentando una funzione alternativa verificabile che è indistinguibile da quella reale sotto coercizione, a condizione che le condizioni statistiche del mezzo di copertura siano soddisfatte.