Circuit ORAM e prestazioni pratiche

Circuit ORAM, proposta da Wang, Chan e Shi (2015), è stata progettata per minimizzare l'overhead della larghezza di banda, mantenendo al contempo una semplice implementazione nei framework di secure computation (garbled circuits e secret sharing). La sua innovazione principale consiste nel ridurre la dimensione dei bucket a Z = 2 blocchi, rispetto a Z = 5 in Path ORAM, dimezzando la larghezza di banda e mantenendo una probabilità di errore trascurabile. La procedura di eviction è stata riprogettata in modo da poter essere espressa come un piccolo circuito booleano.

In Path ORAM con Z = 5, la probabilità di overflow dello stash è controllata disponendo più blocchi per bucket, così da accogliere l'assegnazione casuale dei blocchi ai percorsi. Circuit ORAM dimostra che Z = 2 è sufficiente quando si utilizza una procedura di eviction deterministica (deep-first eviction) invece di una eviction casuale. Questo dimezza lo storage sul server e l'overhead di comunicazione rispetto a Path ORAM con gli stessi parametri di sicurezza.

Circuit ORAM è stata progettata specificamente con una procedura di eviction esprimibile come un circuito booleano efficiente. Nei protocolli di secure computation (garbled circuits, SPDZ), l'accesso ORAM stesso deve essere valutato obliviously: il server che esegue il calcolo non deve apprendere quale posizione di memoria viene consultata. Il semplice circuito di eviction deterministico di Circuit ORAM è molto più efficiente da trasformare in un garbled circuit rispetto alla procedura di eviction di Path ORAM.

Per un database di N blocchi di dimensione B byte, Circuit ORAM richiede 2 * log N * B byte per accesso, leggendo e scrivendo un percorso con Z = 2 blocchi per bucket. Per N = 2^20 blocchi da 4KB ciascuno, ciò corrisponde a 160KB per accesso, rispetto ai 400KB di Path ORAM (Z=5). L'overhead di larghezza di banda rispetto al testo in chiaro è di circa 40x con parametri tipici, in calo rispetto al valore di 100x di Path ORAM.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) utilizza Circuit ORAM per creare versioni oblivious di strutture dati di alto livello: liste collegate oblivious, mappe oblivious (tabelle hash) e code di priorità oblivious. Queste strutture consentono di eseguire calcoli oblivious su dati dinamici senza rivelare i pattern di accesso. Oblix viene eseguito all'interno di enclave Intel SGX e si rivolge all'intersezione privata di insiemi e alle query private su database.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) estende Path ORAM per supportare accessi asincroni ad alta produttività, elaborando più richieste ORAM in parallelo e raggruppando in batch le eviction dei percorsi. Combinando gli accessi allo stesso percorso, TaoStore raggiunge un throughput significativamente superiore (richieste al secondo) rispetto alle costruzioni ORAM sincrone, risultando adatto ai server di archiviazione cloud con molti client simultanei.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) costruisce un sistema completo di archiviazione transazionale sopra Path ORAM. Obladi supporta transazioni ACID su un'archiviazione cifrata che nasconde i pattern di accesso. Introduce l'esecuzione differita: le transazioni vengono raggruppate in epoche ed eseguite in modo da nascondere quali record specifici sono stati consultati all'interno di ciascuna epoca. Obladi funziona come proxy attendibile tra i client e un backend di archiviazione cloud non attendibile.

Per un ORAM da 1 GB (262.144 blocchi da 4 KB) distribuito su AWS, con un client che accede ai blocchi via Internet, la latenza di Path ORAM è di circa 50–200 ms per accesso (dominata dal tempo di andata e ritorno necessario per gli accessi ai bucket log N = 18). Con il recupero parallelo dei bucket, è possibile ridurla. Per le applicazioni SGX locali con ORAM in RAM, la latenza è compresa tra 1 e 10 ms per accesso, un valore accettabile per molte applicazioni di calcolo sicuro.

Il sovraccarico di banda di ORAM dipende fortemente dai pattern di accesso. Per un ORAM di archiviazione cloud da 1 TB con blocchi da 1 MB, ogni accesso trasferisce circa 25 MB (un sovraccarico di 25x per i 25 livelli log N = 25). Per blocchi piccoli (4 KB), il sovraccarico per accesso è minore in termini di byte assoluti, ma maggiore in termini relativi. Le organizzazioni che implementano ORAM devono prevedere un'amplificazione della banda di 20–50x e assicurarsi che le proprie connessioni di rete e i costi di egress dal cloud ne tengano conto.

Un'alternativa a ORAM per la privacy degli accessi è l'hardware trusted: Intel SGX o AMD SEV forniscono un ambiente di esecuzione affidabile in cui persino il sistema operativo host non può osservare i pattern di calcolo o di accesso alla memoria (con difese appropriate). SGX senza ORAM continua a esporre all'hardware i pattern di accesso a livello di pagina, quindi per una protezione completa è necessario utilizzare ORAM all'interno di SGX. Rispetto al solo ORAM, l'hardware trusted riduce il sovraccarico di banda, ma richiede di fidarsi del produttore dell'hardware e della catena di approvvigionamento.

ORAM è appropriato quando: l'avversario osserva i pattern di accesso lato server (provider cloud, co-tenant), la sensibilità dei dati giustifica un sovraccarico di banda di 20–50x e il pattern di accesso stesso potrebbe rivelare informazioni sensibili. Per la maggior parte delle applicazioni, la cifratura standard con un'attenta gestione delle chiavi è sufficiente. ORAM è uno strumento specializzato per scenari ad alta sicurezza: analisi di dati medici, machine learning privato, sistemi di trading finanziario e database delle forze dell'ordine.

Circuit ORAM riduce la dimensione dei bucket a Z=2 (rispetto a Z=5 di Path ORAM), dimezzando la banda mediante un'eviction deterministica dalla profondità verso l'alto. È progettato per essere utilizzato all'interno del calcolo sicuro con circuiti garbled. Il sovraccarico pratico è un'amplificazione della banda pari a 40x per i parametri tipici. I sistemi di produzione includono Oblix (SGX + strutture dati oblivious), TaoStore (ORAM ad alto throughput con elaborazione in batch) e Obladi (ORAM transazionale). ORAM all'interno di SGX è necessario perché SGX da solo espone i pattern di accesso a livello di pagina.