Assume that Alice is running a program $P$ on a RAM, and an adversary
Bob would like to get some information about the input or output of the
program. At each time, during the execution of $P$, Bob is able to see
the addresses of the memory cells involved in the instruction which is
executed and the name of the instruction. In addition to this, at
certain times, Bob can even see the contents of all of the memory cells
involved in the instruction. We will call a time when this happens a
compromised time. Bob can choose the compromised times in an adaptive
way, that is, immediately before the instruction at time $t$ is
executed, Bob, using all of the information at his disposal, can decide
whether time $t$ will be compromised or not. The only restriction on
his choice is, that among $m$ consecutive instructions there can be at
most $\epsilon m$ whose time is compromised, where $\epsilon>0$ is a
small constant. We show that if $m= c\lfloor \log n \rfloor $, where
$c>0$ is a large constant, then for each program $P$, using $n$ memory
cells and time $T=O({ poly}(n))$, Alice can construct a functionally
equivalent program $P'$, such that the probability that Bob gets any
nontrivial information about the input of $P$ is negligible, and the
time and space requirements of $P'$ grows, compared to $P$, only by a
factor of ${ poly}(\log n)$. We assume that the program $P'$ gets its
input in an encoded form, namely each input bit $b$ is encoded by a
random $0,1$-sequence of length $m$ whose parity is $b$. The output
bits must be encoded by $P'$ in a similar way.

As part of the proof of the result described above we also construct for
all positive integers $m$, and for all boolean circuits $C$ of size $n$
a functionally equivalent circuit $C'$ of size $O(n { poly}(m))$ with the
following properties. Assume that an adversary can observe each bit
going through the wires of the circuit $C'$ independently with a
probability of $\epsilon$, where $\epsilon>0 $ is a small constant, and
each input/output bit of $C$ is encoded by $m$ input/output bits of $C'$
the same way as described above for RAMs. Then, such an adversary,
while observing $C'$, can get any information about the input/output of
the circuit $C$ only with a probability of $ne^{-cm}$, where $c>0$ is a
constant.