Paper 2018/005

Simple and Efficient Two-Server ORAM

S. Dov Gordon, Jonathan Katz, and Xiao Wang

Abstract

We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations. A practical instantiation of our protocol has excellent concrete parameters: for storing an -element array of arbitrary size data blocks with statistical security parameter , the servers each store encrypted blocks, the client stores blocks, and the total communication per logical access is roughly encrypted blocks.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Asiacrypt 2018
Keywords
ORAMsingle-roundmulti-party computationRAM model
Contact author(s)
wangxiao @ cs umd edu
History
2018-09-05: last of 3 revisions
2018-01-02: received
See all versions
Short URL
https://ia.cr/2018/005
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/005,
      author = {S.  Dov Gordon and Jonathan Katz and Xiao Wang},
      title = {Simple and Efficient Two-Server {ORAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/005},
      year = {2018},
      url = {https://eprint.iacr.org/2018/005}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.