NDLI: Towards a theory of software protection and simulation by oblivious RAMs

Please wait, while we are loading the content...

Matrix multiplication via arithmetic progressions

Solving minimum-cost flow problems by successive approximation

A new approach to all pairs shortest paths in planar graphs

An algorithm for linear programming which requires $O(((m+n)n^{2}+(m+n)^{1.5}n)L)$ arithmetic operations

A Linear time algorithm for computing the Voronoi diagram of a convex polygon

Testing for cycles in infinite graphs with periodic structure

Approximation algorithms for shortest path motion planning

The complexity of cutting convex polytypes

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Optimal bounds for decision problems on the CRCW PRAM

Two tapes are better than one for off-line Turing machines

Finite monoids and the fine structure of $NC^{1}$

The strong exponential hierarchy collapses

The Boolean formula value problem is in ALOGTIME

Deterministic simulation in LOGSPACE

Properties that characterize LOGCFL

Some consequences of the existence of pseudorandom generators

Efficiency considerations in using semi-random sources

Imperfect random sources and discrete controlled processes

The power of randomness for communication complexity

Towards a theory of software protection and simulation by oblivious RAMs

On hiding information from an oracle

The complexity of perfect zero-knowledge

Zero knowledge proofs of identity

How to play ANY mental game

Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

Analysis of backoff protocols for multiple access channels

Dynamic parallel complexity of computational circuits

Constructing disjoint paths on expander graphs

Reconfiguring a hypercube in the presence of faults

On the learnability of Boolean formulae

On learning Boolean functions

A model for hierarchical memory

Parallel symmetry-breaking in sparse graphs

A random NC algorithm for depth first search

A new graphy triconnectivity algorithm and its parallelization

Matching is as easy as matrix inversion

Fast parallel algorithms for chordal graphs

Two algorithms for maintaining order in a list

An optimal online algorithm for metrical task systems

Searching a two key table under a single key

The page number of genus g graphs is (g)

Simple algebras are difficult

Permutation groups in NC

Threshold spectra for random graphs

The decision problem for the probabilities of higher-order properties

Size-time complexity of Boolean networks for prefix computations

Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials

Realistic analysis of some randomized algorithms

Recognizing primes in random polynomial time

Towards a theory of software protection and simulation by oblivious RAMs

Content Provider	ACM Digital Library
Author	Goldreich, O.
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ε steps of an oblivious RAM with 2m memory cells, where ε>0 is an arbitrary constant.
Starting Page	182
Ending Page	194
Page Count	13
File Format	PDF
ISBN	0897912217
DOI	10.1145/28395.28416
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-01-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in