# TSKT-ORAM: A Two-Server \(k\)-ary Tree Oblivious RAM without Homomorphic Encryption +
## 3 Problem Definition  
We consider a system model as follows. A client exports \(N\) equally-sized data blocks to two remote storage servers, where the two servers do not collude with each other. Note that such an architecture is feasible in practice, since the client can select two servers in a way that they will not know the existence of each other. For example, a client can simply select Amazon S3 and Google Drive as two independent storage servers. Each of the two servers has an identical copy of the data storage.  
The client accesses the exported data every now and then and wishes to hide the pattern of the accesses from the server. Specifically, the client has two types of private accesses to the data stored at the server, as follows:  
* private read \(D=(read,i)\);
* private write \((write,i,D)\).  
Here, \(i\) and \(D\) denote the ID and content of the accessed data block, respectively. These two types can be uniformly denoted as \((op,i,D)\), where \(op\) can be either _read_ or _write_ and should be kept secret.  
To hide each private access to data, the client usually needs to access the storage server multiple times. As the server can observe the locations accessed by the client, we shall prevent the pattern of location access from leaking any information about the data access. There are two types of location access:  
* retrieval from a location, denoted as \(D=(read,l)\);
* uploading to a location, denoted as \((write,l,D)\).  
Here, \(l\) and \(D\) denote the accessed location and the data block retrieved or uploaded, respectively. The two types can also be generalized to \((op,l,D)\), where \(op\) is either _read_ or _write_.  
As the ORAM construction is to protect the client's data access pattern from the cloud storage server, we assume the client to be trustworthy, while assuming the server to be honest but curious. That is, though the server may attempt to find out the client's data access pattern, it honestly stores data and responds to the client's requests for location access. We assume the client-server connection to be secure, which can be accomplished using mechanisms like SSL [34].  
Following the definitions adopted by existing ORAM constructions [23; 25; 12], the security of our proposed ORAM is formalized as follows.  
**Definition 1**.: _Given:_  
* _security parameter_ \(\lambda\)_;_
* _two arbitrary equal-length sequences of private data access denoted as_ \(\vec{x}=\langle\ (op_{x,1},i_{x,1},D_{x,1})\)_,_ \((op_{x,2},i_{x,2},D_{x,2})\)_,_ \(\cdots\ \rangle\) _and_ \(\vec{y}=\langle\ (op_{y,1},i_{y,1},D_{y,1})\)_,_ \((op_{y,2},i_{y,2},D_{y,2})\)_,_ \(\cdots\ \rangle\)_; and_
* _two sequences of the client's access to storage locations that correspond to_ \(\vec{x}\) _and_ \(\vec{y}\)_, denoted as_ \(A(\vec{x})=\langle\ (op^{\prime}_{x,1},l_{x,1},D^{\prime}_{x,1})\)_,_ \((op^{\prime}_{x,2},l_{x,2},D^{\prime}_{x,2})\)_,_ \(\cdots\ \rangle\) _and_ \(A(\vec{y})=\langle\ (op^{\prime}_{y,1},l_{y,1},D^{\prime}_{y,1})\)_,_ \((op^{\prime}_{y,2},l_{y,2},D^{\prime}_{y,2})\)_,_ \(\cdots\ \rangle\)_._  
_An ORAM construction is secure if:_  
* \(A(\vec{x})\) _and_ \(A(\vec{y})\) _are computationally indistinguishable; and_
* _the construction fails with a probability no greater than_ \(2^{-\lambda}\)_._