Abstract
An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern: i.e, for every input the memory locations accessed are similarly distributed. Since their inception, ORAMs have become an invaluable tool in designing cryptographic systems, where observable memory access patterns crucially must not leak sensitive information. We present a survey of cryptographic ORAM research, from the original constructions to the most recent discoveries, and the mysteries that lie ahead.