Two related works on Oblivious RAMs:
(1) Oblivious RAMs without Cryptographic Assumptions
by Ajtai.
(2) Perfectly Secure Oblivious RAM Without Random Oracles
by Damgard, Meldgaard, and Nielsen.
Oded's comments
The issue is hiding the virtual access pattern
in a setting where a bounded-memory player stores
data items on a remote memory. Every desired item
is fetched by a visible sequence of real accesses,
and we wish this visible sequence to yield no information on the
request sequence (i.e., the actual items we are interested in).
A solution involving a polylogarithmic (amortized) overhead
has been known for two decades
(see Goldreich and Ostrovsky),
but this solution required the player to have secret access
to a random function
(which can be implemented using a pseudorandom function).
The current works waive this requirement;
instead of using a random function for storing a large
number of coin tosses, the current work use the memory
itself to store these values while providing an oblivious
way of accessing the required random values.
The original abstracts
See Ajtai's
Oblivious RAMs without Cryptographic Assumptions
and Damgard et al.'s
Perfectly Secure Oblivious RAM Without Random Oracles
Back to
list of Oded's choices.