Oblivious data structure

In computer science, an oblivious data structure is a data structure that gives no information about the sequence or pattern of the operations that have been applied except for the final result of the operations.

[1] In most conditions, even if the data is encrypted, the access pattern can be achieved, and this pattern can leak some important information such as encryption keys.

And in the outsourcing of cloud data, this leakage of access pattern is still very serious.

For example, the sequences of user read or write the data in the cloud are access patterns.

We say a machine is oblivious if the sequence in which it accesses is equivalent for any two inputs with the same running time.

So the data access pattern is independent from the input.

Applications: Goldreich and Ostrovsky proposed this term on software protection.

In the paper composed by Goldreich and Ostrovsky have theorem to oblivious RAM: Let RAM(m) denote a RAM with m memory locations and access to a random oracle machine.

Then t steps of an arbitrary RAM(m) program can be simulated by less than ⁠

Every oblivious simulation of RAM(m) must make at least

Now we have the square-root algorithm to simulate the oblivious ram working.

To access original RAM in t steps we need to simulate it with

For each level there is a random selected hash function.

The operation is like the following: At first load program to the last level, which can be say has ⁠

⁠, there is only one real match and remaining are dummy entries .

The rightmost path may have degree one and this can help to describe the update algorithms.

Oblivious tree requires randomization to achieve a ⁠

For the tree, there are three operations: Step of Create: The list of nodes at the ithlevel is obtained traversing the list of nodes at level i+1 from left to right and repeatedly doing the following: For example, if the coin tosses of d {2, 3} has an outcome of: 2, 3, 2, 2, 2, 2, 3 stores the string “OBLIVION” as follow oblivious tree.

Both the INSERT (b, I, T) and DELETE(I, T) have the O(log n) expected running time.

And for INSERT and DELETE we have: For example, if the CREATE (ABCDEFG) or INSERT (C, 2, CREATE (ABDEFG)) is run, it yields the same probabilities of out come between these two operations.