# Practical Inner Product Encryption with Constant Private Key +
## 4 Security Analysis of the Proposed Scheme  
We now provide the security proof for theoselective security of the proposed IPE scheme. In the subsequent proof, we view a vector as a row vector. Theorem 4.1: _The proposed scheme is csIND-CPA secure for q private key queries, where q is a polynomial in the security parameter \(\lambda\), under the M-DDH\({}_{\mathbb{GT}}\) assumption._  
Proof: Given \((P,A^{\prime}=aP,g_{T},A=g_{T}^{a},B=g_{T}^{b},C)\), we build an algorithm \(\mathcal{C}\) using the adversary \(\mathcal{A}\) to solve the M-DDH\({}_{\mathbb{GT}}\) problem as follows. * **Init. ** The adversary \(\mathcal{A}\) commits \(q\) predicate vectors \(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)}\). * **Setup. **\(\mathcal{C}\) first finds a vector \(\mathbf{u}=(u_{1},u_{2},\ldots,u_{\ell})\) such that \[\left[ \begin{array}{c}\mathbf{y}_{1}\\ \mathbf{y}_{2}\\ \vdots\\ \mathbf{y}_{q}\end{array} \right]\mathbf{u}^{\top}=\mathbf{0}_{\ell}^{\top},\] where \(\mathbf{0}_{\ell}=\underbrace{(0,0,\ldots,0)}_{\ell}\). Such \(\mathbf{u}\) exists when \(q>\ell\). The operation is to find a vector \(\mathbf{u}\) such that \(\langle\mathbf{u},\mathbf{y}_{j}\rangle=0\) for \(j=1\) to \(q\). \(\mathcal{C}\) then chooses \(\mathbf{v}=(v_{1},v_{2},\ldots,v_{\ell})\stackrel{{\$}}{{ \leftarrow}}\mathbb{Z}_{p}^{\ell}\). Next, \(\mathcal{C}\) computes \(\widehat{\mathbf{h}}=(B^{u_{i}}\cdot g_{T}^{v_{i}})_{i=1}^{\ell}=(\widehat{h} _{1},\ldots,\widehat{h}_{\ell})\). Finally, \(\mathcal{C}\) sets params \(=(P,g_{T},\widehat{\mathbf{h}})\) and sends params to \(\mathcal{A}\). Note that \(\mathcal{C}\) implicitly sets \(\texttt{msk}=\mathbf{s}=(s_{i}=u_{i}\cdot b+v_{i})_{i=1}^{\ell}\).
* **Query Phase 1**. After receiving \(\mathbf{y}^{(i)}=(y_{1}^{(i)},\ldots,y_{\ell}^{(i)})\) from \(\mathcal{A}\), where \(i\in[1,2,\ldots,q]\), \(\mathcal{C}\) first chooses \(k\stackrel{{\$}}{{\leftarrow}}\mathbb{Z}_{p}\) and then computes \(K_{\mathbf{y}^{(i)}}=(k_{0},K_{1})=(kP,\langle\mathbf{v},\mathbf{y}^{(i)} \rangle+k\mod p)\). The correctness of the private key \(K_{\mathbf{y}^{(i)}}\) is demonstrated as follows. \[\mathbb{K}_{1}\] \[= \langle\mathbf{s},\mathbf{y}^{(i)}\rangle+k\mod p\] \[= \sum_{j=1}^{\ell}s_{j}y_{j}^{(i)}+k\mod p\] \[= \sum_{j=1}^{\ell}(u_{j}\cdot b+v_{j})\cdot y_{j}^{(i)}+k\mod p\] \[= b\sum_{j=1}^{\ell}u_{j}y_{j}^{(i)}+\sum_{j=1}^{\ell}v_{j}y_{j}^{ (i)}+k\mod p\] \[= b\langle\mathbf{u},\mathbf{y}^{(i)}\rangle+\langle\mathbf{v}, \mathbf{y}^{(i)}\rangle+k\mod p\] \[= \langle\mathbf{v},\mathbf{y}^{(i)}\rangle+k\mod p.\]
* **Challenge**. Upon receiving \(\mathbf{x}^{*}\), where \(\langle\mathbf{x}^{*},\mathbf{y}^{(i)}\rangle\
eq 0\) for \(i=1,\ldots,q\), and two equal-length messages \(M_{0}\), \(M_{1}\) from \(\mathcal{A}\), the challenger \(\mathcal{C}\) performs the following. 1. Choose \(\beta\in\{0,1\}\). 2. Choose \(\delta\stackrel{{\$}}{{\leftarrow}}\mathbb{Z}_{p}\). 3. Set \(\mathcal{C}_{0}^{\prime}=A^{\prime}\) and \(\widehat{\mathcal{C}}_{0}^{\prime}=A\). 4. For \(i=1\) to \(\ell\), compute \(\mathcal{C}_{i}^{\prime}=(C^{u_{i}}\cdot A^{v_{i}}\cdot g_{T}^{\delta x_{i}^{*}}) \cdot M_{\beta}\). 5. Set the challenge ciphertext \(\mathcal{C}^{*}=(\mathcal{C}_{0}^{\prime},\widehat{\mathcal{C}}_{0}^{\prime}, \mathcal{C}_{1}^{\prime},\mathcal{C}_{2}^{\prime},\ldots,\mathcal{C}_{\ell}^{ \prime})\). 6. Return \(\mathcal{C}^{*}\) to \(\mathcal{A}\). Here, we implicitly set the randomness of the encryption procedure to \(a\). Therefore, if \(C=g_{T}^{ab}\), then we have \(\mathcal{C}_{0}^{\prime}=aP,\widehat{\mathcal{C}}_{0}^{\prime}=g_{T}^{a}\) for \(i=1,\ldots,\ell\),  
\[ \begin{array}{ll}\mathcal{C}_{i}^{\prime}&=(C^{u_{i}}\cdot A^{v_{i}}\cdot g_{ T}^{\delta x_{i}^{*}})\cdot M_{\beta}\\ &=(g_{T}^{alu_{i}}\cdot g_{T}^{\alpha_{i}}\cdot S_{T}^{\delta x_{i}^{*}})\cdot M _{\beta}\\ &=(g_{T}^{\alpha(bu_{i}+v_{i})})\cdot(g_{T}^{\delta x_{i}^{*}})\cdot M_{\beta} \\ &=h_{i}^{a}\cdot g_{T}^{\delta x_{i}^{*}}\cdot M_{\beta}.\end{array} \]  
Thus, the challenge ciphertext \(\mathcal{C}^{*}\) is a valid ciphertext. * **Query Phase 2.