# TSKT-ORAM: A Two-Server \(k\)-ary Tree Oblivious RAM without Homomorphic Encryption +
## 4 Preliminary Construction: TSBT-ORAM
### Data Eviction Process
#### 4.3.3 Oblivious Receiving of Evicted Data Block  
After the client has retrieved \(D\), the block should be re-encrypted and then evicted to a child of the evicting node \(v_{l,x}\). On the high level, there are the following two cases:  
* Case I: \(D\) is a real data block.Without loss of generality, suppose \(D\) needs to be evicted to \(v_{l+1,2x}\); meanwhile, a dummy block \(D^{\prime}\) needs to be evicted to \(v_{l+1,2x+1}\) to achieve obliviousness. To reduce the communication cost, \(D\) is treated also as the dummy data block \(D^{\prime}\) when evicted to \(v_{l+1,2x+1}\).
* Case II: \(D\) is a dummy data block. In this case, \(D\) is evicted to both \(v_{l+1,2x}\) and \(v_{l+1,2x+1}\) as a dummy data block.  
Next, we explain the details of the above process.  
Figure 2: An example of the eviction process in TSBT-ORAM.  
The storage space of each node on the server storage tree is logically partitioned into three equally-sized parts, denoted as \(P_{1}\), \(P_{2}\) and \(P_{3}\), and each part can store \(c\log N\) data blocks.  
* \(P_{1}\): This part is used by the node to store the latest \(c\log N\) evicted data blocks, which could be dummy or real, from its parent.
* \(P_{2}\): This part is used to store each real data block that still remains in the node after more than \(c\log N\) (dummy or real) blocks have been evicted to the node since the arrival of this real block. Since the number of real data blocks stored in any node is at most \(c\log N\), this part may contain dummy blocks.
* \(P_{3}\): This is the storage space other than \(P_{1}\) and \(P_{2}\) in the node. This part contains only dummy data blocks.  
Note that the servers only know \(P_{1}\) and the union of \(P2\) and \(P3\); the partitioning between \(P_{2}\) and \(P_{3}\) is known only to the client. A node uses only \(P2\) or \(P3\) to receive data blocks evicted from its parent. Furthermore, \(P_{1}\), \(P_{2}\) and \(P_{3}\) are only logical partitions, and they could change from time to time. For example, when one position in \(P_{2}\) or \(P_{3}\) is used to accept a data block evicted from the parent node, this position is transferred to \(P_{1}\); meanwhile, the oldest position in \(P_{1}\) is automatically transferred from \(P_{1}\) to \(P_{2}\) or \(P_{3}\).  
Based on the above logical partitioning, the client evicts the data block \(D\) from \(v_{l,x}\) to \(v_{l+1,2x}\) or \(v_{l+1,2x+1}\) as follows. First, if \(D\) is a real data block, there are the following two cases:  
* If \(D\) should be evicted to \(v_{l+1,2x}\) (i.e., \(D\) is assigned to the path passing \(v_{l+1,2x}\)), one position in partition \(P_{3}\) of node \(v_{l+1,2x}\) is randomly picked to receive \(D\), and meanwhile, one position in partition \(P_{2}\) or \(P_{3}\) of node \(v_{l+1,2x+1}\) is randomly picked to receive a dummy block.
* Otherwise (i.e., \(D\) should be evicted to \(v_{l+1,2x+1}\)), one position in partition \(P_{3}\) of \(v_{l+1,2x+1}\) is randomly picked to receive \(D\), while one position in partition \(P_{2}\) or \(P_{3}\) of \(v_{l+1,2x}\) is randomly picked to receive a dummy block.  
Second, if \(D\) is a dummy data block (i.e., \(v_{l,x}\) has no real block to evict), for \(v_{l+1,2x}\) (and \(v_{l+1,2x+1}\) respectively), the client randomly picks a position from partitions \(P_{2}\) and \(P_{3}\) of \(v_{l+1,2x}\) (and \(v_{l+1,2x+1}\), respectively) to receive a dummy block. After the reception, the positions of nodes \(v_{l+1,2x}\) and \(v_{l+1,2x+1}\) join partition \(P_{1}\) of the two nodes, respectively, and the least-recently receiving position in each of the two nodes joins partition \(P_{1}\).  
As will be proven in Section 6, each position in \(P_{2}\,\cup\,P_{3}\) has the same probability to be selected to receive a data block evicted from the parent; thus, the eviction process is oblivious and is independent of the data access pattern.