Secure computation with information leaking to an adversary
Miklós Ajtai · 2011
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 ε m whose time is compromised, where ε>0 is a small constant. We show that if m= c⌊ log n ⌋, 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.