Paper 2014/431

A Low-Latency, Low-Area Hardware Oblivious RAM Controller

Christopher W. Fletcher, Ling Ren, Albert Kwon, Marten van Dijk, Emil Stefanov, Dimitrios Serpanos, and Srinivas Devadas

Abstract

We build and evaluate Tiny ORAM, an Oblivious RAM prototype on FPGA. Oblivious RAM is a cryptographic primitive that completely obfuscates an application's data, access pattern and read/write behavior to/from external memory (such as DRAM or disk). Tiny ORAM makes two main contributions. First, by removing an algorithmic bottleneck in prior work, Tiny ORAM is the first hardware ORAM design to support arbitrary block sizes (e.g. 64 Bytes to 4096 Bytes). With a 64-Byte block size, Tiny ORAM can finish an access in 1.4us, over 40x faster than the prior-art implementation. Second, through novel algorithmic and engineering-level optimizations, Tiny ORAM reduces the number of symmetric encryption operations by ~3x compared to a prior work. Tiny ORAM is also the first design to implement and report real numbers for the cost of symmetric encryption in hardware ORAM constructions. Putting it together, Tiny ORAM requires 18381 (5%) LUTs and 146 (13%) Block RAM on a Xilinx XC7VX485T FPGA, including the cost of encryption.

Note: Changelog: - More thorough explanation of stash scan mechanism as it is built in hardware - New integrity verification scheme that is simpler and more efficient than original - Proof sketches for Unified ORAM and new integrity scheme

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. FCCM
DOI
10.1109/FCCM.2015.58
Keywords
oblivous ramPath ORAMsecure processorslocalityintegrity verification
Contact author(s)
renling @ mit edu
History
2015-12-11: last of 6 revisions
2014-06-12: received
See all versions
Short URL
https://ia.cr/2014/431
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/431,
      author = {Christopher W.  Fletcher and Ling Ren and Albert Kwon and Marten van Dijk and Emil Stefanov and Dimitrios Serpanos and Srinivas Devadas},
      title = {A Low-Latency, Low-Area Hardware Oblivious RAM Controller},
      howpublished = {Cryptology ePrint Archive, Paper 2014/431},
      year = {2014},
      doi = {10.1109/FCCM.2015.58},
      note = {\url{https://eprint.iacr.org/2014/431}},
      url = {https://eprint.iacr.org/2014/431}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.