A machine is oblivious if the sequence in which it accesses memory locations is equivalent for any two programs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation.(Thus, it is independent of the actual input.) What is the slowdown in the running time of any machine, if it is required to be oblivious?

In 1979 Pippenger and Fischer [PF] showed how a twotape oblivious Turing Machine can simulate, on-line, a onetape Turing Machine, with a logarithmic slowdown in the running time. We show a similar result for the randomaccess machine (RAM) model of computation, solving an open problem posed by Goldreich [G]. In particular, we show how to do an on-line simulation of an arbitrary RAM program by a probabilistic RAM whose memory access pattern is independent of the program which is being executed, and with a poly-logarithmic slowdown in the running time.