Software protection and simulation on 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 problem as a whole has not received theoretical treatment it deserves. In this paper, we provide software protection. We reduce to efficient simulation on oblivious RAM.A machine if thhe sequence in which accesses memory locations equivalent any two inputs with same running time. For example, an Turing Machine movement heads tapes identical each computation. (Thus, independent actual input.) What slowdown time machine, required be oblivious? 1979, Pippenger Fischer showed how two-tape can simulate, on-line, one-tape Machine, logarithmic show analogous result random-access (RAM) model particular, do on-line arbitrary RAM by probabilistic polylogaithmic On other hand, that lower bound.