Oblivious RAM Done Right (2): [GO96]


  1. Software Protection and Simulation on Oblivious RAMs” by Rafail Ostrovsky

1. Introduction:

This paper starts from the problem of software protection, here we mean “protection against illegitimate duplication”, i.e. ensuring there is no efficient method for creating executable copies of the software. Purely software-based solution doesn’t exist, so hardware must involve. Our task is to minimize the participation of hardware, so that the solution is less expensive.

An existing solution is “software-hardware-package (SH-package)“, that is, selling a physically shielded CPU together with an encrypted program. An instruction cycle of such CPU will be fetching -> decrypting -> executing an instruction. Every ATM machine has such a protected chip.

However, above solution is not good enough, since it doesn’t hide the “access pattern“, i.e. the addresses of the memory cells accessed during the execution are not kept secret. The lack of such property may create trouble, e.g. an adversary could learn the loop structure of the program, which is important in certain scenario. If we come up with a solution that hides the access pattern, we consider it as secure. Informally, “hiding access pattern” means no PPT adversary can distinguish these two cases:

Case 1: The adversary is experimenting with the real CPU that runs the encrypted program.

Case 2: The adversary is experimenting with a fake CPU that runs dummy program, such as “while True do skip”. After the same number of steps as in case 1, the CPU writes exactly the same outputs as in case 1 into memory.

To protect software to such level of security, the cost is “speed”, called software protection overhead. Informally, software protection overhead means the number of steps the protected program makes for each each step of the program. Our task is to minimize this overhead.

2. Model and Definitions:

A machine is oblivious if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time.

3. Reducing Software Protection to Oblivious Simulation of RAMs:

4. Square Root Solution

5. Hierarchical Solution

6. Lower Bound

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s