Cryptology ePrint Archive: Report 2015/005

Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM

Srinivas Devadas and Marten van Dijk and Christopher W. Fletcher and Ling Ren and 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 ORAM bandwidth lower bound. Our construction does not require fully homomorphic encryption, but employs an additive homomorphic encryption scheme such as the Damg\r{a}rd-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 ORAM under standard assumptions (even for the semi-honest setting).

Category / Keywords: ORAM, Cryptographic Protocols

Date: received 5 Jan 2015, last revised 14 Jul 2015

Contact author: renling at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20150714:222440 (All versions of this report)

Short URL: ia.cr/2015/005

Discussion forum: Show discussion | Start new discussion