Paper 2017/827

Scaling ORAM for Secure Computation

Jack Doerner and abhi shelat

Abstract

We design and implement a Distributed Oblivious Random Access Memory (ORAM) 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2017
DOI
10.1145/3133956.3133967
Keywords
Oblivious RAMPrivate Information RetrievalSecure Multi-Party Computation
Contact author(s)
j @ ckdoerner net
History
2018-01-09: last of 3 revisions
2017-08-31: received
See all versions
Short URL
https://ia.cr/2017/827
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/827,
      author = {Jack Doerner and abhi shelat},
      title = {Scaling {ORAM} for Secure Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/827},
      year = {2017},
      doi = {10.1145/3133956.3133967},
      url = {https://eprint.iacr.org/2017/827}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.