Path ORAM: ocultación de accesos a memoria

Path ORAM, propuesta por Stefanov, van Dijk, Shi, Fletcher, Ren, Yu y Devadas (2013), es la construcción ORAM con mayor influencia práctica. Organiza el almacenamiento del servidor como un árbol binario de cubetas, donde cada hoja corresponde a una posición para un bloque de datos. En su forma básica, Path ORAM alcanza un sobrecoste de comunicación de O(log^2 N) por acceso y es lo bastante sencilla como para implementarse en unos cientos de líneas de código.

El mapa de posiciones es una estructura de datos del cliente que asigna cada dirección lógica de bloque a un nodo hoja del árbol binario. Para una base de datos de N bloques con un árbol de altura L = log N, el mapa de posiciones es un arreglo de índices de hojas. Antes de acceder al bloque b, el cliente consulta su hoja asignada actual en el mapa de posiciones y le asigna una hoja aleatoria nueva. La ruta de la hoja anterior se leerá del servidor y se volverá a escribir en él.

El stash es un búfer pequeño del cliente (normalmente de 20-40 bloques) que almacena temporalmente los bloques que se han leído del servidor, pero que aún no se han vuelto a escribir en él. Cuando se lee un bloque, se retira de su ruta y se coloca en el stash. Después de acceder a él y modificarlo, si procede, se vuelven a escribir todos los bloques del stash que puedan colocarse en la nueva ruta. Los bloques que no quepan en una ruta permanecen en el stash.

El almacenamiento del servidor es un árbol binario completo con L+1 niveles (L = log N). Cada nodo (cubeta) contiene Z bloques (normalmente Z = 5). Las hojas corresponden a las posiciones de los bloques de datos. Hay N nodos hoja, por lo que existen 2N-1 nodos en total y el almacenamiento total del servidor es O(NZ). Cada ruta de una hoja a la raíz tiene log N nodos y puede contener Z*log N bloques, lo que proporciona la capacidad necesaria para la estrategia de expulsión por rutas.

Para leer el bloque b: (1) consulte la hoja actual l de b en el mapa de posiciones; (2) asigne a b una hoja aleatoria nueva l' y actualice el mapa de posiciones; (3) lea todas las cubetas de la ruta desde la hoja l hasta la raíz (log N cubetas); (4) busque el bloque b en la ruta leída o en el stash; (5) vuelva a escribir todos los bloques que puedan asignarse a la nueva ruta l' y rellene las ranuras restantes de las cubetas con bloques ficticios. El servidor ve una lectura de una ruta aleatoria en cada ocasión.

Path ORAM mantiene la ocultación de accesos porque cada acceso lee y escribe exactamente una ruta desde la raíz hasta una hoja, independientemente del bloque al que se acceda. La ruta está determinada por una asignación de hoja uniformemente aleatoria, no por el contenido ni la dirección del bloque. Los bloques ficticios llenan las ranuras vacías de las cubetas para que todas las rutas tengan el mismo número de ranuras ocupadas. Un adversario que observa el servidor solo ve accesos a rutas aleatorias.

Cada acceso de Path ORAM requiere leer y escribir una ruta desde la raíz hasta una hoja: O(log N) cubetas de Z bloques cada una. Con un tamaño de bloque B y un tamaño de cubeta Z, cada acceso transfiere O(Z * log N * B) bits. Con parámetros habituales (N = 2^20, Z = 5, B = 4KB), esto supone unos 400KB por acceso, frente a 4KB en un acceso a texto plano: un sobrecoste de 100x. Los mapas de posiciones recursivos reducen este valor a una comunicación de O(log^2 N) en términos de bloques.

El mapa de posiciones ingenuo requiere almacenar N entradas en el cliente, lo que supone un almacenamiento del cliente de O(N), tan grande como la base de datos completa. El mapa de posiciones recursivo reduce el almacenamiento del cliente a O(log^2 N) al almacenar el propio mapa de posiciones en una ORAM más pequeña de forma recursiva. La recursión termina cuando la ORAM es lo bastante pequeña como para caber en el stash. Esta es la técnica estándar para hacer que Path ORAM resulte práctica para conjuntos de datos grandes.

El tamaño del stash en Path ORAM aumenta si los bloques no pueden expulsarse a las rutas que tienen asignadas debido a conflictos entre rutas. Stefanov et al. demostraron que el stash se desborda (supera R bloques) con una probabilidad exponencialmente pequeña en R; concretamente, como máximo 14 * (0.6002)^R según el análisis estándar. Al establecer R = 40, se obtiene una probabilidad de fallo aproximada de 2^{-38}, y esto se cumple para todas las secuencias de acceso, incluidas las elegidas por un adversario.

Antes de Path ORAM, las mejores construcciones ORAM prácticas tenían un sobrecoste de O(log^3 N) (Shi et al. 2011, "Oblivious RAM with O((log N)^3) Worst-Case Cost"). Path ORAM lo redujo a O(log^2 N) con una estructura mucho más sencilla. Trabajos posteriores (Circuit ORAM, OptORAMa) mejoraron aún más las constantes y las cotas asintóticas, pero Path ORAM sigue siendo la construcción más implementada debido a su sencillez.

Path ORAM se ha implementado en decenas de sistemas de investigación y producción. ZeroTrace (Intel SGX + Path ORAM), Obladi (Path ORAM sobre almacenamiento en la nube) y Opaque (Path ORAM sobre Apache Spark) son implementaciones destacadas. El grupo de computación segura de Stanford mantiene una implementación de Path ORAM de código abierto en C++. AWS ofrece Path ORAM como parte de sus prototipos de investigación Nitro Enclaves para análisis de datos con preservación de la privacidad.

Path ORAM organiza el almacenamiento del servidor como un árbol binario en el que cada acceso lee y escribe una ruta desde la raíz hasta una hoja. El mapa de posiciones registra la asignación actual de cada bloque a una hoja; el stash almacena temporalmente los bloques a los que se ha accedido recientemente. Cada acceso se aleatoriza mediante la asignación de nuevas posiciones de hoja aleatorias, de modo que todos los accesos visibles para el servidor tienen distribuciones idénticas. El sobrecoste de comunicación es O(Z * log N) por acceso. Los mapas de posiciones recursivos reducen el almacenamiento del cliente a O(log^2 N). Path ORAM es la construcción ORAM más implementada.