Scaling ORAM for Secure Computation

We design and implement a Distributed Oblivious Random Access Memory (DORAM) data structure that is optimized for use in twoparty secure computation protocols. We improve upon the access time of previous constructions by a factor of 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 [19] , permutation [19] , or trees [39], our Distributed ORAM is derived from the new Function Secret Sharing scheme introduced by Boyle, Gilboa and Ishai [11, 12] . This significantly reduces the amount of secure computation required to implement an ORAM access, albeit at the cost of O (n) efficient 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 [42] and Square-root ORAM [55], for datasets that are 32 KiB or larger, and outperforms prior work on applications such as stable matching [16] or binary search [23] by factors of two to ten.