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.4\mu s$, over $40\times$ faster than prior work. Second, through novel algorithmic and engineering-level optimizations, Tiny ORAM reduces the number of symmetric encryption operations by $\sim3\times$ compared to 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 $5\%/13\%$ of the FPGA logic/memory, including the cost of encryption.
Category / Keywords: cryptographic protocols / oblivous ram, Path ORAM, secure processors, locality, integrity verification Date: received 4 Jun 2014, last revised 24 Jan 2015 Contact author: renling at mit edu Available format(s): PDF | BibTeX Citation 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
Version: 20150124:225135 (All versions of this report) Short URL: ia.cr/2014/431 Discussion forum: Show discussion | Start new discussion