Circuit ORAM i wydajność praktyczna

Circuit ORAM, zaproponowany przez Wanga, Chana i Shiego (2015), zaprojektowano z myślą o minimalizacji narzutu przepustowości oraz prostocie implementacji w ramach bezpiecznych obliczeń (garbled circuits i secret sharing). Jego kluczową innowacją jest zmniejszenie rozmiaru kubełka do Z = 2 bloków (w porównaniu z Z = 5 w Path ORAM), co zmniejsza o połowę przepustowość przy zachowaniu pomijalnie małego prawdopodobieństwa awarii. Procedurę eksmisji przeprojektowano tak, aby można ją było wyrazić jako mały obwód boolowski.

W Path ORAM z Z = 5 prawdopodobieństwo przepełnienia bufora stash jest kontrolowane przez przechowywanie wielu bloków w kubełku, aby pomieścić losowo przypisane bloki na ścieżkach. Circuit ORAM dowodzi, że Z = 2 wystarcza przy zastosowaniu deterministycznej procedury eksmisji (deep-first eviction) zamiast eksmisji losowej. Zmniejsza to o połowę pamięć serwera i narzut komunikacyjny w porównaniu z Path ORAM o tych samych parametrach bezpieczeństwa.

Circuit ORAM zaprojektowano specjalnie tak, aby jego procedurę eksmisji można było wyrazić jako wydajny obwód boolowski. W protokołach bezpiecznych obliczeń (garbled circuits, SPDZ) sam dostęp ORAM musi być obliczany w sposób nieujawniający — serwer wykonujący obliczenia nie może dowiedzieć się, do której lokalizacji pamięci uzyskiwany jest dostęp. Prosty deterministyczny obwód eksmisji Circuit ORAM jest znacznie wydajniejszy do przekształcenia w garbled circuit niż procedura eksmisji Path ORAM.

Dla bazy danych zawierającej N bloków o rozmiarze B bajtów Circuit ORAM wymaga 2 * log N * B bajtów na dostęp (odczytu i zapisu jednej ścieżki z Z = 2 blokami w kubełku). Dla N = 2^20 bloków po 4KB każdy daje to 160KB na dostęp, w porównaniu z 400KB w Path ORAM (Z=5). Dla typowych parametrów narzut przepustowości względem tekstu jawnego wynosi około 40x, czyli mniej niż 100x w Path ORAM.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) wykorzystuje Circuit ORAM do budowy obliviousnych wersji wysokopoziomowych struktur danych: obliviousnych list wiązanych, obliviousnych map (tablic mieszających) oraz obliviousnych kolejek priorytetowych. Struktury te umożliwiają wykonywanie obliczeń na dynamicznych danych bez ujawniania wzorców dostępu. Oblix działa wewnątrz enklaw Intel SGX i jest przeznaczony do bezpiecznego przecięcia zbiorów oraz prywatnych zapytań do baz danych.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) rozszerza Path ORAM o obsługę wysokoprzepustowego dostępu asynchronicznego, przetwarzając wiele żądań ORAM równolegle i grupując eksmisje ścieżek. Łącząc dostępy do tej samej ścieżki, TaoStore osiąga znacznie wyższą przepustowość (liczbę żądań na sekundę) niż synchroniczne konstrukcje ORAM, dzięki czemu nadaje się do serwerów pamięci masowej w chmurze obsługujących wielu równoczesnych klientów.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) tworzy pełny system pamięci transakcyjnej oparty na Path ORAM. Obladi obsługuje transakcje ACID na zaszyfrowanej pamięci masowej, która ukrywa wzorce dostępu. Wprowadza odroczone wykonywanie: transakcje są grupowane w epoki i wykonywane tak, aby ukryć, do których konkretnych rekordów uzyskano dostęp w obrębie każdej epoki. Obladi działa jako zaufany serwer proxy między klientami a niezaufanym backendem pamięci masowej w chmurze.

W przypadku ORAM o rozmiarze 1GB (262,144 bloków po 4KB) wdrożonego w AWS, gdy klient uzyskuje dostęp do bloków przez internet, opóźnienie Path ORAM wynosi około 50–200ms na dostęp. Dominuje w nim czas podróży w obie strony potrzebny na wykonanie log N = 18 dostępów do kubełków. Dzięki równoległemu pobieraniu kubełków można je zmniejszyć. W lokalnych aplikacjach SGX, w których ORAM znajduje się w pamięci RAM, opóźnienie wynosi od 1 do 10ms na dostęp, co jest akceptowalne w wielu zastosowaniach bezpiecznych obliczeń.

Narzut przepustowości ORAM w dużej mierze zależy od wzorców dostępu. W przypadku ORAM pamięci masowej w chmurze o pojemności 1TB i blokach 1MB każdy dostęp przesyła około 25MB (25-krotny narzut dla log N = 25 poziomów). Dla małych bloków (4KB) narzut na dostęp jest mniejszy w wartościach bezwzględnych, ale większy względnie. Organizacje wdrażające ORAM muszą uwzględnić 20–50-krotne zwiększenie transferu oraz upewnić się, że ich łącza sieciowe i koszty transferu wychodzącego z chmury są na to przygotowane.

Alternatywą dla ORAM w zakresie prywatności dostępu jest zaufany sprzęt: Intel SGX lub AMD SEV zapewnia zaufane środowisko wykonywania, w którym nawet system operacyjny hosta nie może obserwować obliczeń ani wzorców dostępu do pamięci, przy zastosowaniu odpowiednich zabezpieczeń. SGX bez ORAM nadal nie ukrywa przed sprzętem wzorców dostępu na poziomie stron, dlatego do pełnej ochrony potrzebny jest ORAM wewnątrz SGX. W porównaniu z rozwiązaniem opartym wyłącznie na ORAM zaufany sprzęt zmniejsza narzut przepustowości, ale wymaga zaufania producentowi sprzętu i łańcuchowi dostaw.

ORAM jest odpowiedni, gdy przeciwnik obserwuje wzorce dostępu po stronie serwera (dostawca chmury, współdzierżawca), wrażliwość danych uzasadnia 20–50-krotny narzut przepustowości, a sam wzorzec dostępu ujawniałby poufne informacje. W większości aplikacji wystarcza standardowe szyfrowanie z właściwym zarządzaniem kluczami. ORAM jest wyspecjalizowanym narzędziem do zastosowań wymagających wysokiego poziomu bezpieczeństwa, takich jak analiza danych medycznych, prywatne uczenie maszynowe, systemy handlu finansowego i bazy danych organów ścigania.

Jaki rozmiar kubełka stosuje Circuit ORAM i dlaczego jest to ulepszenie w porównaniu z Path ORAM?

Circuit ORAM zmniejsza rozmiar kubełka do Z=2 (w porównaniu z Z=5 w Path ORAM), o połowę redukując transfer dzięki deterministycznej eksmisji w głąb. Został zaprojektowany do użycia wewnątrz bezpiecznych obliczeń z wykorzystaniem obwodów zgarblowanych. Dla typowych parametrów praktyczny narzut wynosi 40-krotne zwiększenie transferu. Systemy produkcyjne obejmują Oblix (SGX + obiekty danych ukrywające wzorce dostępu), TaoStore (wysokoprzepustowy ORAM z przetwarzaniem wsadowym) i Obladi (transakcyjny ORAM). ORAM wewnątrz SGX jest niezbędny, ponieważ sam SGX ujawnia wzorce dostępu na poziomie stron.