# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 6 Security and Performance Analysis
### Security
However, since the real search query is constructed with pseudorandom function \(F\) and pseudorandom permutation \(P\), the simulator is not able to distinguish it from the simulated query. Similarly, the simulated outcome of the search is indistinguishable from the real set of nodes. We outline the formal proof as follows. Proof. : Polynomial-size simulator \(\mathbb{S}\) can be defined such that for any challenger and any polynomial-time adversary \(\mathbb{A}\), the outputs of two experiments \(\mathit{Ideal}_{\mathbb{A}\mathbb{S}}(k)\) and \(\mathit{Real}_{\mathbb{A}}(k)\) with secret parameter \(k\) are computationally indistinguishable according to Definition 17. We now describe the details of experiment \(\mathit{Ideal}_{\mathbb{A}\mathbb{S}}(k)\) that presents the simulator \(\mathbb{S}\). * \(\mathbb{S}(1^{k},\mathbb{L}_{1})\): The simulator \(\mathbb{S}\) has a leakage \(\mathbb{L}_{1}\), which gives the simulator information about the number and size of documents, as well as identifier of each encrypted document. The simulator \(\mathbb{S}\) randomly generates a set of simulated ciphertexts \(\widetilde{C}\) and simulated searchable index \(\widetilde{I}\) as follows:
* Simulator \(\mathbb{S}\) outputs the set of ciphertexts \(\widetilde{C}=\{\widetilde{C_{1}},\ldots,\widetilde{C_{l}}\}\), where \(\widetilde{C_{i}}\stackrel{{ R}}{{\leftarrow}}\{0,1\}^{|D_{i}|}\). * Simulator \(\mathbb{S}\) sets the simulated encrypted position heap tree \(\widetilde{\Lambda}\), where each node is set as \(\widetilde{V}(v[i])\stackrel{{ R}}{{\leftarrow}}\{0,1\}^{k}\) and each path label of node \(v[i]\) is set as \(\widetilde{L}(v[i])\stackrel{{ R}}{{\leftarrow}}\{0,1\}^{k}\), where \(i\in[1;n]\). The simulator outputs the encrypted position heap tree \(\widetilde{\Lambda}\). * Simulator \(\mathbb{S}\) then constructs simulated arrays \(\widetilde{X}\) and \(\widetilde{Y}\): \(\widetilde{X}[i]=\{0,1\}^{k}\) and \(\widetilde{Y}[i]=\{0,1\}^{k}\), where \(i\in[1;n]\). * Simulator \(\mathbb{S}\) outputs simulated searchable index \(\widetilde{I}=(\widetilde{\Lambda},\widetilde{Y},\widetilde{X})\) and the set of simulated ciphertexts \(\widetilde{C}\). At this point, the simulator \(\mathbb{S}\) generated the set of simulated encrypted documents \(\widetilde{C}\) and simulated index \(\widetilde{I}\). Next, the adversary \(\mathbb{A}\) adaptively queries the polynomial-size simulator \(\mathbb{S}\) as follows. * \(\mathbb{S}(1^{k},\mathbb{L}_{1},\mathbb{L}_{2})\): The adversary \(\mathbb{A}\) sends a new query \(Q\) to the simulator \(\mathbb{S}\). The simulator then starts collecting various dependencies between the incoming search query and the resulting output. * With given search query \(Q\), simulator \(\mathbb{S}\) traverses the simulated encrypted position heap tree \(\widetilde{\Lambda}\) starting from the root node, following the simulated path labels to find the set of matching encrypted nodes in \(\widetilde{\Lambda}\). The simulator outputs the set of simulated matching nodes: \(\widetilde{ancestors}\) and \(\widetilde{descandants}\). * With given search requests \((\widetilde{y}_{1},\ldots,\widetilde{y}_{num})\), the simulator performs a search in simulated array \(\widetilde{Y}\) and returns matching elements \((\widetilde{Y}_{1},\ldots,\widetilde{Y}_{num})\). * With given search requests \((\widetilde{x}_{1},\ldots,\widetilde{x}_{h})\), the simulator performs a search in simulated array \(\widetilde{X}\) and returns matching elements \((\widetilde{X}_{1},\ldots,\widetilde{X}_{h})\). We now need to show that the outputs of the two experiments \(\mathit{Ideal}_{\mathbb{A}\mathbb{S}}(k)\) and \(\mathit{Real}_{\mathbb{A}}(k)\) are indistinguishable. Since the simulator generates randomly the set of ciphertexts \(\widetilde{C}\), the output of the simulator is truly indistinguishable from the real ciphertexts that are generated with the PCPA-secure symmetric encryption SKE scheme using secret key \(K_{1}\).