Paper 2014/431

Tiny ORAM: A Low-Latency, Low-Area Hardware ORAM Controller with Integrity Verification

Christopher W. Fletcher and Ling Ren and Albert Kwon and Marten Van Dijk and Emil Stefanov and Srinivas Devadas

Abstract

We propose and build \emph{Tiny ORAM}, an ORAM construction that improves the state of the art Path ORAM in several dimensions. First, through a construction that we call \emph{RAW Path ORAM}, we reduce the number of symmetric encryption operations by $4\times$ compared with Path ORAM. Raw Path ORAM also dramatically simplifies the theoretical analysis on the client's storage requirement (stash size). Second, we propose an integrity verification scheme that is asymptotically more efficient than prior work for position-based ORAMs. Third, through a construction that we call \emph{Unified Path ORAM}, we reduce the empirical overhead of the recursive ORAM construction. We demonstrate and evaluate a working prototype on a stock FPGA board. Of independent interest, Tiny ORAM is the first hardware ORAM design to support small client storage and arbitrary block sizes (e.g., 64~Bytes to 4096~Bytes). Block size flexibility allows Tiny ORAM to greatly reduce the worst-case access latency for ORAM running programs with erratic data locality. Tiny ORAM is also the first design to implement and report real numbers for the cost of symmetric encryption in hardware ORAM constructions. Tiny ORAM requires $3\%/14\%$ of the FPGA logic/memory (including the cost of encryption) and can complete an ORAM access for a 64 Byte block in $1.25-4.75\mu s$.

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