# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 6 Security and Performance Analysis
### Performance  
In this section, we outline the performance of the proposed solution. We assume that the encryption and decryption using the SKE scheme take \(O(k)\) time, where \(k\) is the security parameter. We also assume that the element selection from the array takes \(O(1)\) time. We first focus on the encryption efficiency of the SSP-SSE scheme. Given plaintext position heap tree \(\Lambda\) with \(n\) nodes, we compute encrypted position heap tree \(\Lambda\) using SKE in \(O(kn)\) time. The arrays\(X\) and \(Y\) each have \(n\) elements and can be computed in \(O(kn)\) time. Therefore, encryption takes \(O(kn)\) time, and the total ciphertext is \(O(kn)\) in size. We now analyze the efficiency of proposed search algorithm. The cloud user inputs a substring \(\chi\) of length \(m\) and outputs a search query in \(O(m)\) time. The cloud provider uses \(\tilde{\Lambda}\), performs \(m\) matches in the tree and retrieves \(occ\) descendant nodes, in \(O(m+occ)\) time. The cloud user then computes \(y_{1},\ldots,y_{m+occ}\) elements, and the cloud provider retrieves \(Y[y_{1}],\ldots,Y[y_{m+occ}]\) in \(O(m+occ)\) time. The cloud user then computes \(x_{1},\ldots,x_{m^{2}}\) elements (the cloud user wants to inspect \(m\) ancestor positions and the substring \(\chi\) of \(m\) length that may appear at each ancestor position), and the cloud provider retrieves \(X[x_{1}],\ldots,X[x_{l^{2}}]\) in \(O(m^{2})\) time. Now, the cloud user performs an inspection of \(m\) ancestors \(m\) times, making execution in \(O(m^{2})\) time. Thus, both the cloud user and the cloud provider take computation time \(O(m^{2}+occ)\) in the query protocol and three rounds of communication to complete the execution of the protocol. We have developed and implemented a proof-of-concept prototype of the SSP-SSE scheme using C++ language. Our prototype leverages the libtomcryptographic library[33], which is a portable C cryptographic library that supports symmetric ciphers, one-way hashes, pseudo-random number generators and a plethora of support routines. We use libtomcrypt to build the searchable index \(I\) and encrypt the document collection. We utilize AES-CTR encryption for the SKE symmetric-key encryption scheme, HMAC-SHA1 for pseudorandom function \(F\) and DES encryption for pseudorandom permutation \(P\). We show a thorough experimental evaluation of the SSP-SSE scheme on a real-world dataset: the Genome database [34] (published by the National Center for Biotechnology Information, National Institutes of Health) that contains sequence data from the whole genomes of over 1000 species or strains. The database includes all three main domains of life (Bacteria, Archaea and Eukaryota), as well as many viruses, phages, viroids, plasmids and organelles. All experiments have been performed on a six-core Intel Xeon E5645 2.40-GHz processor and 98 GB memory running 64-bit Fedora 23. The cloud server, data owner and cloud user applications were run on the same machine, as the network communication overhead was assumed to be negligible. For our experiments, we pick large mRNA transcript datasets of various insects. Table 2 shows the details of the experimental set. Figure 5a shows the overhead of constructing the encrypted position heap tree \(\Lambda\). We compare the time of the construction of the plaintext position heap tree (original algorithm) and the encrypted position heap tree proposed in this work. Figure 5b shows the storage overhead of searchable index \(I\) that consists of encrypted position heap tree \(\Lambda\), position array \(Y\) and text array \(X\). In short, we notice that the proposed scheme adds insignificant overhead to the computation time; however, its storage overhead depends on the block cipher size of the underlying encryption schemes. We believe that the proposed solution can be easily deployed in a real-world cloud environment.