Revisiting Square-Root ORAM: Efficient Random Access in Multi-party Computation

Samee Zahur, Xiao Wang, Mariana Raykova, Adria Gascon, Jack Doerner, David Evans, Jonathan Katz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

Abstract

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 100x 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE Symposium on Security and Privacy, SP 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages218-234
Number of pages17
ISBN (Electronic)9781509008247
DOIs
Publication statusPublished - Aug 16 2016
Event2016 IEEE Symposium on Security and Privacy, SP 2016 - San Jose, United States
Duration: May 23 2016May 25 2016

Publication series

NameProceedings - 2016 IEEE Symposium on Security and Privacy, SP 2016

Conference

Conference2016 IEEE Symposium on Security and Privacy, SP 2016
CountryUnited States
CitySan Jose
Period5/23/165/25/16

    Fingerprint

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications
  • Software

Cite this

Zahur, S., Wang, X., Raykova, M., Gascon, A., Doerner, J., Evans, D., & Katz, J. (2016). Revisiting Square-Root ORAM: Efficient Random Access in Multi-party Computation. In Proceedings - 2016 IEEE Symposium on Security and Privacy, SP 2016 (pp. 218-234). [7546504] (Proceedings - 2016 IEEE Symposium on Security and Privacy, SP 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SP.2016.21