Path ORAM: An extremely simple oblivious RAM protocol

Emil Stefanov; Marten V.A.N. Dijk; S. H.I. Elaine; T. H.Hubert Chan; Christopher Wardlaw Fletcher; Ling Ren; Xiangyao Yu; Srinivas Devadas

doi:10.1145/3177872

Path ORAM: An extremely simple oblivious RAM protocol

Emil Stefanov, Marten V.A.N. Dijk, S. H.I. Elaine, T. H.Hubert Chan, Christopher Wardlaw Fletcher, Ling Ren, Xiangyao Yu, Srinivas Devadas

Research output: Contribution to journal › Article › peer-review

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 known to date with small client storage. We formally prove that Path ORAM has a O(log N) bandwidth cost for blocks of size B = Ω(log² N) bits. For such block sizes, Path ORAM is asymptotically better than the best-known ORAM schemes with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

Original language	English (US)
Article number	18
Journal	Journal of the ACM
Volume	65
Issue number	4
DOIs	https://doi.org/10.1145/3177872
State	Published - Apr 2018

Keywords

Access pattern
ORAM
Oblivious RAM
Path ORAM

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Online availability

10.1145/3177872

Library availability

Discover UIUC Full Text

Cite this

@article{1b34a5c88fe34a7897958c9a3335f2c6,

title = "Path ORAM: An extremely simple oblivious RAM protocol",

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 known to date with small client storage. We formally prove that Path ORAM has a O(log N) bandwidth cost for blocks of size B = Ω(log2 N) bits. For such block sizes, Path ORAM is asymptotically better than the best-known ORAM schemes with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.",

keywords = "Access pattern, ORAM, Oblivious RAM, Path ORAM",

author = "Emil Stefanov and Dijk, {Marten V.A.N.} and Elaine, {S. H.I.} and Chan, {T. H.Hubert} and Fletcher, {Christopher Wardlaw} and Ling Ren and Xiangyao Yu and Srinivas Devadas",

note = "Publisher Copyright: {\textcopyright} 2018 ACM 0004-5411/2018/04-ART18 $15.00",

year = "2018",

month = apr,

doi = "10.1145/3177872",

language = "English (US)",

volume = "65",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery",

number = "4",

}

TY - JOUR

T1 - Path ORAM

T2 - An extremely simple oblivious RAM protocol

AU - Stefanov, Emil

AU - Dijk, Marten V.A.N.

AU - Elaine, S. H.I.

AU - Chan, T. H.Hubert

AU - Fletcher, Christopher Wardlaw

AU - Ren, Ling

AU - Yu, Xiangyao

AU - Devadas, Srinivas

PY - 2018/4

Y1 - 2018/4

N2 - 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 known to date with small client storage. We formally prove that Path ORAM has a O(log N) bandwidth cost for blocks of size B = Ω(log2 N) bits. For such block sizes, Path ORAM is asymptotically better than the best-known ORAM schemes with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

AB - 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 known to date with small client storage. We formally prove that Path ORAM has a O(log N) bandwidth cost for blocks of size B = Ω(log2 N) bits. For such block sizes, Path ORAM is asymptotically better than the best-known ORAM schemes with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

KW - Access pattern

KW - ORAM

KW - Oblivious RAM

KW - Path ORAM

UR - http://www.scopus.com/inward/record.url?scp=85052364322&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052364322&partnerID=8YFLogxK

U2 - 10.1145/3177872

DO - 10.1145/3177872

M3 - Article

AN - SCOPUS:85052364322

SN - 0004-5411

VL - 65

JO - Journal of the ACM

JF - Journal of the ACM

IS - 4

M1 - 18

ER -

Path ORAM: An extremely simple oblivious RAM protocol

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this