Path ORAM: Menyembunyikan Akses Memori

Path ORAM, yang dicadangkan oleh Stefanov, van Dijk, Shi, Fletcher, Ren, Yu dan Devadas (2013), ialah binaan ORAM yang paling berpengaruh dari segi praktikal. Ia menyusun storan pelayan sebagai pepohon binari yang terdiri daripada bekas, dengan setiap daun mewakili satu kedudukan untuk blok data. Path ORAM mencapai overhed komunikasi O(log^2 N) bagi setiap capaian dalam bentuk asasnya dan cukup mudah untuk dilaksanakan dalam beberapa ratus baris kod.

Peta kedudukan ialah struktur data pada klien yang memetakan setiap alamat blok logik kepada nod daun dalam pepohon binari. Bagi pangkalan data yang mempunyai N blok dengan pepohon setinggi L = log N, peta kedudukan ialah tatasusunan yang mengandungi N indeks daun. Sebelum mencapai blok b, klien mencari daun yang sedang ditetapkan kepadanya dalam peta kedudukan dan menetapkan daun rawak baharu kepadanya. Laluan daun lama akan dibaca daripada pelayan dan ditulis semula kepadanya.

Penimbal ialah penimbal kecil pada klien (biasanya 20-40 blok) yang menyimpan sementara blok yang telah dibaca daripada pelayan tetapi belum ditulis semula. Apabila sesuatu blok dibaca, blok itu dikeluarkan daripada laluannya dan diletakkan dalam penimbal. Selepas blok itu dicapai dan mungkin diubah suai, semua blok dalam penimbal yang boleh diletakkan pada laluan baharu akan ditulis semula. Blok yang tidak dapat dimuatkan pada sesuatu laluan akan kekal dalam penimbal.

Storan pelayan ialah pepohon binari lengkap dengan L+1 aras (L = log N). Setiap nod (bekas) menyimpan Z blok (biasanya Z = 5). Daun mewakili kedudukan untuk blok data. Terdapat N nod daun, maka jumlah keseluruhan nod ialah 2N-1 dan jumlah storan pelayan ialah O(NZ). Setiap laluan dari daun ke akar mempunyai log N nod dan boleh menyimpan Z*log N blok, sekali gus menyediakan kapasiti untuk strategi pengusiran laluan.

Untuk membaca blok b: (1) cari daun semasa l bagi b dalam peta kedudukan; (2) tetapkan daun rawak baharu l' kepada b dan kemas kini peta kedudukan; (3) baca semua bekas pada laluan dari daun l ke akar (log N bekas); (4) cari blok b dalam laluan yang dibaca atau dalam penimbal; (5) tulis semula semua blok yang boleh ditetapkan kepada laluan baharu l', dan isi ruang bekas yang selebihnya dengan blok olok-olok. Pelayan melihat bacaan laluan rawak setiap kali.

Path ORAM mengekalkan sifat tanpa kebocoran kerana setiap capaian membaca dan menulis tepat satu laluan dari akar ke daun, tanpa mengira blok yang dicapai. Laluan tersebut ditentukan oleh penetapan daun yang rawak seragam, bukannya oleh kandungan atau alamat blok. Blok olok-olok mengisi ruang bekas yang kosong supaya setiap laluan mempunyai bilangan ruang berisi yang sama. Penyerang yang memerhati pelayan hanya melihat capaian laluan rawak.

Setiap capaian Path ORAM memerlukan pembacaan dan penulisan satu laluan dari akar ke daun: O(log N) bekas yang setiap satunya mengandungi Z blok. Dengan saiz blok B dan saiz bekas Z, setiap capaian memindahkan O(Z * log N * B) bit. Bagi parameter biasa (N = 2^20, Z = 5, B = 4KB), jumlahnya kira-kira 400KB bagi setiap capaian, berbanding 4KB untuk capaian teks biasa — overhed 100x. Peta kedudukan rekursif mengurangkannya kepada komunikasi O(log^2 N) dari segi bilangan blok.

Peta kedudukan naif memerlukan N entri yang disimpan pada klien, iaitu storan klien O(N) — sebesar keseluruhan pangkalan data. Peta kedudukan rekursif mengurangkan storan klien kepada O(log^2 N) dengan menyimpan peta kedudukan itu sendiri dalam ORAM yang lebih kecil secara rekursif. Rekursi berhenti apabila ORAM tersebut cukup kecil untuk dimuatkan dalam penimbal. Inilah teknik piawai untuk menjadikan Path ORAM praktikal bagi set data yang besar.

Saiz penimbal dalam Path ORAM meningkat apabila blok tidak dapat diusir ke laluan yang ditetapkan kepadanya disebabkan konflik laluan. Stefanov dan rakan-rakan membuktikan bahawa penimbal melimpah (melebihi R blok) dengan kebarangkalian yang sangat kecil secara eksponen terhadap R — khususnya, paling banyak 14 * (0.6002)^R dalam analisis piawai. Dengan menetapkan R = 40, kebarangkalian kegagalan adalah kira-kira 2^{-38}, dan keputusan ini terpakai kepada semua urutan capaian termasuk urutan yang dipilih secara berlawanan oleh penyerang.

Sebelum Path ORAM, binaan ORAM praktikal terbaik mempunyai overhed O(log^3 N) (Shi et al. 2011, "RAM tanpa pengetahuan dengan Kos Kes Terburuk O((log N)^3)"). Path ORAM mengurangkannya kepada O(log^2 N) dengan struktur yang jauh lebih ringkas. Kerja seterusnya (Circuit ORAM, OptORAMa) menambah baik pemalar dan batas asimptotik, tetapi Path ORAM kekal sebagai binaan yang paling banyak dilaksanakan kerana kesederhanaannya.

Path ORAM telah dilaksanakan dalam berpuluh-puluh sistem penyelidikan dan pengeluaran. ZeroTrace (Intel SGX + Path ORAM), Obladi (Path ORAM pada storan awan) dan Opaque (Path ORAM pada Apache Spark) ialah antara pelaksanaan yang terkenal. Kumpulan pengiraan selamat Stanford menyelenggara pelaksanaan Path ORAM C++ sumber terbuka. AWS menawarkan Path ORAM sebagai sebahagian daripada prototaip penyelidikan Nitro Enclaves mereka untuk analitik data yang memelihara privasi.

Path ORAM menyusun storan pelayan sebagai pepohon binari yang setiap capaiannya membaca atau menulis satu laluan dari akar ke daun. Peta kedudukan menjejaki penetapan daun semasa bagi setiap blok, manakala penimbal menyimpan sementara blok yang baru dicapai. Setiap capaian dirawakkan dengan menetapkan kedudukan daun rawak baharu, lalu menjadikan semua capaian yang dapat dilihat pelayan mempunyai taburan yang sama. Overhed komunikasi ialah O(Z * log N) bagi setiap capaian. Peta kedudukan rekursif mengurangkan storan klien kepada O(log^2 N). Path ORAM ialah binaan ORAM yang paling banyak dilaksanakan.