Path ORAM: ukrywanie dostępu do pamięci

Path ORAM, zaproponowany przez Stefana, van Dijka, Shiego, Fletchera, Rena, Yu i Devadasa (2013), jest najbardziej wpływową w praktyce konstrukcją ORAM. Organizuje pamięć serwera jako binarne drzewo kubełków, w którym każdy liść odpowiada pozycji bloku danych. Path ORAM w podstawowej postaci osiąga narzut komunikacyjny O(log^2 N) na dostęp i jest na tyle prosty, że można go zaimplementować w kilkuset wierszach kodu.

Mapa pozycji jest strukturą danych po stronie klienta, która mapuje każdy logiczny adres bloku na liść w drzewie binarnym. W bazie danych zawierającej N bloków i drzewie o wysokości L = log N mapa pozycji jest tablicą N indeksów liści. Przed uzyskaniem dostępu do bloku b klient wyszukuje w mapie pozycji aktualnie przypisany mu liść i przypisuje mu nowy losowy liść. Stara ścieżka od liścia do korzenia zostanie odczytana z serwera i ponownie na nim zapisana.

Bufor stash jest niewielkim buforem po stronie klienta (zwykle mieszczącym 20–40 bloków), który tymczasowo przechowuje bloki odczytane z serwera, ale jeszcze na nim niezapisane. Po odczytaniu blok jest usuwany ze swojej ścieżki i umieszczany w buforze stash. Po uzyskaniu dostępu do niego i ewentualnej modyfikacji wszystkie bloki z bufora stash, które można umieścić na nowej ścieżce, są zapisywane z powrotem. Bloki, które nie mieszczą się na żadnej ścieżce, pozostają w buforze stash.

Pamięć serwera jest pełnym drzewem binarnym o L+1 poziomach (L = log N). Każdy węzeł (kubełek) przechowuje Z bloków (zwykle Z = 5). Liście odpowiadają pozycjom bloków danych. Istnieje N liści, więc łącznie jest 2N-1 węzłów, a całkowita pamięć serwera wynosi O(NZ). Każda ścieżka od liścia do korzenia zawiera log N węzłów i może pomieścić Z*log N bloków, zapewniając pojemność potrzebną strategii eksmisji bloków ze ścieżki.

Aby odczytać blok b: (1) wyszukaj w mapie pozycji bieżący liść l przypisany do b; (2) przypisz b nowy losowy liść l' i zaktualizuj mapę pozycji; (3) odczytaj wszystkie kubełki na ścieżce od liścia l do korzenia (log N kubełków); (4) znajdź blok b na odczytanej ścieżce lub w buforze stash; (5) zapisz z powrotem wszystkie bloki, które można przypisać do nowej ścieżki l', a pozostałe miejsca w kubełkach wypełnij blokami pozornymi. Serwer przy każdym dostępie widzi odczyt losowej ścieżki.

Path ORAM zachowuje ukrywanie wzorców dostępu, ponieważ każdy dostęp odczytuje i zapisuje dokładnie jedną ścieżkę od korzenia do liścia, niezależnie od tego, do którego bloku uzyskiwany jest dostęp. Ścieżka jest wyznaczana przez jednostajnie losowe przypisanie liścia, a nie przez zawartość ani adres bloku. Bloki pozorne wypełniają wszystkie puste miejsca w kubełkach, dzięki czemu każda ścieżka ma taką samą liczbę zajętych miejsc. Przeciwnik obserwujący serwer widzi wyłącznie dostępy do losowych ścieżek.

Każdy dostęp w Path ORAM wymaga odczytu i zapisu jednej ścieżki od korzenia do liścia: O(log N) kubełków zawierających po Z bloków. Przy rozmiarze bloku B i rozmiarze kubełka Z każdy dostęp przesyła O(Z * log N * B) bitów. Dla typowych parametrów (N = 2^20, Z = 5, B = 4KB) daje to około 400KB na dostęp, w porównaniu z 4KB przy dostępie do tekstu jawnego — narzut 100-krotny. Rekurencyjne mapy pozycji zmniejszają komunikację do O(log^2 N) w przeliczeniu na bloki.

Naiwna mapa pozycji wymaga przechowywania N wpisów po stronie klienta, co oznacza pamięć klienta O(N) — tak dużą jak cała baza danych. Rekurencyjna mapa pozycji zmniejsza pamięć po stronie klienta do O(log^2 N), przechowując samą mapę pozycji w mniejszym ORAM w sposób rekurencyjny. Rekurencja kończy się, gdy ORAM jest na tyle mały, że mieści się w buforze stash. Jest to standardowa technika umożliwiająca praktyczne zastosowanie Path ORAM dla dużych zbiorów danych.

Rozmiar bufora stash w Path ORAM rośnie, jeśli bloków nie można eksmitować na przypisane im ścieżki z powodu konfliktów ścieżek. Stefanov i in. dowiedli, że bufor stash przepełnia się (przekracza R bloków) z prawdopodobieństwem wykładniczo małym względem R — dokładniej, w standardowej analizie wynosi ono co najwyżej 14 * (0.6002)^R. Ustawienie R = 40 daje prawdopodobieństwo awarii wynoszące około 2^{-38}; wynik ten obowiązuje dla wszystkich sekwencji dostępów, również tych wybranych przez przeciwnika.

Przed powstaniem Path ORAM najlepsze praktyczne konstrukcje ORAM miały narzut O(log^3 N) (Shi et al. 2011, "Oblivious RAM with O((log N)^3) Worst-Case Cost"). Path ORAM zmniejszył go do O(log^2 N), oferując znacznie prostszą strukturę. Późniejsze prace (Circuit ORAM, OptORAMa) dodatkowo poprawiły stałe i granice asymptotyczne, ale Path ORAM pozostaje najszerzej implementowaną konstrukcją ze względu na swoją prostotę.

Path ORAM zaimplementowano w dziesiątkach systemów badawczych i produkcyjnych. ZeroTrace (Intel SGX + Path ORAM), Obladi (Path ORAM w pamięci chmurowej) i Opaque (Path ORAM w Apache Spark) to przykłady znaczących implementacji. Grupa Stanford zajmująca się bezpiecznymi obliczeniami utrzymuje implementację Path ORAM w języku C++ o otwartym kodzie źródłowym. AWS oferuje Path ORAM jako część prototypów badawczych Nitro Enclaves służących do analityki danych z zachowaniem prywatności.

Jaką rolę pełni mapa pozycji w Path ORAM?

Path ORAM organizuje pamięć serwera jako drzewo binarne, w którym każdy dostęp odczytuje i zapisuje jedną ścieżkę od korzenia do liścia. Mapa pozycji śledzi bieżące przypisanie każdego bloku do liścia, a bufor stash przechowuje ostatnio używane bloki. Każdy dostęp jest losowany przez przypisanie nowych losowych pozycji liści, dzięki czemu wszystkie dostępy widoczne dla serwera mają identyczny rozkład. Narzut komunikacyjny wynosi O(Z * log N) na dostęp. Rekurencyjne mapy pozycji zmniejszają pamięć klienta do O(log^2 N). Path ORAM jest najszerzej implementowaną konstrukcją ORAM.