Oblivious RAMs without Cryptographic Assumptions 1

Abstract. We show that oblivious on-line simulation with only polylogarithmic increase in the time and space requirements is possible on a probabilistic (coin flipping) RAM without using any cryptographic assumptions. The simulation will fail with a negligible probability. If n memory locations are used, then the probability of failure is at most n − logn. Pippenger and Fischer has shown in 1979, see [11], that a Turing machine with one-dimensional tapes, performing a computation of length n can be simulated on-line by an oblivious Turing machine with two dimensional tapes, in time O(n log n), where a Turing machine is oblivious if the movements of it heads as a function of time are independent of its input. For RAMs the notion of obliviousness was defined by Goldreich in 1987 in [6], and he proved a simulation theorem about it. A RAM is oblivious if the distribution of its memory access pattern, which memory cells are accessed at which time, is independent of the program running on the RAM, provided that the time used by the program is fixed. That is, an adversary watching the memory access will not know anything about the program running on the machine apart from its total time. Ostrovsky, improving Goldreich’s theorem, has shown in 1990, see [8], [9], [7], that a RAM using n memory cells can a be simulated by an oblivious RAM with a random oracle (where th