HomeResearchSoftware & CodeExposition
Revisiting Square-Root ORAM
in IEEE S&P 2016
Samee Zahur • Xiao Wang • Mariana Raykova • Adrià Gascón • Jack Doerner • David Evans • Jonathan Katz

Hiding memory access patterns is required for secure computation, but remains prohibitively expensive for many interesting applications. Prior work has either developed custom algorithms that minimize the need for data-dependant memory access, or proposed the use of Oblivious RAM (ORAM) to provide a general-purpose solution. However, most ORAMs are designed for client-server scenarios, and provide only asymptotic benefits in secure computation. Even the best prior schemes show concrete benefits over naïve linear scan only for array sizes greater than 100. This immediately implies each ORAM access is 100 times slower than a single access at a known location. Even then, prior evaluations ignore the substantial initialization cost of existing schemes.

We show how the classical square-root ORAM of Goldreich and Ostrovsky can be modified to overcome these problems, even though it is asymptotically worse than the best known schemes. Specifically, we show a design that has over 100 times lower initialization cost, and provides benefits over linear scan for just 8 blocks of data. For all benchmark applications we tried, including Gale-Shapley stable matching and the scrypt key derivation function, our scheme outperforms alternate approaches across a wide range of parameters, often by several orders of magnitude.

Scaling ORAM for Secure Computation
in ACM CCS 2017 (best paper)
Jack Doerner • abhi shelat

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 234 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.

Secure Stable Matching at Scale
in ACM CCS 2016 • poster in IEEE S&P 2016
Jack Doerner • David Evans • abhi shelat

When a group of individuals and organizations wish to compute a stable matching—for example, when medical students are matched to medical residency programs—they often outsource the computation to a trusted arbiter in order to preserve the privacy of participants' preferences. Secure multi-party computation offers the possibility of private matching processes that do not rely on any common trusted third party. However, stable matching algorithms have previously been considered infeasible for execution in a secure multi-party context on non-trivial inputs because they are computationally intensive and involve complex data-dependent memory access patterns.

We adapt the classic Gale-Shapley algorithm for use in such a context, and show experimentally that our modifications yield a lower asymptotic complexity and more than an order of magnitude in practical cost improvement over previous techniques. Our main improvements stem from designing new oblivious data structures that exploit the properties of the matching algorithms. We apply a similar strategy to scale the Roth-Peranson instability chaining algorithm, currently in use by the National Resident Matching Program. The resulting protocol is efficient enough to be useful at the scale required for matching medical residents nationwide, taking just over 18 hours to complete an execution simulating the 2016 national resident match with more than 35,000 participants and 30,000 residency slots.

Jack Doerner • abhi shelat • David Evans

Zeroledge is a zero-knowledge proof system by which a bank or exchange can prove properties about its liabilities without leaking any information about individual accounts or more details than necessary about its business. Homomorphism is used to demonstrate certain properties of public commitments to all account balances and to their sum, and verification is distributed among account holders.

Zeroledge was my undergraduate thesis for the University of Virginia School of Engineering. It was intended to supplant the prior merkle-tree based proof of solvency, while correcting its deficiencies and introducing new and useful guarantees.

Although both a paper and an efficient and fully functional impelementation are complete, this research has been subsumed by another effort from Dagher et al, and it will therefore remain unpublished.