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.)