Freecursive ORAM: [Nearly] free recursion and integrity verification for position-based oblivious RAM

Christopher W. Fletcher, Ling Ren, Albert Kwon, Marten Van Dijk, Srinivas Devadas

Research output: Contribution to journalArticlepeer-review


Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. Recently, ORAM has been architected into secure processors. A big challenge for hardware ORAM schemes is how to efficiently manage the Position Map (PosMap), a central component in modern ORAM algorithms. Implemented naïvely, the PosMap causes ORAM to be fundamentally unscalable in terms of on-chip area. On the other hand, a technique called Recursive ORAM fixes the area problem yet significantly increases ORAM's performance overhead. To address this challenge, we propose three new mechanisms. We propose a new ORAM structure called the PosMap Lookaside Buffer (PLB) and PosMap compression techniques to reduce the performance overhead from Recursive ORAM empirically (the latter also improves the construction asymptotically). Through simulation, we show that these techniques reduce the memory bandwidth overhead needed to support recursion by 95%, reduce overall ORAM bandwidth by 37% and improve overall SPEC benchmark performance by 1.27x. We then show how our PosMap compression techniques further facilitate an extremely efficient integrity verification scheme for ORAM which we call PosMap MAC (PMMAC). For a practical parameterization, PMMAC reduces the amount of hashing needed for integrity checking by ≥ 68 x relative to prior schemes and introduces only 7% performance overhead. We prototype our mechanisms in hardware and report area and clock frequency for a complete ORAM design postsynthesis and post-layout using an ASIC flow in a 32 nm commercial process. With 2 DRAM channels, the design post-layout runs at 1 GHz and has a total area of .47 mm2. Depending on PLB-specific parameters, the PLB accounts for 10% to 26% area. PMMAC costs 12% of total design area. Our work is the first to prototype Recursive ORAM or ORAM with any integrity scheme in hardware.

Original languageEnglish (US)
Pages (from-to)103-116
Number of pages14
JournalACM SIGPLAN Notices
Issue number4
StatePublished - Apr 2015
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Freecursive ORAM: [Nearly] free recursion and integrity verification for position-based oblivious RAM'. Together they form a unique fingerprint.

Cite this