Square-Root ORAM

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. We developed a new version of the classical square-root ORAM of Goldreich and Ostrovsky suited for use in secure computation. It has over 100x lower initialization cost than the best previous schemes, and provides benefits over linear scan for just 8 blocks of data. Our scheme outperforms alternate approaches across a wide range of parameters, often by several orders of magnitude.

Samee Zahur presented the results at IEEE Symposium on Security and Privacy (“Oakland”) 2016. The full paper is:

Samee Zahur, Xiao Wang, Mariana Raykova, Adrià Gascón, Jack Doerner, David Evans, Jonathan Katz. Revisiting Square-Root ORAM Efficient Random Access in Multi-Party Computation. In 37th IEEE Symposium on Security and Privacy (“Oakland”). San Jose, CA. 23-25 May 2016.

For more (including source code and benchmarks), see https://oblivc.org/sqoram/.