# Efficient Conjunctive Keywords Search over Encrypted E-Mail Data in Public Key Setting
## 4 Proposed Spe-Cks Scheme
### Security Proof  
In this subsection, we will give a rigorous proof to show the security of the proposed scheme. The essential of the proof is that we will show the difficulty of breaking our scheme is the same as that of solving the assumption of \((q_{T}+1)\)-BDHI, according to the security game described in Section 3.2. The concrete proof is given as follows. **Theorem 1**. : _The scheme of SPE-CKS is secure according to IND-CR-CKA game if the decision \((q_{T}+1)\)-BDHI assumption is hard._  
**Proof. ** Suppose that an algorithm \(\mathbb{A}\) has advantage \(\epsilon\) in breaking the SPE-CKS under the security game IND-CR-CKA. Suppose that \(\mathbb{A}\) makes at most \(q_{H_{2}}\) hash function queries to \(H_{2}\), at most \(q_{I}\) secure index queries and at most \(q_{T}\) trapdoor queries, we can build an algorithm \(\mathbb{C}\) that solves the decision \((q_{T}+1)\)-BDHI assumption with probability at least \(\epsilon^{{}^{\prime}}=\frac{\epsilon}{\hat{e}^{\varepsilon^{{}^{\prime}}+n}q_{T }^{\varepsilon^{{}^{\prime}}}}\), where \(e\) is base of natural logarithm, \(n\) and \(m\) are the number of keywords contained in an index and a trapdoor, respectively. Algorithm \(\mathbb{C}\)'s running time is approximately the same as \(\mathbb{A}\)'s. Let \(g\) be a generator of \(G_{1}\), given \(g,g^{x},g^{x^{2}},\ldots,g^{x^{\ell_{T}+1}}\) and \(R\), the goal of algorithm \(\mathbb{C}\) is to output \(1\) if \(R=\hat{e}(g,g)^{\frac{1}{x}}\) and \(0\) otherwise. Algorithm \(\mathbb{C}\) simulating the challenger interacts with algorithm \(\mathbb{A}\) simulating attacker as follows:  
**- Setup**: Algorithm \(\mathbb{C}\) works as follows:  
1. Algorithm \(\mathbb{C}\) randomly chooses \(q_{T}\) random numbers \(\rho_{1},\rho_{2},\ldots,\rho_{q_{T}}\in Z_{q}^{*}\) and computes \(f(z)=\prod_{i=1}^{q_{T}}(z+\rho_{i})=\sum_{j=0}^{q_{T}}c_{j}z^{j}\). 2. \(\mathbb{C}\) computes \(U=g^{f(x)}=g^{\sum_{j=0}^{t_{T}}c_{j}x^{j}}\) and \(V=g^{x/(x)}=g^{\sum_{j=0}^{t_{T}}c_{j}x^{j+1}}\). Since \(f_{i}(z)=\frac{1}{z+\rho_{j}}f(z)=\sum_{j=0}^{t_{T}-1}d_{j}z^{j}\), \(\mathbb{C}\) gets \(U^{\frac{1}{z+\rho_{i}}}=g^{f_{i}(x)}=g^{\sum_{j=0}^{t_{T}-1}d_{j}x^{j}}\) where \(i\in[1,q_{T}]\). Then \(\mathbb{C}\) stores the pairs \(\{\rho_{i},g^{f_{i}(x)}\}\) in a list named \(S\)-list where \(i\in[1,q_{T}]\). 3. \(\mathbb{C}\) computes \(\frac{f(z)-c_{0}}{z}=\sum_{j=1}^{q_{T}}c_{j}z^{j-1}\) and sets \(R_{U}=\hat{e}(g^{\sum_{j=1}^{q_{T}}c_{j}x^{j-1}},g^{\sum_{j=0}^{t_{T}}c_{j}x^{ j+c_{0}}})\times K^{c_{0}^{2}}\). Obviously, if \(R=\hat{e}(g,g)^{\frac{1}{z}}\), then it has \(R_{U}=\hat{e}(g^{\sum_{j=1}^{q_{T}}c_{j}x^{j-1}},g^{\sum_{j=0}^{t_{T}}c_{j}x^{ j+c_{0}}})\times K^{c_{0}^{2}}=\hat{e}(g^{\frac{f(x)-c_{0}}{x}},g^{f(x)+c_{0}}) \times\hat{e}(g,g)^{\frac{2}{z}}=\hat{e}(g,g)^{\frac{f(x)-c_{0}^{2}}{x}}\times \hat{e}(g,g)^{\frac{c_{0}^{2}}{x}}=\hat{e}(g,g)^{\frac{f(x)}{x}}=\hat{e}(g,g)^{ \frac{f(x)}{x}}=\hat{e}(U,U)^{\frac{1}{z}}\). 4. \(\mathbb{C}\) randomly chooses \(2n+3\) numbers \(s_{0},s_{1},\ldots,s_{n},t_{1},\ldots,t_{n},\eta\in Z_{q}^{*}\) and computes \(f(z)=\prod_{i=1}^{n}(z-t_{i})=\sum_{j=0}^{n}b_{j}z^{j}\). Let \(Z=V^{\eta}\), \(\mathbb{C}\) constructs \(X_{j}=V^{\eta_{j}}-U^{b_{j}}\) for each \(j\in[0,n]\). \(\mathbb{C}\) randomly chooses a \(g_{0}\in G\) and a number \(t\in Z_{q}^{*}\) and then computes \(T=g_{0}^{t}\). After that, \(\mathbb{C}\) gives the public key \(pk_{R}=\{X_{0},X_{1},\ldots,X_{n},Z,\mu=\hat{e}(U,U),g_{0},T\}\) to \(\mathbb{A}\). The corresponding private key \(sk_{R}\) unknown to \(\mathbb{C}\) is \(\{s_{0}x-b_{0},s_{1}x-b_{1},\ldots,s_{n}x-b_{n},\eta x,t\}\). 5. \(\mathbb{C}\) randomly chooses a number \(s\in Z_{q}^{*}\) and sets \(S=S_{0}^{*}\). \(\mathbb{C}\) generates a hash function \(H_{3}:G\to\{0,1\}^{*}\). After that, \(\mathbb{C}\) outputs \(pk_{S}=\{S,H_{3}\}\) and keeps \(sk_{S}=\{s\}\) secret. 6. \(H_{1},H_{2}-\)**queries**: Algorithm \(\mathbb{A}\) can query the random oracles \(H_{1}\) or \(H_{2}\) at any time.