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.

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 began as my undergraduate thesis for the University of Virginia School of Engineering, and I continued the research as an employee upon my graduation. It is intended to supplant Gregory Maxwell's 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. It will therefore remain unpublished.