SOFTWARE PROTECTION AND SIMULATION ON OBLIVIOUS RAMS

Software protection is one of the most important issues concerning com puter practice. There exist many heuristics and ad-hoc methods for pro tection, but the problem as a whole has not received the theoretical t reatment it deserves. In this paper, we provide theoretical treatment of software protection. We reduce the problem of software protection t o the problem of efficient simulation on oblivious RAM. A machine is o blivious if the sequence in which it accesses memory locations is equi valent for any two inputs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, the movement is i ndependent of the actual input.) What is the slowdown in the running t ime of a machine, if it is required to be oblivious? In 1979, Pippenge r and Fischer showed how a two-tape oblivious Turing Machine can simul ate, on-line, a one-tape Turing Machine, with a logarithmic slowdown i n the running time. We show an analogous result for the random-access machine (RAM) model of computation. In particular, we show how to do a n on-line simulation of an arbitrary RAM by a probabilistic oblivious RAM with a polylogarithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound.