# Searchable Data Vault: Encrypted Queries in Secure Distributed Cloud Storage
## 4 A Multi-Server SSE Scheme
#### Security Analysis  
By referring to Definition 1 and the description of the scheme in Figure 3, we say that \(\mathsf{SSE}_{SDV}\) is \(\mathcal{L}\)-secure against non-adaptive keyword attack by colluding servers, if the underlying pseudorandom function \(F\) and the symmetric encryption scheme \(\mathcal{E}\) is IND-CPA-secure. In the following, we define the leakage profiles \(\mathcal{L}\) based on an adversary \(\mathcal{A}\) who controls all storage servers. This means the adversary sees leakages from all storage servers involved in the system. \(\mathsf{SSE}_{SDV}=(\mathsf{Setup},\mathsf{Search},\mathsf{Update})\)  
**Input:** A set of \(n\) documents \(\{D_{1},\ldots,D_{n}\}\), filenames of the documents (as keyword index), a list of \(s\) server identifiers \(\{S_{1},\ldots,S_{s}\}\). **Output:** A set of secret keys \(K\), a set of encrypted blocks \(C\) and an index table \(I\). 1. Generate a master key \(mk\) and for \(j=1\) to \(s,s=|S|\colon k_{j}\leftarrow\mathcal{E}.\mathsf{Gen}(1^{\lambda})\). 2. Set \(K=(mk,(k_{1},\ldots,k_{s}))\). 3. Initialize empty index \(I\) and a set of list \(C=\{\mathbf{c}_{1},\ldots\mathbf{c}_{s}\}\). 4. Create temporary empty list \(\mathbf{t}\). 5. For \(i=1\) to \(n\): 1. Divide \(D_{i}\) into blocks: \(D_{i}=\{d_{i,1}||1,d_{i,2}||2,\ldots,d_{i,h}||h\}\). 2. Generate keyword token \(tok_{i}\gets F(mk,\text{filename}(D_{i}))\). 3. For \(x=1\) to \(h\): * Randomly select a cloud server: \(j\stackrel{{ R}}{{\leftarrow}}[s],s=|S|\). * Encrypt \(d_{i,x}||x\): \(e_{d_{i,x}}\leftarrow\mathcal{E}.\mathsf{Enc}(k_{j},d_{i,x}||x)\). * Store \(id(e_{d_{i,x}})\) and \(e_{d_{i,x}}\) in \(\mathbf{c}_{j}\). * Append \(id(e_{d_{i,x}})||j\) in \(\mathbf{t}\). 4. Set \(I[tok_{i}]=\mathbf{t}\). 6. Output \(K,C\) and \(I\). **Input:** A keyword (\(filename\)). **Output:** A sequence of tuple (block identifier, server identifier) or false. 1. SDV API: \(tok_{i}\gets F(mk,\text{filename}(D_{i}))\). 2. SDV controller: If \(tok_{i}\) does not match any entry in \(I\), return \(\bot\), else return \(I[tok_{i}]\). **Update**  
**Input:** An operation op (add or remove), optionally an input object (a filename), the index table \(I\) and the set of server identifiers. **Output:** True with the updated index \(I^{\prime}\), or false (for unsuccessful addition or removal). 1. For \(\mathsf{op}=\mathsf{Doc+}\), \(\mathsf{in}=filename(D_{a})\), execute Step 4 and Step 5 of Setup and update \(I\) by adding \(I[tok_{a}]\). 2. For \(\mathsf{op}=\mathsf{Doc-}\): \(\mathsf{in}=\text{filename}(D_{x})\), execute Search and update \(I\) by deleting \(I[tok_{x}]\). 3. Output \(I^{\prime}\) as the updated index \(I\). \(\mathcal{L}^{setup}=(|B|,b)\): For setup, the information leaked to the adversary is the number of blocks of a server \(|B|\) and the block size of the encrypted blocks, where the block size is denoted as \(b\). A fixed block size means the storage servers cannot even study the difference in size of the encrypted blocks to learn which document a block belongs to. However, in our current implementation, we use a range of different block sizes so that it is efficient in generating the index entries and submission of encrypted blocks of large documents. This means the storage servers learn different sizes of encrypted blocks. Figure 3: \(\mathsf{SSE}_{SDV}\): Description of the scheme. \(\mathcal{L}^{query}=|B_{q}|\): For search, the adversary learns the number of encrypted blocks associated to the input keyword token. This is because the SDV controller sends retrieval requests to the cloud storage servers to retrieve encrypted blocks of a document. Here, we denote the number of retrieved encrypted blocks as \(|B_{q}|\). \(\mathcal{L}^{update}=|B_{q}|\): Adding and removing a document includes submitting the encrypted blocks, or removing the encrypted blocks of a document from the cloud storage servers. Thus, the leakage is similar to \(\mathcal{L}^{query}\), where the adversary learns the number of encrypted blocks associated to the document.