Circuit ORAM dan Kinerja Praktis

ORAM Sirkuit, yang diusulkan oleh Wang, Chan, dan Shi (2015), dirancang untuk meminimalkan biaya tambahan lebar pita sekaligus mudah diimplementasikan dalam kerangka kerja komputasi aman (sirkuit tersamar dan pembagian rahasia). Inovasi utamanya adalah mengurangi ukuran wadah menjadi Z = 2 blok (dibandingkan dengan Z = 5 pada ORAM Jalur), sehingga mengurangi separuh lebar pita dengan tetap mempertahankan probabilitas kegagalan yang dapat diabaikan. Prosedur pengusiran dirancang ulang agar dapat dinyatakan sebagai sirkuit Boolean kecil.

Pada ORAM Jalur dengan Z = 5, probabilitas luapan penyimpanan sementara dikendalikan dengan menyediakan beberapa blok per wadah untuk menampung penetapan acak blok ke berbagai jalur. ORAM Sirkuit membuktikan bahwa Z = 2 sudah memadai jika menggunakan prosedur pengusiran deterministik (pengusiran terdalam lebih dahulu), bukan pengusiran acak. Hal ini mengurangi separuh penyimpanan peladen dan biaya tambahan komunikasi dibandingkan dengan ORAM Jalur yang memiliki parameter keamanan sama.

ORAM Sirkuit dirancang khusus agar prosedur pengusirannya dapat dinyatakan sebagai sirkuit Boolean yang efisien. Dalam protokol komputasi aman (sirkuit tersamar, SPDZ), akses ORAM itu sendiri harus dievaluasi tanpa membocorkan pola akses—peladen yang menjalankan komputasi tidak boleh mengetahui lokasi memori yang diakses. Sirkuit pengusiran deterministik ORAM Sirkuit yang sederhana jauh lebih efisien untuk disamarkan daripada prosedur pengusiran ORAM Jalur.

Untuk basis data yang terdiri atas N blok berukuran B byte, ORAM Sirkuit memerlukan 2 * log N * B byte per akses (membaca dan menulis satu jalur dengan Z = 2 blok per wadah). Untuk N = 2^20 blok yang masing-masing berukuran 4KB, jumlahnya 160KB per akses, dibandingkan dengan 400KB untuk ORAM Jalur (Z=5). Biaya tambahan lebar pita dibandingkan dengan teks biasa sekitar 40 kali untuk parameter umum, turun dari 100 kali pada ORAM Jalur.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) menggunakan ORAM Sirkuit untuk membangun versi tanpa pola akses dari struktur data tingkat tinggi: daftar tertaut tanpa pola akses, peta tanpa pola akses (tabel pencincangan), dan antrean prioritas tanpa pola akses. Struktur ini memungkinkan komputasi tanpa pola akses pada data dinamis tanpa mengungkap pola akses. Oblix berjalan di dalam enklave Intel SGX dan ditujukan untuk irisan himpunan privat yang aman serta kueri basis data privat.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) memperluas Path ORAM untuk mendukung akses asinkron dengan laju pemrosesan tinggi melalui pemrosesan beberapa permintaan ORAM secara paralel dan pengelompokan pengeluaran blok dari jalur. Dengan menggabungkan akses ke jalur yang sama, TaoStore mencapai laju pemrosesan (permintaan per detik) yang jauh lebih tinggi daripada konstruksi ORAM sinkron, sehingga cocok untuk peladen penyimpanan awan dengan banyak klien yang mengakses secara bersamaan.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) membangun sistem penyimpanan transaksional lengkap di atas Path ORAM. Obladi mendukung transaksi ACID pada penyimpanan terenkripsi yang menyamarkan pola akses. Sistem ini memperkenalkan eksekusi tertunda: transaksi dikelompokkan ke dalam beberapa epoch dan dijalankan dengan cara yang menyembunyikan catatan mana yang secara spesifik diakses dalam setiap epoch. Obladi berjalan sebagai proksi tepercaya antara klien dan sistem penyimpanan awan sisi server yang tidak tepercaya.

Untuk ORAM berukuran 1GB (262,144 blok berukuran 4KB) yang diterapkan di AWS, dengan klien mengakses blok melalui internet, waktu tunda Path ORAM kira-kira 50-200ms per akses (didominasi oleh waktu perjalanan pulang-pergi untuk 18 akses wadah, yaitu log N = 18). Dengan pengambilan wadah secara paralel, waktu tunda ini dapat dikurangi. Untuk aplikasi SGX lokal dengan ORAM di RAM, waktu tundanya berkisar antara 1-10ms per akses, yang dapat diterima oleh banyak aplikasi komputasi aman.

Beban tambahan lebar pita ORAM sangat bergantung pada pola akses. Untuk ORAM penyimpanan awan berukuran 1TB dengan blok berukuran 1MB, setiap akses mentransfer sekitar 25MB (beban tambahan 25 kali untuk 25 tingkat, yaitu log N = 25). Untuk blok kecil berukuran 4KB, beban tambahan per akses lebih rendah dalam jumlah bita absolut, tetapi lebih tinggi secara relatif. Organisasi yang menerapkan ORAM harus menganggarkan peningkatan penggunaan lebar pita sebesar 20-50 kali serta memastikan bahwa koneksi jaringan dan biaya keluarnya data dari awan telah diperhitungkan.

Alternatif ORAM untuk privasi akses adalah perangkat keras tepercaya: Intel SGX atau AMD SEV menyediakan lingkungan eksekusi tepercaya tempat bahkan OS induk tidak dapat mengamati komputasi atau pola akses memori, dengan pertahanan yang sesuai. SGX tanpa ORAM tetap membocorkan pola akses tingkat halaman kepada perangkat keras, sehingga ORAM di dalam SGX diperlukan untuk perlindungan penuh. Dibandingkan dengan ORAM murni, perangkat keras tepercaya mengurangi beban tambahan lebar pita, tetapi mengharuskan Anda memercayai produsen perangkat keras dan rantai pasoknya.

ORAM tepat digunakan ketika: penyerang dapat mengamati pola akses di sisi server (penyedia komputasi awan atau penyewa bersama), sensitivitas data membenarkan beban tambahan lebar pita sebesar 20-50 kali, dan pola akses itu sendiri dapat mengungkapkan informasi sensitif. Untuk sebagian besar aplikasi, enkripsi standar dengan pengelolaan kunci yang cermat sudah memadai. ORAM adalah alat khusus untuk skenario dengan tingkat keamanan tinggi: analisis data medis, pembelajaran mesin privat, sistem perdagangan finansial, dan basis data penegakan hukum.

Berapa ukuran wadah yang digunakan Circuit ORAM, dan mengapa hal ini merupakan peningkatan dibandingkan Path ORAM?

Circuit ORAM mengurangi ukuran wadah menjadi Z=2 (dibandingkan Z=5 pada Path ORAM), sehingga mengurangi lebar pita hingga setengahnya melalui pengeluaran deterministik dari tingkat terdalam. ORAM ini dirancang untuk digunakan di dalam komputasi aman dengan sirkuit tersamarkan. Beban praktisnya adalah peningkatan penggunaan lebar pita sebesar 40 kali untuk parameter umum. Sistem produksi mencakup Oblix (SGX + struktur data tersamar), TaoStore (ORAM yang dikelompokkan untuk laju pemrosesan tinggi), dan Obladi (ORAM transaksional). ORAM di dalam SGX diperlukan karena SGX saja membocorkan pola akses tingkat halaman.