Oded Goldreich
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 thhe 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 polylogaithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound.
- AHO, A. V., HOPCROFr, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Pa. Google Scholar
- AJTAI, M., KOMLOS, J., AND SZEMEREDI, E. 1983. An O(n log n) sorting network. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New York, pp. 1-9. Google Scholar
- AJTAI, M., KOMLOS, J., AND SZEMEREDt, E. 1992. Halvers and Expanders. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science. (Pittsburgh, Pa., Oct. 24-27). IEEE, New York, pp. 686-692.Google Scholar
- BATCHER, K. 1968. Sorting networks and their applications. In AFIPS Spring Joint Computer Conference, Vol. 32 AFIPS Press, Richmond, Va., pp. 307-314.Google Scholar
- BEST, R. 1979. Microprocessor for executing encrypted programs. US Patent 4, 168396.Google Scholar
- BLUM, M. Designing programs to check their work. manuscript.Google Scholar
- Bt.UM, M., AND KANNAN, S. 1989. Designing programs that check their work. In Proceedings of the 21st Annual ACM Symposium on Theoo' of Computing (Seattle, Wash., May 15-17). ACM, New York, pp. 86-92. Google Scholar
- BLUM, M., EVANS, W., GEMMELL, P., KANNAN, S., AND NAOR, M. 1991. Checking the correctness of memories. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (San Juan, P.R., Oct. 1-4). IEEE, New York, pp. 90-97. Google Scholar
- BLUM, M., AND MICALI, S. 1984. How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13, 850-864. Google Scholar
- CARTER, J. L., AND WEGMAN, M.N. 1979. Universal classes of hash functions. Jr. Comput. Syst. ScL 18, 143-154.Google Scholar
- GOLDREICH, O. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 182-194. Google Scholar
- GOLDREtCH, O., AND OSTROVSKY, R. Comprehensive software protection system U.S. Patent, Serial No. 07/395.882.Google Scholar
- GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. 1986. How to construct random functions. J. ACM 33, 4 (Oct.), 792-807. Google Scholar
- GOLDWASSER, S., AND MICALI, S. 1984. Probabilistic encryption Z Comput. Syst. Sci. 28, 2, 270-299.Google Scholar
- GOLDWASSER, S., M1CALI, S., AND RACKOFF, C. 1985. The knowledge complexity of interactive proof-systems. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, pp. 291-304. Google Scholar
- HASTAD, J. 1990. Pseudo-random generators under uniform assumptions. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, Md., May 12-14). ACM, New York, pp. 395-404. Google Scholar
- IMPAGLIAZZO, R., LEVlN, L., AND LUaY, M. 1989. Pseudo-random generation from one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (Seattle, Wash., May 17-19). ACM, New York, pp. 12-24. Google Scholar
- KENT, S.T., 1980. Protecting externally supplied software in small computers. Ph.D. dissertation. MIT/LCS/TR-255. MIT, Cambridge, Mass. Google Scholar
- LUBY, M., AND RACKOFF, C. 1986. Pseudo-random permutation generators and cryptographic composition. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York, pp. 356-363. Google Scholar
- OSTROVSKY, R. 1990. Efficient computation on oblivious RAMs. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, Md., May 12-14). ACM, New York, pp. 514-523. Google Scholar
- PIPPENGER, N., AND FISCHER, M.J. 1979. Relations among complexity measures. J. ACM, 26, 2 (Apr.), 361-381. Google Scholar
- RACKOFF, C., AND SIMON, M. 1993. Cryptographic defense against traffic analysis, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 672-681. Google Scholar
- YAO. A. C. 1982. Theory and Applications of Trapdoor Functions. In Proceedings of the 23rd Annual 1EEE Symposium on Foundations of Computer Science (Chicago, I11., Nov. 3-5). IEEE, New York, pp. 80-01.Google Scholar
Index Terms
- Software protection and simulation on oblivious RAMs
Recommendations
Towards a theory of software protection and simulation by oblivious RAMs
STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingSoftware 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 ...
Oblivious RAMs without cryptogrpahic assumptions
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingithmic increase in the time and space requirements is possible on a probabilistic (coin flipping) RAM without using any cryptographic assumptions. The simulation will fail with a negligible probability. If n memory locations are used, then the ...
Comments