Path ORAM: nascondere gli accessi alla memoria

Path ORAM, proposta da Stefanov, van Dijk, Shi, Fletcher, Ren, Yu e Devadas (2013), è la costruzione ORAM più influente dal punto di vista pratico. Organizza lo storage sul server come un albero binario di bucket, in cui ogni foglia corrisponde a una posizione per un blocco di dati. Nella sua forma di base, Path ORAM raggiunge un overhead di comunicazione O(log^2 N) per accesso ed è abbastanza semplice da poter essere implementata in poche centinaia di righe di codice.

La mappa delle posizioni è una struttura dati lato client che associa ogni indirizzo logico di blocco a un nodo foglia dell'albero binario. Per un database di N blocchi con un albero di altezza L = log N, la mappa delle posizioni è un array di indici delle foglie. Prima di accedere al blocco b, il client cerca nella mappa delle posizioni la foglia attualmente assegnata e assegna al blocco una nuova foglia casuale. Il vecchio percorso dalla foglia alla radice verrà letto dal server e riscritto.

Lo stash è un piccolo buffer lato client, che contiene in genere 20-40 blocchi e conserva temporaneamente i blocchi letti dal server ma non ancora riscritti. Quando un blocco viene letto, viene rimosso dal relativo percorso e inserito nello stash. Dopo averlo consultato ed eventualmente modificato, tutti i blocchi dello stash che possono essere collocati nel nuovo percorso vengono riscritti. I blocchi che non possono entrare in un percorso rimangono nello stash.

Lo storage sul server è un albero binario completo con L+1 livelli (L = log N). Ogni nodo (bucket) contiene Z blocchi, in genere Z = 5. Le foglie corrispondono alle posizioni dei blocchi di dati. Ci sono N nodi foglia, quindi in totale ci sono 2N-1 nodi e O(NZ) di storage sul server. Ogni percorso dalla foglia alla radice contiene log N nodi e può contenere Z*log N blocchi, fornendo la capacità necessaria per la strategia di eviction lungo il percorso.

Per leggere il blocco b: (1) cercare nella mappa delle posizioni la foglia corrente l di b; (2) assegnare a b una nuova foglia casuale l' e aggiornare la mappa delle posizioni; (3) leggere tutti i bucket sul percorso dalla foglia l alla radice (log N bucket); (4) trovare il blocco b nel percorso letto o nello stash; (5) riscrivere tutti i blocchi che possono essere assegnati al nuovo percorso l' e riempire gli slot rimanenti dei bucket con blocchi fittizi. Il server vede ogni volta la lettura di un percorso casuale.

Path ORAM mantiene l'obliviousness perché ogni accesso legge e scrive esattamente un percorso dalla radice alla foglia, indipendentemente dal blocco consultato. Il percorso è determinato dall'assegnazione di una foglia uniformemente casuale, non dal contenuto o dall'indirizzo del blocco. I blocchi fittizi riempiono gli slot vuoti dei bucket, così ogni percorso ha lo stesso numero di slot occupati. Un avversario che osserva il server vede soltanto accessi a percorsi casuali.

Ogni accesso a Path ORAM richiede la lettura e la scrittura di un percorso dalla radice alla foglia: O(log N) bucket, ciascuno composto da Z blocchi. Con una dimensione del blocco B e una dimensione del bucket Z, ogni accesso trasferisce O(Z * log N * B) bit. Con parametri tipici (N = 2^20, Z = 5, B = 4KB), ciò corrisponde a circa 400KB per accesso, rispetto ai 4KB di un accesso al testo in chiaro: un overhead di 100x. Le mappe delle posizioni ricorsive riducono questo valore a O(log^2 N) in termini di blocchi.

La mappa delle posizioni ingenua richiede N voci memorizzate sul client, ovvero O(N) di storage lato client, grande quanto l'intero database. La mappa delle posizioni ricorsiva riduce lo storage sul client a O(log^2 N), memorizzando ricorsivamente la mappa delle posizioni stessa in un ORAM più piccolo. La ricorsione termina quando l'ORAM è abbastanza piccola da entrare nello stash. Questa è la tecnica standard per rendere Path ORAM pratica per dataset di grandi dimensioni.

La dimensione dello stash in Path ORAM cresce se i blocchi non possono essere espulsi nei percorsi loro assegnati a causa di conflitti tra percorsi. Stefanov et al. hanno dimostrato che lo stash va in overflow, ovvero supera R blocchi, con una probabilità esponenzialmente piccola in R: nello specifico, al massimo 14 * (0.6002)^R secondo l'analisi standard. Impostando R = 40 si ottiene una probabilità di errore di circa 2^{-38}, e questo vale per tutte le sequenze di accesso, comprese quelle scelte dall'avversario.

Prima di Path ORAM, le migliori costruzioni ORAM pratiche avevano un overhead di O(log^3 N) (Shi et al. 2011, "Oblivious RAM with O((log N)^3) Worst-Case Cost"). Path ORAM lo ha ridotto a O(log^2 N) con una struttura molto più semplice. I lavori successivi (Circuit ORAM, OptORAMa) hanno ulteriormente migliorato le costanti e i limiti asintotici, ma Path ORAM rimane la costruzione più implementata grazie alla sua semplicità.

Path ORAM è stata implementata in decine di sistemi di ricerca e di produzione. ZeroTrace (Intel SGX + Path ORAM), Obladi (Path ORAM su storage cloud) e Opaque (Path ORAM su Apache Spark) sono implementazioni degne di nota. Il gruppo di secure computation di Stanford mantiene un'implementazione open source di Path ORAM in C++. AWS offre Path ORAM come parte dei suoi prototipi di ricerca Nitro Enclaves per l'analisi dei dati con tutela della privacy.

Qual è il ruolo della mappa delle posizioni in Path ORAM?

Path ORAM organizza lo storage sul server come un albero binario, in cui ogni accesso legge e scrive un percorso dalla radice alla foglia. La mappa delle posizioni tiene traccia dell'assegnazione corrente di ogni blocco a una foglia; lo stash conserva temporaneamente i blocchi consultati di recente. Ogni accesso viene randomizzato assegnando nuove posizioni casuali alle foglie, facendo sì che tutti gli accessi visibili al server abbiano distribuzioni identiche. L'overhead di comunicazione è O(Z * log N) per accesso. Le mappe delle posizioni ricorsive riducono lo storage sul client a O(log^2 N). Path ORAM è la costruzione ORAM più implementata.