# Efficient Conjunctive Keywords Search over Encrypted E-Mail Data in Public Key Setting
## 4 Proposed Spe-Cks Scheme
### Security Proof
Moreover, \(\mathbb{C}\) constructs \(l_{ik}=-\frac{(h_{1}^{k}+h_{2}^{y}+\ldots+h_{im}^{k})\rho_{i}}{\sum_{p=0}^{n} b_{p}(h_{1}^{y}+h_{2}^{y}+\ldots+h_{im}^{y})}\) which is satisfied with the equality \(\frac{h_{1}^{k}+h_{2}^{y}+\ldots+h_{im}^{k}}{u_{i}\eta x+\sum_{p=0}^{n}(s_{p} x-h_{p})(h_{1}^{y}+h_{2}^{y}+\ldots+h_{im}^{y})}=\frac{l_{ik}}{x+\rho_{i}}\) for each \(k\in[0,n]\). Obviously, \((U^{\frac{l_{1}}{x+\rho_{i}}},U^{\frac{l_{2}}{x+\rho_{i}}},\ldots,U^{\frac{l_ {2}}{x+\rho_{i}}},U^{\frac{l_{i}}{x+\rho_{i}}})\) is a trapdoor for keyword query \(Q_{i}\). 3. Through searching the S-list to obtain the tuple \(\{\rho_{i}g^{f_{i}(x)}\}\), \(\mathbb{C}\) sends \((g^{f_{i}(x)l_{0}},g^{f_{i}(x)l_{1}},\ldots,g^{f_{i}(x)l_{in}},g^{f_{i}(x)l_{i}})\) to \(\mathbb{A}\) as the correct trapdoor for the query \(Q_{i}\). 4. **Challenge**: Algorithm \(\mathbb{A}\) produces a target keyword set \(W^{*}\) which it wants to challenge on and sends \(W^{*}\) to \(\mathbb{C}\). Algorithm \(\mathbb{C}\) chooses a random keyword set \(R\) and sets \(W_{0}=W^{*}=\{w_{01},w_{02},\ldots,w_{0n}\}\), \(W_{1}=R=\{w_{11},w_{12},\ldots,w_{1n}\}\). The only restriction is that the trapdoor queried in previous phase can not distinguish \(W_{0}\) from \(W_{1}\). Let \((w_{0i},h_{0i},\sigma_{0i})\) be the corresponding tuples on the \(H_{1}-\)list, for each \(i\in[1,n]\), if \(\sigma_{0i}>n\), then \(\mathbb{C}\) reports failure and terminates. After that, \(\mathbb{C}\) selects a random bit \(\beta\in\{0,1\}\) and runs the above algorithm for responding to \(H_{1}-\)queries to obtain the values \(h_{\beta 1},h_{\beta 2},\ldots,h_{\beta n}\) where \(H_{1}(w_{\beta i}|\phi)=h_{\beta i},w_{\beta i}\in W_{\beta},i\in[1,n]\). Then, \(\mathbb{C}\) generates the challenge SPE-CKS index \(l_{\beta}\) as follows: 1. \(\mathbb{C}\) constructs \(f(z)=\prod_{i=1}^{m}(z-h_{\beta i})=\sum_{j=0}^{n}a_{j}z^{j}\). Then \(\mathbb{C}\) computes \(C_{\beta j}=X_{j}^{\frac{f_{i}}{x}}\times U^{\frac{f_{i}}{x}a_{j}}=U^{s_{j} \rho_{i}-b_{j}^{\frac{f_{i}}{x}}+a_{j}\frac{f_{j}}{x}}=U^{s_{j}\rho_{i}}\) for each \(j\in[0,n]\) and \(C_{W_{\beta}}=Z^{\frac{f_{\beta}}{x}}=V^{\frac{f_{\beta}}{x}}=U^{r_{\beta}}\). Let \(D_{W_{\beta}}=H_{2}(R_{U}^{r_{\beta}})\), observe that if \(R=\hat{e}(g,g)^{\frac{1}{x}}\), then \(R_{U}=\hat{e}(U,U)^{\frac{1}{x}}\). This means that \((C_{\beta 0},C_{\beta 1},\ldots,C_{\beta n},C_{W_{\beta}},D_{W_{\beta}})\) is a valid SPE-CKS index of keyword set \(W_{\beta}\) when \(R=\hat{e}(g,g)^{\frac{1}{x}}\). 2. \(\mathbb{C}\) sends \(I_{\beta}=(C_{\beta 0},C_{\beta 1},\ldots,C_{\beta n},C_{W_{\beta}},D_{W_{\beta}})\) and two keyword sets \(W_{0}\) and \(W_{1}\) to \(\mathbb{A}\). 3. **More queries**: \(\mathbb{A}\) continues to issue index and trapdoor queries. The only restriction is that no index and trapdoor query can distinguish \(W_{0}\) from \(W_{1}\). 4. **Response**: \(\mathbb{A}\) outputs a guess \(\beta^{{}^{\prime}}\in\{0,1\}\). If \(\beta^{{}^{\prime}}=\beta\), then \(\mathbb{C}\) outputs \(1\) which means \(R=\hat{e}(g,g)^{\frac{1}{x}}\). Otherwise, \(\mathbb{C}\) outputs \(0\) which means \(R\) is a random number where \(R\in G_{2}^{*}\). We analyze the probability that \(\mathbb{C}\) does not abort in _trapdoor queries_ phase and _challenge_ phase. We define three events:  
\(\omega_{1}\): \(\mathbb{C}\) does not abort in index queries phase for generating the \(I_{W}\). \(\omega_{2}\): \(\mathbb{C}\) does not abort as a result of any of \(\mathbb{A}\)'s trapdoor queries. \(\omega_{3}\): \(\mathbb{C}\) does not abort in challenge phase for generating the \(I_{\beta}\). If \(q_{I}\) is sufficiently large, then the probability of event \(\omega_{1}\) is at least \((1-\frac{1}{q_{I}})^{\mathit{n}q_{I}}=\frac{1}{\hat{e}^{2}}\). Suppose that \(q_{T}\) is sufficiently large. Therefore, the probability of event \(\omega_{2}\) is at least \((1-\frac{1}{q_{T}})^{\mathit{m}q_{T}}=\frac{1}{\hat{e}^{2}}\). The probability of event \(\omega_{3}=\frac{1}{\hat{q}_{T}^{2}}\).