Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM

Srinivas Devadas; Marten van Dijk; Christopher W.  Fletcher; Ling Ren; Elaine Shi; Daniel Wichs

Paper 2015/005

Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM

Srinivas Devadas, Marten van Dijk, Christopher W. Fletcher, Ling Ren, Elaine Shi, and Daniel Wichs

Abstract

We present Onion ORAM, an Oblivious RAM (ORAM) with constant worst-case bandwidth blowup that leverages poly-logarithmic server computation to circumvent the logarithmic lower bound on ORAM bandwidth blowup. Our construction does not require fully homomorphic encryption, but employs an additively homomorphic encryption scheme such as the Damgard-Jurik cryptosystem, or alternatively a BGV-style somewhat homomorphic encryption scheme without bootstrapping. At the core of our construction is an ORAM scheme that has "shallow circuit depth" over the entire history of ORAM accesses. We also propose novel techniques to achieve security against a malicious server, without resorting to expensive and non-standard techniques such as SNARKs. To the best of our knowledge, Onion ORAM is the first concrete instantiation of a constant bandwidth blowup ORAM under standard assumptions (even for the semi-honest setting).

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in TCC 2016
Keywords: ORAM Cryptographic Protocols
Contact author(s): cwfletch @ mit edu
History: 2015-11-07: last of 8 revisions; 2015-01-05: received; See all versions
Short URL: https://ia.cr/2015/005
License: CC BY

BibTeX

@misc{cryptoeprint:2015/005,
      author = {Srinivas Devadas and Marten van Dijk and Christopher W.  Fletcher and Ling Ren and Elaine Shi and Daniel Wichs},
      title = {Onion {ORAM}: A Constant Bandwidth Blowup Oblivious {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/005},
      year = {2015},
      url = {https://eprint.iacr.org/2015/005}
}