Oblivious data structure

<h2 id="oblivious-data-structures">Oblivious data structures</h2>
<h3>Oblivious RAM</h3>
Goldreich and Ostrovsky proposed this term on software protection.
The memory access of <a href="/facts/Oblivious_ram/DeeotLyN">oblivious RAM</a> is probabilistic and the probabilistic distribution is independent of the input. 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 ⁠
 
 
 
 O
 (
 t
 (
 
 log
 
 2
 
 
 ⁡
 t
 
 )
 
 3
 
 
 )
 
 
 {\displaystyle O(t(\log _{2}t)^{3})}
 
⁠ steps of an oblivious ⁠
 
 
 
 
 R
 A
 M
 
 (
 m
 (
 
 log
 
 2
 
 
 ⁡
 m
 
 )
 
 2
 
 
 )
 
 
 {\displaystyle \mathrm {RAM} (m(\log _{2}m)^{2})}
 
⁠. Every oblivious simulation of RAM(m) must make at least 
 
 
 
 max
 {
 m
 ,
 (
 t
 −
 1
 )
 
 log
 
 2
 
 
 ⁡
 m
 }
 
 
 {\displaystyle \max\{m,(t-1)\log _{2}m\}}
 
 accesses in order to simulate t steps.
Now we have the square-root algorithm to simulate the oblivious ram working.

<ol><li>For each 
 
 
 
 
 
 m
 
 
 
 
 {\displaystyle {\sqrt {m}}}
 
 accesses, randomly permute first 
 
 
 
 m
 +
 
 
 m
 
 
 
 
 {\displaystyle m+{\sqrt {m}}}
 
 memory.</li>
<li>Check the shelter words first if we want to access a word.</li>
<li>If the word is there, access one of the dummy words. And if the word is not there, find the permuted location.</li></ol>
To access original RAM in t steps we need to simulate it with 
 
 
 
 t
 +
 
 
 m
 
 
 
 
 {\displaystyle t+{\sqrt {m}}}
 
 steps for the oblivious RAM. For each access, the cost would be O(
 
 
 
 
 
 m
 
 
 ⋅
 log
 ⁡
 m
 
 
 {\displaystyle {\sqrt {m}}\cdot \log m}
 
).
Another way to simulate is hierarchical algorithm. The basic idea is to consider the shelter memory as a buffer, and extend it to the multiple levels of buffers. For level I, there are ⁠
 
 
 
 
 4
 
 i
 
 
 
 
 {\displaystyle 4^{i}}
 
⁠ buckets and for each bucket has log t items. 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 ⁠
 
 
 
 
 4
 
 t
 
 
 
 
 {\displaystyle 4^{t}}
 
⁠ buckets. For reading, check the bucket ⁠
 
 
 
 
 h
 
 i
 
 
 (
 V
 )
 
 
 {\displaystyle h_{i}(V)}
 
⁠ from each level, If (V,X) is already found, pick a bucket randomly to access, and if it is not found, check the bucket ⁠
 
 
 
 
 h
 
 i
 
 
 (
 V
 )
 
 
 {\displaystyle h_{i}(V)}
 
⁠, there is only one real match and remaining are dummy entries . For writing, put (V,X) to the first level, and if the first I levels are full, move all I levels to ⁠
 
 
 
 I
 +
 1
 
 
 {\displaystyle I+1}
 
⁠ levels and empty the first I levels.
The time cost for each level cost O(log t); cost for every access is ⁠
 
 
 
 O
 (
 (
 log
 ⁡
 t
 
 )
 
 2
 
 
 )
 
 
 {\displaystyle O((\log t)^{2})}
 
⁠; The cost of Hashing is ⁠
 
 
 
 O
 (
 t
 (
 log
 ⁡
 t
 
 )
 
 3
 
 
 )
 
 
 {\displaystyle O(t(\log t)^{3})}
 
⁠.

<h3>Oblivious tree</h3>
An Oblivious Tree is a rooted tree with the following property:

<ul><li>All the leaves are in the same level.</li>
<li>All the internal nodes have degree at most 3.</li>
<li>Only the nodes along the rightmost path in the tree may have degree of one.</li></ul>
The oblivious tree is a data structure similar to <a href="/facts/2%25E2%2580%25933_tree/bPAFTAJP">2–3 tree</a>, but with the additional property of being oblivious. The rightmost path may have degree one and this can help to describe the update algorithms. Oblivious tree requires randomization to achieve a ⁠
 
 
 
 O
 (
 log
 ⁡
 (
 n
 )
 )
 
 
 {\displaystyle O(\log(n))}
 
⁠ running time for the update operations. And for two sequences of operations M and N acting to the tree, the output of the tree has the same output probability distributions. For the tree, there are three operations:

CREATE (L)
build a new tree storing the sequence of values L at its leaves.
INSERT (b, i,T)
insert a new leaf node storing the value b as the ith leaf of the tree T.
DELETE (i, T)
remove the ith leaf from T.
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:

<ol><li>Choose d {2, 3} uniformly at random.</li>
<li>If there are less than d nodes left at level i+1, set d equal to the number of nodes left.</li>
<li>Create a new node n at level I with the next d nodes at level i+1 as children and compute the size of n as the sum of the sizes of its children.</li></ol>
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:

INSERT (b, I, CREATE (L)) = CREATE (L [1] + …….., L[ i], b, L[i+1]………..)
DELETE (I, CREATE (L)) = CREATE (L[1]+ ………L[I - 1], L[i+1], ………..)

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.

<ul><li>Micciancio, Daniele (May 1997). "Oblivious data structures: applications to cryptography". STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">Symposium on Theory of Computing</a>. <a href="/facts/El_Paso%2c_Texas/SanXJ0WE">El Paso, Texas</a>. pp. 456–464. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F258533.258638">10.1145/258533.258638</a>.</li>
<li><a href="/facts/Oded_Goldreich/Ufn1bqW7">Goldreich, Oded</a>; <a href="/facts/Rafail_Ostrovsky/EwxNK6PS">Ostrovsky, Rafail</a> (May 1996). "Software protection and simulation on oblivious RAMs". <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>. 43 (3). <a href="/facts/Association_for_Computing_Machinery/abI2atlP">Association for Computing Machinery</a>: 431–473. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F233551.233553">10.1145/233551.233553</a>.</li>
<li><a href="/facts/John_C._Mitchell/8tzw9FNg">Mitchell, John C.</a>; Zimmerman, Joe (March 2014). "Data-Oblivious Data Structures". 31st International Symposium on Theoretical Aspects of Computer Science. <a href="/facts/Symposium_on_Theoretical_Aspects_of_Computer_Science/mc2KvrdL">Symposium on Theoretical Aspects of Computer Science</a>. <a href="/facts/Lyon%2c_France/hKh6EX67">Lyon, France</a>. pp. 554–565. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4230%2FLIPIcs.STACS.2014.554">10.4230/LIPIcs.STACS.2014.554</a>.</li>
<li><a href="/facts/Craig_Gentry_(computer_scientist)/VrzFdLyQ">Gentry, Craig</a>; Goldman, Kenny A.; Halevi, Shai; Jutla, Charanjit S.; Raykova, Mariana; Wichs, Daniel (July 2013). "Optimizing ORAM and Using It Efficiently for Secure Computation". 13th International Symposium, PETS 2013. Privacy Enhancing Technologies Symposium. <a href="/facts/Bloomington%2c_IN/kF5HqGJ7">Bloomington, IN</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-39077-7_1">10.1007/978-3-642-39077-7_1</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Wang, Xiao; Nayak, Kartik; Liu, Chang; Chan, Hubert; Shi, Elaine; Stefanov, Emil; Huang, Yan (November 2014). "Oblivious Data Structures". CCS '14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. Scottsdale, Arizona. pp. 215–226. doi:10.1145/2660267.2660314. <a href="/wiki/Elaine_Shi" target="_blank">/wiki/Elaine_Shi</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Oblivious data structure open-in-new

Oblivious data structure