# TSKT-ORAM: A Two-Server \(k\)-ary Tree Oblivious RAM without Homomorphic Encryption +
## 5 Final Construction: TSKT-ORAM
### Data Eviction
#### 5.5.1 Overview  
The purpose of data eviction in TSKT-ORAM is essentially the same as in TSBT-ORAM. Thus, it could be conducted as follows: Over the logical binary tree view of the \(k\)-ary tree, the eviction process requires the root b-node and two randomly selected b-nodes from each non-leaf layer to each evict a data block to its child nodes. The evicted data block is ideally a real data block; but a dummy block is evicted if a selected node does not have a real data block. The eviction process is ensured to be oblivious with the same techniques used in TSBT-ORAM.  
Adopting the above approach, however, would not take advantage of the \(k\)-ary tree structure and would incur a client-server communication cost of \(O(\log N)\) blocks per query, which is similar to the eviction cost incurred by existing binary tree-based ORAM constructions. In order to leverage the \(k\)-ary tree structure to reduce the eviction cost, we propose to opportunistically delay and aggregate evictions that occur within a k-node. We call such kinds of evictions as intra k-node evictions, while call other evictions as inter k-node evictions. Next, we use the examples in Figure 4 to explain the idea.  
In the figure, b-node \(v_{2,2}\) is selected to evict a data block to its child nodes, and this node and its child nodes all belong to the same k-node \(u_{1,2}\). Hence, the eviction from \(v_{2,2}\) is an intra k-node eviction. Because b-nodes belonging to the same k-node share one DA space to store their data blocks, an intra k-node eviction can be conducted by only updating the EI of the k-node to reflect the change of the \(bn1D\) field of the evicted block, without physically moving the block. That is, an intra k-node eviction can be conducted more efficiently. On the other hand, evicting a data block from b-node \(v_{3,2}\) to its child nodes is an inter k-node eviction, because this b-node and its child nodes belong to three different k-nodes. These b-nodes do not share DA space, and thus, the eviction has to be conducted by moving blocks across k-nodes. This is less efficient than an intra k-node eviction.  
Furthermore, we find that it is not always necessary to immediately conduct intra k-node eviction. Instead, such evictions can be delayed and aggregated opportunistically. More specifically, we may find that a k-node is not involved in any inter k-node eviction during an eviction process; that is, its root b-node is not a child of any node selected to evict data block, and meanwhile, its leaf b-nodes do not evict data blocks. For example, k-node \(u_{2,3}\) and \(u_{2,11}\) are such k-nodes in Figure 4. For intra-k-node evictions occurring within such k-nodes (e.g., the evictions from \(v_{4,3}\) and \(v_{4,11}\) to their child nodes), we do not have to conduct them immediately; rather, they can be conducted (i.e., updating the EIs of the k-nodes) later when the k-node is next accessed in a query process or an inter-k-node eviction. Note that such a delay does not affect the correctness of the eviction process, because the EIs will not be accessed before the updates are made; moreover, the delay could allow more intra k-node evictions to be conducted at once, i.e., intra-k-node evictions could be aggregated, which could further reduce the cost.