Emil Stefanov

Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. This paper proposes Ring ORAM, the most bandwidth-efficient ORAM scheme for the small client storage setting in both theory and practice. Ring ORAM is the first tree-based ORAM whose bandwidth is in-dependent of the ORAM bucket size, a property that unlocks multiple performance improvements. First, Ring ORAM’s overall bandwidth is 2.3 × to 4 × better than Path ORAM, the prior-art scheme for small client storage. Second, if memory can perform simple un-trusted computation, Ring ORAM achieves constant on-line bandwidth ( ∼ 60 × improvement over Path ORAM for practical parameters). As a case study, we show Ring ORAM speeds up program completion time in a secure processor by 1.5 × relative to Path ORAM. On the the-ory side, Ring ORAM features a tighter and significantly simpler analysis than Path ORAM.