Path ORAM: Menyembunyikan Akses Memori

ORAM Jalur, yang diusulkan oleh Stefanov, van Dijk, Shi, Fletcher, Ren, Yu, dan Devadas (2013), adalah konstruksi ORAM yang paling berpengaruh secara praktis. Konstruksi ini mengatur penyimpanan peladen sebagai pohon biner yang terdiri atas wadah, dengan setiap daun mewakili posisi sebuah blok data. ORAM Jalur mencapai biaya tambahan komunikasi O(log^2 N) per akses dalam bentuk dasarnya dan cukup sederhana untuk diimplementasikan dalam beberapa ratus baris kode.

Peta posisi adalah struktur data sisi klien yang memetakan setiap alamat blok logis ke simpul daun dalam pohon biner. Untuk basis data berisi N blok dengan pohon setinggi L = log N, peta posisi adalah larik indeks daun. Sebelum mengakses blok b, klien mencari daun yang saat ini ditetapkan untuknya dalam peta posisi, lalu menetapkan daun acak baru. Jalur daun lama akan dibaca dari peladen dan ditulis kembali ke sana.

Penyimpanan sementara adalah penyangga kecil di sisi klien (biasanya 20-40 blok) yang menampung sementara blok yang telah dibaca dari peladen tetapi belum ditulis kembali. Ketika sebuah blok dibaca, blok tersebut dikeluarkan dari jalurnya dan ditempatkan dalam penyimpanan sementara. Setelah diakses dan mungkin diubah, semua blok dalam penyimpanan sementara yang dapat ditempatkan pada jalur baru ditulis kembali. Blok yang tidak dapat dimuat pada suatu jalur tetap berada dalam penyimpanan sementara.

Penyimpanan peladen adalah pohon biner lengkap dengan L+1 tingkat (L = log N). Setiap simpul (wadah) menampung Z blok (biasanya Z = 5). Daun mewakili posisi untuk blok data. Ada N simpul daun, sehingga terdapat 2N-1 simpul secara keseluruhan dan penyimpanan peladen total O(NZ). Setiap jalur dari daun ke akar memiliki log N simpul dan dapat menampung Z*log N blok, sehingga menyediakan kapasitas untuk strategi pengeluaran blok dari jalur.

Untuk membaca blok b: (1) cari daun l saat ini untuk b dalam peta posisi; (2) tetapkan daun acak baru l' untuk b dan perbarui peta posisi; (3) baca semua wadah pada jalur dari daun l ke akar (log N wadah); (4) cari blok b pada jalur yang dibaca atau dalam penyimpanan sementara; (5) tulis kembali semua blok yang dapat ditempatkan pada jalur baru l', lalu isi slot wadah yang tersisa dengan blok tiruan. Peladen melihat pembacaan jalur acak setiap kali.

ORAM Jalur mempertahankan sifat tanpa pola akses karena setiap akses membaca dan menulis tepat satu jalur dari akar ke daun, terlepas dari blok mana yang diakses. Jalur tersebut ditentukan oleh penetapan daun yang acak seragam, bukan oleh isi atau alamat blok. Blok tiruan mengisi slot wadah yang kosong agar setiap jalur memiliki jumlah slot terisi yang sama. Penyerang yang mengamati peladen hanya melihat akses jalur acak.

Setiap akses ORAM Jalur memerlukan pembacaan dan penulisan satu jalur dari akar ke daun: O(log N) wadah yang masing-masing berisi Z blok. Dengan ukuran blok B dan ukuran wadah Z, setiap akses memindahkan O(Z * log N * B) bit. Untuk parameter umum (N = 2^20, Z = 5, B = 4KB), jumlahnya sekitar 400KB per akses, dibandingkan dengan 4KB untuk akses teks biasa—biaya tambahan 100 kali. Peta posisi rekursif mengurangi komunikasi menjadi O(log^2 N) jika dihitung dalam satuan blok.

Peta posisi naif memerlukan N entri yang disimpan di sisi klien, yaitu penyimpanan klien O(N)—sebesar seluruh basis data. Peta posisi rekursif mengurangi penyimpanan klien menjadi O(log^2 N) dengan menyimpan peta posisi itu sendiri dalam ORAM yang lebih kecil secara rekursif. Rekursi berhenti ketika ORAM tersebut cukup kecil untuk dimuat dalam penyimpanan sementara. Ini adalah teknik standar untuk membuat ORAM Jalur praktis bagi kumpulan data besar.

Ukuran penyimpanan sementara dalam ORAM Jalur bertambah jika blok tidak dapat dikeluarkan ke jalur yang ditetapkan karena konflik jalur. Stefanov et al. membuktikan bahwa penyimpanan sementara meluap (melebihi R blok) dengan probabilitas yang sangat kecil secara eksponensial terhadap R—secara khusus, paling besar 14 * (0.6002)^R untuk analisis standar. Menetapkan R = 40 menghasilkan probabilitas kegagalan sekitar 2^{-38}, dan hal ini berlaku untuk semua urutan akses, termasuk yang dipilih oleh penyerang.

Sebelum ORAM Jalur, konstruksi ORAM praktis terbaik memiliki biaya tambahan O(log^3 N) (Shi et al. 2011, "RAM Tanpa Pola Akses dengan Biaya Kasus Terburuk O((log N)^3)"). ORAM Jalur menguranginya menjadi O(log^2 N) dengan struktur yang jauh lebih sederhana. Penelitian selanjutnya (ORAM Sirkuit, OptORAMa) semakin meningkatkan konstanta dan batas asimtotik, tetapi ORAM Jalur tetap menjadi konstruksi yang paling banyak diimplementasikan karena kesederhanaannya.

ORAM Jalur telah diimplementasikan dalam puluhan sistem riset dan produksi. ZeroTrace (Intel SGX + ORAM Jalur), Obladi (ORAM Jalur pada penyimpanan awan), dan Opaque (ORAM Jalur pada Apache Spark) adalah implementasi yang terkenal. Kelompok komputasi aman Stanford memelihara implementasi ORAM Jalur C++ sumber terbuka. AWS menawarkan ORAM Jalur sebagai bagian dari prototipe riset Nitro Enclaves mereka untuk analitik data yang menjaga privasi.

Apa peran peta posisi dalam ORAM Jalur?

ORAM Jalur mengatur penyimpanan peladen sebagai pohon biner, yang setiap aksesnya membaca atau menulis satu jalur dari akar ke daun. Peta posisi melacak penetapan daun terkini setiap blok; penyimpanan sementara menyangga blok yang baru diakses. Setiap akses diacak dengan menetapkan posisi daun acak baru, sehingga semua akses yang terlihat oleh peladen memiliki distribusi yang identik. Biaya tambahan komunikasi adalah O(Z * log N) per akses. Peta posisi rekursif mengurangi penyimpanan klien menjadi O(log^2 N). ORAM Jalur adalah konstruksi ORAM yang paling banyak diimplementasikan.