# TSKT-ORAM: A Two-Server \(k\)-ary Tree Oblivious RAM without Homomorphic Encryption +
## 6 Security Analysis
The expectation of \(X\) is:  
\[E[X]=E\left[\sum_{i=1}^{N}X_{i}\right]=\sum_{i=1}^{N}E[X_{i}]=N\cdot\frac{k}{2N }=\frac{k}{2}. \tag{18}\]  
According to the Chernoff bound, when \(\delta=2j/k-1\geq 2e-1\), it holds that:  
\[ \begin{split}&\mathbf{Pr}\left[\text{at least $j$ balls in this bin}\right]\\ =&\mathbf{Pr}\left[X\geq j\right]<\left(\frac{e^{ \delta}}{(1+\delta)^{(1+\delta)}}\right)^{k/2}\\ <&\left(\frac{e^{\delta}}{(2e)^{\delta}}\right)^{k/2 }=2^{-k\delta/2}.\end{split}  \tag{19}\]  
Hence, letting \(j=4(k-1)\), we have:  
\[\mathbf{Pr}\left[\text{at least $4(k-1)$ balls in this bin}\right]<2^{-1.5k}. \tag{20}\]  
Finally, we have the following equation:  
\[ \begin{split}&\mathbf{Pr}\left[\exists\text{ a bin with at least $4(k-1)$ balls}\right]\\ <&\sum_{i=0}^{2N}-1\mathbf{Pr}\left[\text{ bin $i$ has at least $4(k-1)$ balls}\right]\\ <&\frac{2N}{k}\cdot 2^{-1.5k}=\frac{2N}{k}\cdot 2^{-1. 5(1.36\lambda+6.44)}\\ =&\frac{2N}{k}\cdot 2^{-2.04\lambda+9.66}<2^{- \lambda}.\end{split}  \tag{21}\]  
The first inequality is due to the union bound. The second inequality is due to the fact that \(\lambda\geq\log N+10\). According to the above two parts, we have proven that the overflow probability is \(2^{-\lambda}\). **Lemma 2**. : _Any query process in TSKT-ORAM accesses k-nodes from each layer of the k-ary tree, uniformly at random._Proof. : (Sketch) In TSKT-ORAM, each real data block is initially mapped to a leaf k-node uniformly at random; and after a real data block is queried, it is re-mapped to a leaf k-node also uniformly at random. When a real data block is queried, all k-nodes on the path from the root to the leaf k-node that the real data block is currently mapped to are accessed. Due to the uniform randomness of the mapping from real data blocks to leaf k-nodes, the set of k-nodes accessed during a query process is also uniformly at random. Any eviction process in TSKT-ORAM accesses a sequence of k-nodes independently of the client's private data request. Proof. : (Sketch) During an eviction process, the accessed sequence of k-nodes is independent of the client's private data request due to: (i) the selection of b-nodes for eviction (i.e., Phase I of the eviction process) is uniformly random on the fixed set of layers of the logical binary tree and thus is independent of the client's private data request; and (ii) the rules determining which evictions should be executed immediately (and hence, the involved k-nodes should be accessed) and which can be delayed are also independent of the client's private data requests. For any k-node \(n_{i}\) with k-node \(n_{p}\) as its parent, each position in \(P_{2}\bigcup P_{3}\) of \(n_{i}\) has the equal probability of \(\frac{1}{2c\log N}\) to be selected to access. Proof. : During an eviction process, \(n_{p}\) may evict a real or dummy block to one of its child nodes (i.e., \(n_{i}\) or \(n_{1-i}\)). In the following, we consider these two cases respectively. Case I: \(n_{p}\) evicts a real block to a child node. There are two subcases as follows. Case I-1: the real block is evicted to \(n_{i}\); this subcase occurs with the probability of 0.5. In this subcase, according to the previously described eviction policy, a position is randomly selected from \(P_{3}\) to accept the evicted block. Case I-2: the real block is evicted to \(n_{1-i}\), i.e., a dummy block is evicted to \(n_{i}\); this occurs with the probability of 0.5. In this subcase, according to the eviction policy, a position is randomly selected from \(P_{2}\) to access. Case II: \(n_{p}\) does not evict any real block to its child nodes. That is, both \(n_{i}\) and \(n_{1-i}\) are evicted with dummy blocks. In this case, according to the eviction policy, a position is randomly selected from \(P_{2}\bigcup P_{3}\) to access. Furthermore, because \(P_{2}\) and \(P_{3}\) have the same size, each position in \(P_{2}\bigcup P_{3}\) has equal probability to be selected to access. TSKT-ORAM is secure under Definition 1, if \(k\geq 1.36\lambda+6.44\) and \(c=4\). Proof.