Date Added: Dec 2012
As cloud computing gains momentum, an increasing amount of data is outsourced to cloud storage, and data privacy has become an important concern for many businesses and individuals alike. The authors take an important step forward in making Oblivious RAM (O-RAM) practical. On the theoretic front, they propose a fundamentally novel technique for constructing Oblivious RAMs: specifically, they partition a bigger O-RAM into smaller O-RAMs, and employ a background eviction technique to obliviously evict blocks from the client-side cache into a randomly assigned server-side partition. This novel technique is the key to achieving the gains in practical performance.