Onion ORAM: A constant bandwidth blowup oblivious RAM

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 Damgå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 blowup ORAM under standard assumptions (even for the semi-honest setting).

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 3th International Conference, TCC 2016-A, Proceedings
EditorsTal Malkin, Eyal Kushilevitz
PublisherSpringer-Verlag Berlin Heidelberg
Pages145-174
Number of pages30
ISBN (Print)9783662490983
DOIs
StatePublished - Jan 1 2016
Externally publishedYes
Event13th International Conference on Theory of Cryptography, TCC 2016 - Tel Aviv, Israel
Duration: Jan 10 2016Jan 13 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9563
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Conference on Theory of Cryptography, TCC 2016
CountryIsrael
CityTel Aviv
Period1/10/161/13/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Onion ORAM: A constant bandwidth blowup oblivious RAM'. Together they form a unique fingerprint.

  • Cite this

    Devadas, S., van Dijk, M., Fletcher, C. W., Ren, L., Shi, E., & Wichs, D. (2016). Onion ORAM: A constant bandwidth blowup oblivious RAM. In T. Malkin, & E. Kushilevitz (Eds.), Theory of Cryptography - 3th International Conference, TCC 2016-A, Proceedings (pp. 145-174). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9563). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-662-49099-0_6