Towards a theory of software protection and simulation by oblivious RAMs

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 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&egr; steps of an oblivious RAM with 2m memory cells, where &egr;>0 is an arbitrary constant.

REFERENCES

• AHU: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• AKS: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• ACGS: Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
• Bat: Batcher, K., "Sorting Networks and the:it Applications", AFIPS Spring Joint Cornouter Conference, 32, 1968, pp. 307-314.
• Be: Best, R., "Microprocessor for Executing Encrypted Programs", US Patent 4,168,396. Issued September 1979.
• BG: Manuel Blum , Shafi Goldwasser, An efficient probabilistic public key encryption scheme which hides all partial information, Proceedings of CRYPTO 84 on Advances in cryptology, p.289-302, August 1985, Santa Barbara, California, United States
• BM: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• GGM: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• GM: Goldwasser S., and S. Micali, "Probabilistic Encryption", Jour. of Computer and System Science, Vol. 28, No. 2, 1984, pp. 270-299.
• K: S. Kent, PROTECTING EXTERNALLY SUPPLIED SOFTWARE IN SMALL COMPUTERS, Massachusetts Institute of Technology, Cambridge, MA, 1981
• L: L A Levin, One-way functions and pseudorandom generators, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.363-365, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22185]
• LR: M Luby , C Rackoff, Pseudo-random permutation generators and cryptographic composition, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.356-363, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12167]
• PF: Nicholas Pippenger , Michael J. Fischer, Relations Among Complexity Measures, Journal of the ACM (JACM), v.26 n.2, p.361-381, April 1979 [doi>10.1145/322123.322138]
• Y: Yao, A.C., "Theory and Applications of Trapdoor Functions", Proc. of the 23rd IEEE Syrup. on Foundation of Computer Science, 1982, pp. 80-91.

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.4 OPERATING SYSTEMS

  E. Data
  E.3 DATA ENCRYPTION

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  K. Computing Milieux
  K.5 LEGAL ASPECTS OF COMPUTING

General Terms:
Management, Security, Theory, Verification