Friday, March 23, 2018 - 10:30am to 12:00pm

Location:

Hewlett G882

Speaker:

Jack Doerner, Northeastern University

Seminar group:

Abstract: We design and implement a Distributed Oblivious Random Access Memory (DORAM) 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 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, permutation, or trees, our Distributed ORAM is derived from the new Function Secret Sharing scheme introduced by Boyle, Gilboa and Ishai. 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 and Square-root ORAM, for datasets that are 32 KiB or larger, and outperforms prior work on applications such as *stable matching* or *binary search* by factors of two to ten.

This is a joint work with Abhi Shelat

the paper is available here:

https://eprint.iacr.org/2017/8