Paper 2015/1065

Bucket ORAM: Single Online Roundtrip, Constant Bandwidth Oblivious RAM

Christopher Fletcher, Muhammad Naveed, Ling Ren, Elaine Shi, and Emil Stefanov

Abstract

Known Oblivious RAM (ORAM) constructions achieve either optimal bandwidth blowup or optimal latency (as measured by online roundtrips), but not both. We are the first to demonstrate an ORAM scheme, called Bucket ORAM, which attains the best of both worlds. Bucket ORAM simultaneously achieves a single online roundtrip as well as constant overall bandwidth blowup.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
Oblivious RAMconstant bandwidth blowupsingle online roundtrip
Contact author(s)
elaine @ cs cornell edu
History
2015-11-04: revised
2015-11-02: received
See all versions
Short URL
https://ia.cr/2015/1065
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1065,
      author = {Christopher Fletcher and Muhammad Naveed and Ling Ren and Elaine Shi and Emil Stefanov},
      title = {Bucket ORAM: Single Online Roundtrip, Constant Bandwidth Oblivious RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1065},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1065}},
      url = {https://eprint.iacr.org/2015/1065}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.