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^{-\log n}$. Pippenger and Fischer has shown in 1979, 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, 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, that a RAM using $n $ memory cells can a be simulated by an

oblivious RAM with a random oracle (where the random bits can be

accessed repeatedly) so that the increase of the space and time

requirement is only about a factor of $\polyln$ (Goldreich's factor was

about $\exp[(\log n)^{1/2}]$). In both cases the oblivious RAM with a

random oracle, can be replaced, by an oblivious probabilistic

(coin-flipping) RAM, provided that we accept some unproven cryptographic

assumptions, e.g., the existence of a one-way function. In this paper

we show that simulation with an oblivious, coin-flipping RAM, with only

a factor of $\polyln$ increase in time and space requirements, is

possible, even without any cryptographic assumptions.

In the theorems of Goldreich and Ostrovsky it is assumed that the

oblivious RAM has a protected CPU, that is, a constant number of

registers, so that, the accesses to these registers are not included

into the memory access pattern, and so they are not available to the

adversary. We show that the protected CPU is not needed for the

present, or former, results, since a protected $CPU$ can be simulated on

a RAM, so that the time requirement is increasing only by a constant

factor, and the space requirement by an additive constant. In fact we

may even let the adversary know which instruction is executed at each

time, and the results still remain the same. (Note however, that the

theorems of Goldreich and Ostrovsky hold even for an adversary who can

see the contents of all memory cells outside the protected CPU. There is

no equivalent statement in the present result.)

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^{-\log n}$. Pippenger and Fischer has shown in 1979, 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, 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, that a RAM using $n $ memory cells can a be simulated by an

oblivious RAM with a random oracle (where the random bits can be

accessed repeatedly) so that the increase of the space and time

requirement is only about a factor of $\polyln$ (Goldreich's factor was

about $\exp[(\log n)^{1/2}]$). In both cases the oblivious RAM with a

random oracle, can be replaced, by an oblivious probabilistic

(coin-flipping) RAM, provided that we accept some unproven cryptographic

assumptions, e.g., the existence of a one-way function. In this paper

we show that simulation with an oblivious, coin-flipping RAM, with only

a factor of $\polyln$ increase in time and space requirements, is

possible, even without any cryptographic assumptions.

In the theorems of Goldreich and Ostrovsky it is assumed that the

oblivious RAM has a protected CPU, that is, a constant number of

registers, so that, the accesses to these registers are not included

into the memory access pattern, and so they are not available to the

adversary. We show that the protected CPU is not needed for the

present, or former, results, since a protected $CPU$ can be simulated on

a RAM, so that the time requirement is increasing only by a constant

factor, and the space requirement by an additive constant. In fact we

may even let the adversary know which instruction is executed at each

time, and the results still remain the same. (Note however, that the

theorems of Goldreich and Ostrovsky hold even for an adversary who can

see the contents of all memory cells outside the protected CPU. There is

no equivalent statement in the present result.)