Path ORAM : masquer les accès mémoire

L’ORAM par chemin, proposée par Stefanov, van Dijk, Shi, Fletcher, Ren, Yu et Devadas (2013), est la construction ORAM qui a eu le plus d’influence en pratique. Elle organise le stockage du serveur sous la forme d’un arbre binaire de compartiments, chaque feuille correspondant à une position pour un bloc de données. Dans sa forme de base, l’ORAM par chemin atteint un surcoût de communication de O(log^2 N) par accès et est suffisamment simple pour être implémentée en quelques centaines de lignes de code.

La table de positions est une structure de données côté client qui associe l’adresse de chaque bloc logique à un nœud feuille de l’arbre binaire. Pour une base de données de N blocs avec un arbre de hauteur L = log N, la table de positions est un tableau de N indices de feuilles. Avant d’accéder au bloc b, le client recherche sa feuille actuellement attribuée dans la table de positions et lui attribue une nouvelle feuille aléatoire. Le chemin de l’ancienne feuille sera lu puis réécrit sur le serveur.

La réserve est un petit tampon côté client (généralement de 20 à 40 blocs) qui contient temporairement les blocs lus sur le serveur mais pas encore réécrits. Lorsqu’un bloc est lu, il est retiré de son chemin et placé dans la réserve. Après y avoir accédé et l’avoir éventuellement modifié, tous les blocs de la réserve qui peuvent être placés sur le nouveau chemin y sont réécrits. Les blocs qui ne peuvent pas tenir sur un chemin restent dans la réserve.

Le stockage du serveur est un arbre binaire complet comportant L+1 niveaux (L = log N). Chaque nœud (compartiment) contient Z blocs (généralement Z = 5). Les feuilles correspondent aux positions des blocs de données. Il y a N nœuds feuilles, donc 2N-1 nœuds au total et un stockage total côté serveur de O(NZ). Chaque chemin feuille-racine comporte log N nœuds et peut contenir Z*log N blocs, ce qui fournit la capacité nécessaire à la stratégie d’éviction par chemin.

Pour lire le bloc b : (1) rechercher dans la table de positions la feuille actuelle l de b ; (2) attribuer à b une nouvelle feuille aléatoire l' et mettre à jour la table de positions ; (3) lire tous les compartiments du chemin allant de la feuille l à la racine (log N compartiments) ; (4) trouver le bloc b sur le chemin lu ou dans la réserve ; (5) réécrire tous les blocs qui peuvent être attribués au nouveau chemin l' et remplir les emplacements restants des compartiments avec des blocs factices. Le serveur voit une lecture d’un chemin aléatoire à chaque fois.

L’ORAM par chemin conserve son caractère oblivieux, car chaque accès lit et écrit exactement un chemin racine-feuille, quel que soit le bloc consulté. Le chemin est déterminé par l’attribution uniforme d’une feuille aléatoire, et non par le contenu ou l’adresse du bloc. Des blocs factices remplissent les emplacements vides des compartiments afin que chaque chemin comporte le même nombre d’emplacements occupés. Un adversaire qui observe le serveur ne voit que des accès à des chemins aléatoires.

Chaque accès à l’ORAM par chemin nécessite de lire et d’écrire un chemin racine-feuille : O(log N) compartiments contenant chacun Z blocs. Avec une taille de bloc B et une taille de compartiment Z, chaque accès transfère O(Z * log N * B) bits. Pour les paramètres courants (N = 2^20, Z = 5, B = 4 Ko), cela représente environ 400 Ko par accès, contre 4 Ko pour un accès en clair, soit un surcoût de 100 fois. Les tables de positions récursives réduisent la communication à O(log^2 N) en nombre de blocs.

La table de positions naïve nécessite de stocker N entrées côté client, soit un stockage client de O(N), aussi grand que la base de données entière. La table de positions récursive réduit le stockage côté client à O(log^2 N) en stockant récursivement la table de positions elle-même dans un ORAM plus petit. La récursion s’arrête lorsque l’ORAM est suffisamment petit pour tenir dans la réserve. Il s’agit de la technique standard qui rend l’ORAM par chemin pratique pour les grands ensembles de données.

La taille de la réserve de l’ORAM par chemin augmente lorsque des conflits de chemins empêchent l’expulsion des blocs vers les chemins qui leur sont attribués. Stefanov et ses coauteurs ont démontré que la réserve déborde (dépasse R blocs) avec une probabilité exponentiellement faible en R, précisément au plus 14 * (0.6002)^R selon l’analyse standard. En fixant R = 40, on obtient une probabilité d’échec d’environ 2^{-38}, et ce résultat vaut pour toutes les séquences d’accès, y compris celles choisies par un adversaire.

Avant l’ORAM par chemin, les meilleures constructions ORAM pratiques entraînaient un surcoût de O(log^3 N) (Shi et al. 2011, « RAM oblivieuse avec un coût dans le pire des cas de O((log N)^3) »). L’ORAM par chemin a réduit ce surcoût à O(log^2 N) grâce à une structure beaucoup plus simple. Des travaux ultérieurs (ORAM en circuit, OptORAMa) ont encore amélioré les constantes et les bornes asymptotiques, mais l’ORAM par chemin reste la construction la plus largement implémentée en raison de sa simplicité.

L’ORAM par chemin a été implémentée dans des dizaines de systèmes de recherche et de production. ZeroTrace (Intel SGX + ORAM par chemin), Obladi (ORAM par chemin sur un stockage en nuage) et Opaque (ORAM par chemin sur Apache Spark) sont des implémentations notables. Le groupe de calcul sécurisé de Stanford maintient une implémentation C++ libre de l’ORAM par chemin. AWS propose l’ORAM par chemin dans le cadre de ses prototypes de recherche Nitro Enclaves pour l’analyse de données préservant la confidentialité.

Quel est le rôle de la table de positions dans l’ORAM par chemin ?

L’ORAM par chemin organise le stockage du serveur sous la forme d’un arbre binaire dans lequel chaque accès lit et écrit un chemin racine-feuille. La table de positions suit l’attribution actuelle d’une feuille à chaque bloc ; la réserve contient temporairement les blocs récemment consultés. Chaque accès est randomisé par l’attribution de nouvelles positions de feuilles aléatoires, ce qui rend tous les accès visibles par le serveur identiquement distribués. Le surcoût de communication est de O(Z * log N) par accès. Les tables de positions récursives réduisent le stockage côté client à O(log^2 N). L’ORAM par chemin est la construction ORAM la plus largement implémentée.