Oblivious RAM simulation with efficient worst-case access overhead

Abstract

Oblivious RAM simulation is a method for achieving confidentiality and privacy in cloud computing environments. It involves obscuring the access patterns to a remote storage so that others, including even the manager of that storage, cannot infer information about its contents. Existing solutions typically yield small amortized overheads for achieving this goal, but also yield huge variations in access times, depending on when they occur. In this paper, we show how to deamortize oblivious RAM simulations, so that each access takes a worst-case bounded amount of time.