Towards a theory of software protection and simulation by oblivious RAMs

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this paper, we make the first steps towards a theoretic treatment of software protection: First, we distill and formulate the key problem of learning about a program from its execution. Second, assuming the existence of one-way permutations, we present an efficient way of executing programs such that it is infeasible to learn anything about the program by monitoring its executions.

How can one efficiently execute programs without allowing an adversary, monitoring the execution, to learn anything about the program? Traditional cryptographic techniques can be applied to keep the contents of the memory unknown throughout the execution, but are not applicable to the problem of hiding the access pattern. The problem of hiding the access pattern efficiently corresponds to efficient simulation of Random Access Machines (RAM) on an oblivious RAM. We define an oblivious RAM to be a (probabilistic) RAM for which (the distribution of) the memory access pattern is independent of the input. We present an (on-line) simulation of t steps of an arbitrary RAM with m memory cells, by less than t·m^ε steps of an oblivious RAM with 2m memory cells, where ε>0 is an arbitrary constant.