Constants count: Practical improvements to oblivious RAM

Ling Ren, Christopher Fletcher, Albert Kwon, Emil Stefanov, Elaine Shi, Marten Van Dijk, Srinivas Devadas

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


Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. This paper proposes Ring ORAM, the most bandwidth-efficient ORAM scheme for the small client storage setting in both theory and practice. Ring ORAM is the first tree-based ORAM whose bandwidth is independent of the ORAM bucket size, a property that unlocks multiple performance improvements. First, Ring ORAM’s overall bandwidth is 2.3× to 4× better than Path ORAM, the prior-art scheme for small client storage. Second, if memory can perform simple untrusted computation, Ring ORAM achieves constant online bandwidth (∼ 60× improvement over Path ORAM for practical parameters). As a case study, we show Ring ORAM speeds up program completion time in a secure processor by 1.5× relative to Path ORAM. On the theory side, Ring ORAM features a tighter and significantly simpler analysis than Path ORAM.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th USENIX Security Symposium
PublisherUSENIX Association
Number of pages16
ISBN (Electronic)9781931971232
StatePublished - 2015
Externally publishedYes
Event24th USENIX Security Symposium - Washington, United States
Duration: Aug 12 2015Aug 14 2015

Publication series

NameProceedings of the 24th USENIX Security Symposium


Conference24th USENIX Security Symposium
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Constants count: Practical improvements to oblivious RAM'. Together they form a unique fingerprint.

Cite this