AbstractSoftware 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. 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, the movement is independent of the actual input.) What is the slowdown in the running time of a 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 analogous 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 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.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in:
- Oded Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 182-194, New York City, 25-27 May 1987.
- Rafail Ostrovsky. Efficient computation on oblivious RAMs. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 514-523, Baltimore, Maryland, 14-16 May 1990.
Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]; E.3 [Data Encryption]; F.1.1 [Computation by Abstract Devices]: Models of Computation -- bounded-action devices
General Terms: Security, Theory
Additional Key Words and Phrases: Pseudorandom functions, simulation of random access machines, software protection
Selected papers that cite this one
- Eyal Kushilevitz and Rafail Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval (extended abstract). In 38th Annual Symposium on Foundations of Computer Science, pages 364-373, Miami Beach, Florida, 20-22 October 1997. IEEE.
- Rafail Ostrovsky and Victor Shoup. Private information storage (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 294-303, El Paso, Texas, 4-6 May 1997.
Selected references
- M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 1-9, Boston, Massachusetts, 25-27 April 1983.
- Miklós Ajtai, János Komlós, and Endre Szemerédi. Halvers and expanders. In 33rd Annual Symposium on Foundations of Computer Science, pages 686-692, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Werner Alexi, Benny Chor, Oded Goldreich, and Claus P. Schnorr. RSA/Rabin bits are 1/2 + 1/poly(log N) secure. In 25th Annual Symposium on Foundations of Computer Science, pages 449-457, Singer Island, Florida, 24-26 October 1984. IEEE.
- Manuel Blum, Will Evans, Peter Gemmell, Sampath Kannan, and Moni Naor. Checking the correctness of memories. In 32nd Annual Symposium on Foundations of Computer Science, pages 90-99, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Manuel Blum and Sampath Kannan. Designing programs that check their work. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 86-97, Seattle, Washington, 15-17 May 1989.
- Oded Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 182-194, New York City, 25-27 May 1987.
- Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, October 1986.
- Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 291-304, Providence, Rhode Island, 6-8 May 1985.
- Johan Håstad. Pseudo-random generators under uniform assumptions. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 395-404, Baltimore, Maryland, 14-16 May 1990.
- Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 12-24, Seattle, Washington, 15-17 May 1989.
- Michael Luby and Charles Rackoff. Pseudo-random permutation generators and cryptographic composition. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 356-363, Berkeley, California, 28-30 May 1986.
- Rafail Ostrovsky. Efficient computation on oblivious RAMs. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 514-523, Baltimore, Maryland, 14-16 May 1990.
- Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. Journal of the ACM, 26(2):361-381, April 1979.
- Charles Rackoff and Daniel R. Simon. Cryptographic defense against traffic analysis. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 672-681, San Diego, California, 16-18 May 1993.
- Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, Chicago, Illinois, 3-5 November 1982. IEEE.