# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 6 Security and Performance Analysis  
### Security  
In this section, we focus on the the security of the SSP-SSE scheme. First, we show that the SSP-SSE scheme is correct according to Definition 13. Second, we prove that the SSP-SSE scheme is secure against the Chosen-Query Attack (CQA-2) executed by the adaptive adversary according to Definition 17. **Theorem 18**: **(Correctness). ** _The Substring Positions Searchable Symmetric Encryption (SSP-SSE) scheme consisting of six polynomial-time algorithms (KeyGen, BuildTree, Encrypt, ConstructQuery, Search, Decrypt) is correct according to Definition 13._  
The index \(I\) in the Search algorithm consists of the encrypted position heap tree \(\tilde{\Lambda}\) and two arrays \(X\), \(Y\) (both encrypted). Since the path labels in \(\tilde{\Lambda}\) and the search query \(Q\) are both encrypted with the same instance of pseudorandom function \(F\) with the same secret key \(K_{Q}\), the correctness of the SSP-SSE scheme relies on the correctness of the pseudorandom function. When the cloud provider receives the search query \(Q\) in the Search algorithm, it traverses the path labels in the encrypted position heap tree \(\tilde{\Lambda}\) according to Definition 11. Search query \(Q\) is constructed using the pseudorandom function \(F\) applied on the substring \(\chi\) with key \(K_{Q}\). Each encrypted path label in \(\tilde{\Lambda}\) is constructed using the pseudorandom function \(F\) with the key \(K_{Q}\) on the set of characters extracted from the plaintext document collection \(D=\{D_{1},\ldots,D_{l}\}\). The search algorithm outputs true if the document \(D_{i}\) contains the string of characters \(\chi\). Thus, the cloud provider outputs a set of documents that matches the search query \(Q\). **Theorem 19**: **(Security). ** _Let SKE be a symmetric PCPA-secure encryption scheme, \(F\) be a pseudorandom function and \(P\) be a pseudorandom permutation. Substring Position Searchable Symmetric Encryption (SSP-SSE) presented above is \((\mathbb{L}_{1},\mathbb{L}_{2})\)-adaptively secure against chosen-query attacks defined in Definition 17 (CQA-2 security), where \(\mathbb{L}_{1}\) and \(\mathbb{L}_{2}\) are the possible leakages._  
In a nutshell, the proof of security of SSP-SSE scheme works as follows. The simulator \(\mathbb{S}\) generates a simulated searchable index \(\widetilde{I}\) that consists of simulated encrypted position heap tree \(\tilde{\Lambda}\), simulated position array \(\widetilde{Y}\) and simulated text array \(\widetilde{X}\), i.e., \(\widetilde{I}=(\widetilde{\Lambda},\widetilde{Y},\widetilde{X})\); as well as the simulated set of ciphertexts \(\widetilde{C}=\{\widetilde{C}_{1},\ldots,\widetilde{C}_{l}\}\). Both \(\widetilde{I}\) and \(\widetilde{C}\) are constructed using the leakage \(\mathbb{L}_{1}\) that discloses the number of encrypted documents, the size of the encrypted documents and the identifier of each encrypted document. The simulated encrypted position heap tree \(\widetilde{\Lambda}\) is constructed using the pseudorandom function \(F\) and symmetric-key encryption SKE with random values \(\{0,1\}\). Both simulated \(\widetilde{Y}\) and \(\widetilde{X}\) are constructed using the pseudorandom permutation \(P\) and symmetric-key encryption SKE on random values \(\{0,1\}\). The security of the proposed scheme relies on the following assumptions. The pseudo-randomness of \(F\) guarantees that the simulated encrypted position heap tree \(\tilde{\Lambda}\) is indistinguishable from the real encrypted position heap tree \(\tilde{\Lambda}\). The pseudo-randomness of \(P\) will guarantee that simulated \(\widetilde{Y}\) and \(\widetilde{X}\) are indistinguishable from the real \(Y\) and \(X\). Moreover, the simulated set of ciphertext \(\widetilde{C}\) is indistinguishable from the real encrypted document collection \(C\). The search algorithm is simulated in a similar way that requires keeping track of different dependencies between the result output and the search query.