# TSKT-ORAM: A Two-Server \(k\)-ary Tree Oblivious RAM without Homomorphic Encryption +
## 6 Security Analysis  
In this section, we first study the failure probability of TSKT-ORAM, which is followed by the study of its obliviousness. These studies finally lead to the main theorem. **Lemma 1**. : _The probability for a DA in any k-node to overflow is no greater than \(2^{-\lambda}\), as long as the parameters of TSKT-ORAM meet the following conditions:_  
* \(3c(k-1)\) _data blocks are stored in each DA;_
* \(k\geq 1.36\lambda+6.44\)_;_
* \(c=4\)_; and_
* \(\lambda>\log N+10\)_._  
Proof. : The proof considers non-leaf and leaf k-nodes separately. Non-leaf k-nodes:  
The proof for non-leaf k-node proceeds in the following two steps. In the first step, we consider the binary tree that a \(k\)-ary tree in TSKT-ORAM is logically mapped to and study the number of real data blocks (denoted as a random variable \(X_{v}\)) logically belonging to an arbitrary b-node \(v\) on an arbitrary level \(l\) of the binary tree. As the eviction process of TSKT-ORAM completely simulates the eviction process of T-ORAM and P-PIR over the logical binary tree, the results of [22] of the theoretical study on the number of real data blocks in a binary tree node can still apply. Specifically, \(X_{v}\) can be modeled as a Markov chain denoted as \(\mathcal{Q}(\alpha_{l},\beta_{l})\). In the chain, the initial one is \(X_{v}=0\), The transition from \(X_{v}=i\) to \(X_{v}=i+1\) occurs with probability \(\alpha_{l}\), and the transition from \(X_{v}=i+1\) to \(X_{v}=i\) occurs with probability \(\beta_{l}\), for every non-negative integer \(i\). Here, \(\alpha_{l}=1/2^{l}\) and \(\beta_{l}=2/2^{l}\) for any level \(l\). Furthermore, for any \(l\geq 2\), a unique stationary distribution exists for the chain; that is,  
\[\pi_{l}(i)=\rho_{l}^{i}(1-\rho_{l}), \tag{9}\]  
where:  
\[\rho_{l}=\frac{\alpha_{l}(1-\beta_{l})}{\beta_{l}(1-\alpha_{l})}=\frac{2^{l}- 2}{2(2^{l}-1)}\in\left[\frac{1}{3},\frac{1}{2}\right). \tag{10}\]  
In the second step, we consider an arbitrary k-node \(u\) on the \(k\)-ary tree and study the number of real data blocks stored at the DA of \(u\), which is denoted as a random variable \(Y_{u}\). The binary subtree that \(u\) is logically mapped to contains \(k-1\) b-nodes, which are denoted as \(v_{1},\ldots,v_{k-1}\) for simplicity. Then \(Y_{u}=\sum_{i=1}^{k-1}X_{v_{i}}\). Furthermore, as \(k\) should be greater than two to make TSKT-ORAM nontrivial, any of the b-nodes \(v_{1},\ldots,v_{k-1}\) should be on a level greater than or equal to one on the logical binary tree (those b-nodes on Levels 0 and 1 never overflow). Now, we compute the probability:  
\[\textbf{Pr}\left[Y_{u}=t\right]=\textbf{Pr}\left[X_{v_{1}}+\cdots+X_{v_{k-1}} =t\right]. \tag{11}\]  
Note that there are \(\binom{t+k-2}{k-2}\) different combinations of \(X_{i}=t_{i}\) (\(i=1,\ldots,k-1\)) such that \(t_{1  
Then, the following inequalities follow:  
\[ \begin{split}\mathbf{Pr}\left[Y_{u}\geq t\right]&= \sum_{i=0}^{\infty}\mathbf{Pr}\left[Y_{u}=t+i\right]<\sum_{i=0}^{\infty}[(\frac{ 3}{5})^{1/4}]^{t+i}\\ &=\frac{(\frac{3}{5})^{t/4}}{1-(\frac{3}{5})^{1/4}}<9\cdot 2^{-0.74 (k-1)}<2^{-\lambda}.\end{split}  \tag{16}\]  
Leaf k-nodes:  
At any time, all the leaf k-nodes contain at most \(N\) real blocks, and each of the blocks is randomly placed into one of the leaf k-nodes. Thus, we can apply the standard balls and bins model to analyze the overflow probability. In this model, \(N\) balls (real blocks) are thrown into \(2N/k\) bins (i.e., leaf k-nodes) in a uniformly random manner. We study one arbitrary bin and let \(X_{1},\ldots,X_{N}\) be \(N\) random variables such that:  
\[X_{i}=\left\{ \begin{array}{ll}1&\text{the $i$-th ball is thrown into this bin},\\ 0&\text{otherwise}.\end{array} \right. \tag{17}\]  
Note that \(X_{1},\ldots,X_{N}\) are independent of each other, and hence, for each \(X_{i}\), \(\mathbf{Pr}\left[X_{i}=1\right]=\frac{1}{2N/k}=\frac{k}{2N}\). Let \(X=\sum_{i=1}^{N}X_{i}\).