# TSKT-ORAM: A Two-Server \(k\)-ary Tree Oblivious RAM without Homomorphic Encryption +
## 5 Final Construction: TSKT-ORAM
### Data Eviction
#### 5.5.2 The Algorithm  
Based on the previously-explained idea, the eviction algorithm is designed to include the following three phases. * Phase I, selecting b-nodes for inter-k-node eviction: In this phase, the client randomly selects two b-nodes from each layer \(l^{\prime}\in\{\log k-1,2\log k-1,\ldots,(\lceil\frac{\log N+1}{\log k}\rceil-1 )\cdot\log k-1\}\) on the binary tree; that is, each selected b-node must be on the bottom layer of the binary subtree within a certain non-leaf k-node. Each selected b-node needs to evict a data block to its child nodes, which are in other k-nodes. Hence, the eviction has to be an inter k-node eviction and should be conducted immediately. * Phase II, conducting delayed intra-k-node evictions: Each inter-k-node eviction planned in the previous phase involves three k-nodes: the k-node that contains the evicting b-node and the two other k-nodes that contain the child b-nodes of the evicting b-node. Before the inter-k-node eviction is executed, we need to make sure that the three involved k-nodes have completed all delayed evictions within them, and this is the purpose of this phase. Figure 4: An example data eviction process in TSKT-ORAM with a quaternary-tree storage structure. In the logical view (i.e., binary-tree view) of the tree, the root b-node and two b-nodes from each layer, which are circled in the figure, are selected to evict data blocks to their child nodes; thus, the k-nodes that contain these selected b-nodes or their child nodes are also involved in the eviction. With the delay eviction mechanism, not all of these evictions have to be performed immediately. Instead, the evictions that occur within the same k-node, for example, the evictions from \(v_{4,3}\) to its child nodes and from \(v_{4,11}\) to its child nodes, occur in k-nodes \(u_{2,3}\) and \(u_{2,11}\), respectively, which are highlighted with bold boundaries, can be delayed to reduce the eviction overhead. More specifically, the following three steps should be taken for each k-node, denoted as \(u_{l,j}\), which is involved in an inter-k-node eviction planned in the previous phase. Note that, here, \(l\) denotes the layer of the k-node on the \(k\)-ary tree. 1. The client downloads the EI of \(u_{l,j}\), decrypts it and extracts the value of field \(ts\). 2. The client computes \(r=\mathcal{C}-ts\). Note that, \(\mathcal{C}\) counts the number of queries issued by the client, which is also the number of eviction processes that have been launched, and \(ts\) is the discrete timestamp for the latest access of \(u_{i,j}\). Hence, \(r\) is the number of eviction processes for which \(u_{l,i}\) may have delayed its intra-k-node evictions. 3. The client simulates the \(r\) eviction processes to find out and execute the delayed intra-k-node evictions. In particular, for each of the eviction processes: 1. The client randomly selects two b-nodes from each binary-tree layer \(l^{\prime}\in\{l\cdot\log k,l\cdot\log k+1,\ldots,(l+1)\cdot\log k-2\}\). Note that layer \(l^{\prime}\) is not a leaf binary-tree layer within a k-node, and therefore, any b-node selecting from the layer only has child nodes within the same k-node; in other words, the eviction from the selected b-node must be an intra-k-node eviction. 2. For each previously selected b-node that is within k-node \(u_{l,i}\), one data block is picked from it, and the \(lb1D\) field of the block is updated to one of its child nodes that the block can be evicted to; this way, the delayed eviction from the selected b-node is executed. 4. After the previous step completes, all the delayed evictions within k-node \(u_{l,i}\) have been executed. Therefore, the \(ts\) field in the EI of \(u_{l,j}\) is updated to \(\mathcal{C}\). * Phase III, conducting inter-k-node evictions: For each inter-k-node eviction planned in the first phase, its involved k-nodes should have conducted all of their delayed evictions in the second phase. Hence, the planned inter-k-node eviction can be conducted now.