# MinHash-Based Fuzzy Keyword Search of Encrypted Data across Multiple Cloud Servers
## 4 Security and Performance Analysis
### Security Analysis  
**Theorem 1**. : _If DDH is established, no attacker can launch keyword attacks to destroy the system._  
Proof. : If attacker A (a cloud storage server) wins the game IND-CKA with a non-negligible probability, then challenger C can use attacker A to solve challenge DDHP with an ignorable probability. Challenger C can challenge the game in the following steps:  
* System establishment: Select DDHP parameters \(\mathrm{h_{1}}=\mathrm{g^{a}}\), \(\mathrm{h_{2}}=\mathrm{g^{b}}\), \(\mathrm{h_{3}}=\mathrm{g^{c}}\), pseudo-random functions f: \(\{0\),\(1\}^{k}\times Z_{\mathrm{p}}^{*}\)\(\rightarrow\)\(Z_{\mathrm{p}}^{*}\) and random parameters \(\mathrm{t}\in\{0\),\(1\}^{k}\). Select hash function H(x):\(\{0\),\(1\}^{*}\)\(\rightarrow\)\(Z_{\mathrm{p}}^{*}\) and calculate \(\mathrm{h}=\mathrm{h_{1}}=\mathrm{g^{a}}\), and params = (G,g,p,f,h,H) is used as the public parameter. * Query before challenge: Attacker A asks challenger C for ciphertext index of keywords list \(\mathrm{W_{i}}=\{\mathrm{w^{\prime}_{1}},\mathrm{w^{\prime}_{2}},\cdots, \mathrm{w^{\prime}_{m}}\}\). Challenger C sends \(\mathrm{W_{i}}\) to A after encryption. For the encryption, challenger C randomly selects \(\mathrm{r}\in Z_{\mathrm{p}}^{*}\), calculates \(\mathrm{g^{r}}\) and \(\mathrm{h^{r}}\), \(\forall\)\(\mathrm{w^{\prime}_{j}}\in\mathrm{W_{i}}\), \(1\leq\mathrm{j}\leq\mathrm{m}\), calculates \(\mathrm{g^{\prime}_{j}}=\mathrm{f[t,H(w^{\prime}_{j})]}\), \(\mathrm{E}(\mathrm{w^{\prime}_{j}})=\left(\mathrm{h}\cdot\mathrm{g^{f^{f}_{j} }}\right)^{r}\), outputs \(\mathrm{I}=\left(\mathrm{g^{r}}\mathrm{,h^{r}}\mathrm{,E}(\mathrm{w^{\prime}_{ 1}})\mathrm{,E}(\mathrm{w^{\prime}_{2}})\right)\), \(\ldots\)\(\mathrm{E}(\mathrm{w^{\prime}_{m}})\right)\) and sends I to A. * Challenge: Attacker A randomly selects two keywords \(\mathrm{w^{\prime}_{0}}\) and \(\mathrm{w^{\prime}_{1}}\) that have not been inquired by challenger C and sends them to C. Challenger C randomly selects \(\mathrm{t^{\prime}}\in\{0\),\(1\}\), calculates \(\mathrm{\delta^{\prime}_{t^{\prime}}}=\mathrm{f[t,H(w_{t^{\prime}})]}\), randomly selects \(\mathrm{r^{\prime}}\in Z_{\mathrm{p}}^{*}\), calculates \(\mathrm{E}(\mathrm{w^{\prime}_{t^{\prime}}})=\left(\mathrm{h_{3}}\cdot\mathrm{ h_{2}^{\mathrm{w^{\prime}_{t^{\prime}}}}}\right)^{r^{\prime}}\), outputs the encrypted index \(\mathrm{I_{t^{\prime}}}=\left(\mathrm{h_{2}^{r}},\mathrm{h_{3}^{r}},\mathrm{E} (\mathrm{w^{\prime}_{t^{\prime}}})\right)\) of \(\mathrm{w^{\prime}_{t^{\prime}}}\) and returns it to A. * Query after challenge: Challenger C can adaptively choose the ciphertext index of query keywords for attacker A, but cannot query the ciphertext index of keywords \(\mathrm{w^{\prime}_{0}}\) and \(\mathrm{w^{\prime}_{1}}\) and the number of queries takes polynomial times of k.
* Output: Attacker A outputs conjecture \(\mathrm{b_{A}}\in\{0\),\(1\}\) on B in ciphertext index \(\mathrm{I_{b}}\). If \(\mathrm{b_{A}}=\mathrm{b}\), i.e., the A is said to have guessed the correct answer and won the game, [PERSON] answers \(\mathrm{c}=\mathrm{ab}\) in DDHP challenge; otherwise, if [PERSON] failed, [PERSON] answers \(\mathrm{c}\
eq\mathrm{ab}\). If \(\mathrm{c}=\mathrm{ab}\), the ciphertext index \(\mathrm{I_{t^{\prime}}}=\left(\mathrm{h_{2}^{r^{\prime}}},\mathrm{h_{3}^{r^{ \prime}}},\left(\mathrm{h_{3}}\cdot\mathrm{h_{2}^{\mathrm{s^{\prime}_{t^{\prime} }}}}\right)^{r^{\prime}}\right)=\left(\mathrm{g^{br^{\prime}}}\mathrm{,h^{br^{ \prime}}}\left(\mathrm{h}\cdot\mathrm{g^{\mathrm{s^{\prime}_{t^{\prime}}}}} \right)^{\mathrm{br^{\prime}}}\right)\) of keywords \(\mathrm{w^{\prime}_{t^{\prime}}}\) is a correct keyword ciphertext, here \(\mathrm{h}=\mathrm{h_{1}}=\mathrm{g^{a}}\), \(\mathrm{h_{3}}=\mathrm{gc}=\mathrm{hb}\). If \(\mathrm{c}\
eq\mathrm{ab}\), \(\mathrm{I_{t^{\prime}}}\) must be the ciphertext of the correct keywords list, so there will be \(\mathrm{c}=\mathrm{ab}\). If \(\mathrm{c}\
eq\mathrm{ab}\), [PERSON] does not have a chance to win the game.