Path ORAM: An extremely simple oblivious RAM protocol

Emil Stefanov, Marten Van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, Srinivas Devadas

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

Abstract

We present Path ORAM, an extremely simple Oblivious RAM protocol with a small amount of client storage. Partly due to its simplicity, Path ORAM is the most practical ORAM scheme for small client storage known to date. We formally prove that Path ORAM requires O(log2 N / log χ) bandwidth overhead for block size B = χ log N. For block sizes bigger than ω(log2 N), Path ORAM is asymptotically better than the best known ORAM scheme with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

Original languageEnglish (US)
Title of host publicationCCS 2013 - Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security
Pages299-310
Number of pages12
DOIs
StatePublished - Dec 9 2013
Externally publishedYes
Event2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013 - Berlin, Germany
Duration: Nov 4 2013Nov 8 2013

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Other

Other2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013
CountryGermany
CityBerlin
Period11/4/1311/8/13

Keywords

  • access pattern
  • oblivious ram
  • oram
  • path oram

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Path ORAM: An extremely simple oblivious RAM protocol'. Together they form a unique fingerprint.

Cite this