@inproceedings{DS17,
 title = {Scaling ORAM for Secure Computation},
 author = {Jack Doerner and abhi shelat},
 booktitle = {CCS'2017},
 year = {2017},
}

eprint

We design and implement an Oblivious Random Access Memory (ORAM) data structure that is optimized for use in two-party secure computation protocols. We improve upon the access time of previous constructions by a factor up to ten, their memory overhead by a factor of one hundred or more, and their initialization time by a factor of thousands. We are able to instantiate ORAMs that hold $2^{34}$ bytes, and perform operations on them in seconds, which was not previously feasible with any implemented scheme.

Unlike prior ORAM constructions based on hierarchical hashing [GO96], permutation [GO96], or trees [SDSFRRYD13], our ORAM is derived from the new Function Secret Sharing scheme introduced by Boyle, Gilboa and Ishai [BGI16a,b]. This significantly reduces the amount of secure computation required to implement an ORAM access, albeit at the cost of $O(n)$ efficient \emph{local} memory operations.

We implement our construction and find that, despite its poor $O(n)$ asymptotic complexity, it still outperforms the fastest previously known constructions, Circuit ORAM [WCS15] and Square-root ORAM [ZWRGDEK16], for datasets that are 32 KiB or larger, and outperforms prior work on applications such as \emph{stable matching} [DES16] or \emph{binary search} [DKKKMRV12] by factors of two to ten.