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
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
-
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} }