PrORAM: Dynamic prefetcher for oblivious RAM

Xiangyao Yu, Syed Kamran Haider, Ling Ren, Christopher Fletcher, Albert Kwon, Marten Van Dijk, Srinivas Devadas

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


Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system. With ORAM, a curious adversary cannot tell what address the user is accessing when observing the bits moving between the user and the storage system. All existing ORAM schemes achieve obliviousness by adding redundancy to the storage system, i.e., each access is turned into multiple random accesses. Such redundancy incurs a large performance overhead. Although traditional data prefetching techniques successfully hide memory latency in DRAM based systems, it turns out that they do not work well for ORAM because ORAM does not have enough memory bandwidth available for issuing prefetch requests. In this paper, we exploit ORAM locality by taking advantage of the ORAM internal structures. While it might seem apparent that obliviousness and locality are two contradictory concepts, we challenge this intuition by exploiting data locality in ORAM without sacrificing security. In particular, we propose a dynamic ORAM prefetching technique called PrORAM (Dynamic Prefetcher for ORAM) and comprehensively explore its design space. PrORAM detects data locality in programs at runtime, and exploits the locality without leaking any information on the access pattern. Our simulation results show that with PrORAM, the performance of ORAM can be significantly improved. PrORAM achieves an average performance gain of 20% over the baseline ORAM for memory intensive benchmarks among Splash2 and 5.5% for SPEC06 workloads. The performance gain for YCSB and TPCC in DBMS benchmarks is 23.6% and 5% respectively. On average, PrORAM offers twice the performance gain than that offered by a static super block scheme.

Original languageEnglish (US)
Title of host publicationISCA 2015 - 42nd Annual International Symposium on Computer Architecture, Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages13
ISBN (Electronic)9781450334020
StatePublished - Jun 13 2015
Externally publishedYes
Event42nd Annual International Symposium on Computer Architecture, ISCA 2015 - Portland, United States
Duration: Jun 13 2015Jun 17 2015

Publication series

NameProceedings - International Symposium on Computer Architecture
ISSN (Print)1063-6897


Other42nd Annual International Symposium on Computer Architecture, ISCA 2015
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'PrORAM: Dynamic prefetcher for oblivious RAM'. Together they form a unique fingerprint.

Cite this