Enclave-based oblivious RAM using Intel's SGX

Abstract

Oblivious RAM (ORAM) schemes exist in order to protect the access pattern of data in a data store. Under an ORAM algorithm, a client accesses a data store in such a way that does not reveal which item it is interested in. This is typically accomplished by accessing multiple items each access and periodically reshuffling some, or all, of the data in the data-store. While many recent schemes make the ORAM computation complexity feasible, the performance of practical implementations is still largely limited by computational and storage limitations of the client as well as the bandwidth available between the client and the data store. In a cloud computing environment, where it is commonly assumed that the client is underpowered and you must pay by the gigabyte for data transfer, traditional ORAM methods are not optimal. Intel's Software Guard Extensions (SGX) provide a new opportunity for ORAM implementations that can safely outsource the computational and bandwidth requirements along with the data itself, meaning that the client can be very limited and still attain high performance. In this work, we develop efficient techniques for constructing ORAMs that takes advantage of the SGX enclave technology. We demonstrate implementations of multiple ORAM schemes (linear, square root, and path ORAM) using Intel's SGX. We discuss the limitations of SGX as they pertain to implementing ORAM, and discuss alterations to the standard algorithms to overcome these limitations. We then evaluate the performance of our techniques.