  We study the problem of providing privacy-preserving access to an outsourced
honest-but-curious data repository for a group of trusted users. We show that
such privacy-preserving data access is possible using a combination of
probabilistic encryption, which directly hides data values, and stateless
oblivious RAM simulation, which hides the pattern of data accesses. We give
simulations that have only an $O(\log n)$ amortized time overhead for
simulating a RAM algorithm, $\cal A$, that has a memory of size $n$, using a
scheme that is data-oblivious with very high probability assuming the
simulation has access to a private workspace of size $O(n^\nu)$, for any given
fixed constant $\nu>0$. This simulation makes use of pseudorandom hash
functions and is based on a novel hierarchy of cuckoo hash tables that all
share a common stash. We also provide results from an experimental simulation
of this scheme, showing its practicality. In addition, in a result that may be
of some theoretical interest, we also show that one can eliminate the
dependence on pseudorandom hash functions in our simulation while having the
overhead rise to be $O(\log^2 n)$.
