Rafail Ostrovsky - Publications

Software Protection and Simulation on Oblivious RAMs.

Rafail Ostrovsky

Abstract: 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 provide theoretical treatment of software protection. We reduce the problem of software protection to the problem of efficient simulation on oblivious RAM.

A machine is oblivious if the sequence in which it accesses memory locations is equivalent 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, it is independent of the actual input.) What is the slowdown in the running time of any machine, if it is required to be oblivious? In 1979 Pippenger and Fischer showed how a two-tape oblivious Turing Machine can simulate, on-line, a one-tape Turing Machine, with a logarithmic slowdown in the running time. We show an analogue result for the random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of an arbitrary RAM input by a probabilistic oblivious RAM with a poly-logarithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound. Our proof yields a technique of efficiently hiding (through randomization) the access pattern into any composite data-structure which has many practical applications.

comment: M.I.T. Ph.D. Thesis, 1992. Preliminary version appeared in Proceedings of 22^nd annual ACM Symposium on Theory of Computing (STOC-90) pp. 514-523. Journal version (which combines my thesis with Oded Goldreich previous paper on the same subject) appeared in the Journal of the JACM, Vol. 43, No. 3, May 1996, pp.431-473. written jointly with Oded Goldreich.

Fetch PostScript file of the thesis      or fetch PDF file of the thesis

You can also get journal version of my thesis (with a somewhat different, shorter proof of bucket reshuffles of section 5.5) written jointly with Oded Goldreich, that appeared in JACM in 1996:
Fetch PostScript file of the JACM paper     Fetch PDF file of the JACM paper