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.