__
TR11-082 | 20th May 2011 03:45
__

#### Secure Computation with Information Leaking to an Adversary

**Abstract:**
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.