# Decentralized Inner-Product Encryption with Constant-Size Ciphertext
## 4 Security Proof
KeyExtract oracle: Upon receiving a vector \(\vec{X}=(x_{1},x_{2},\ldots,x_{\ell})\) and a global identity \(GID\) from \(\mathcal{A}\), where \(\langle\vec{X},\vec{Y}^{*}\rangle\
eq 0\) (As shown in Definition 3, \(\mathcal{A}\) is not allowed to make a KeyExtract query with \(\langle\vec{X},\vec{Y}^{*}\rangle=0\), otherwise \(\mathcal{A}\) can break the security trivially.) \(\mathcal{C}\) performs as follows. For \(i=1,\ldots,n-1\), \(sk_{i}\) can be easily computed using the algorithm \(\mathbf{KeyGen_{A_{i}}}(pp,MSK_{i},GID,\vec{X})\) shown in Section 3 since \(\mathcal{C}\) knows \(MSK_{i}\). As for \(sk_{n}\), it can be computed from the instance of the \(\ell\)-DBDHE problem by the following steps:  
1. Query \(V_{k}=H(GID,\vec{X})\) and set \(D_{0}=V_{k}\). Let \(D_{0}=g^{t}\), where \[t=\frac{x_{1}\gamma^{\ell}+x_{2}\gamma^{\ell-1}+\ldots+x_{\ell}\gamma}{ \langle\vec{X},\vec{Y}^{*}\rangle}+v_{k}.\] Note that \(v_{k}\) can be found in the \(H\)-list;
2. For \(j=2,\ldots,\ell\), compute \[K_{j,n}=H(GID,\vec{X})^{-\alpha_{1,n}\frac{x_{j}}{\tau_{1}}}\cdot H(GID,\vec {X})^{\alpha_{j,n}}=(g^{-\alpha_{1,n}\frac{x_{j}}{\tau_{1}}}g^{\alpha_{j,n}})^ {t}.\] One can note that, in the exponent of \(K_{j,n}\), \[(-\alpha_{1,n}\frac{x_{j}}{x_{1}}+\alpha_{j,n})t=(-\gamma\frac{x_{j}}{x_{1}} +\gamma^{j})\cdot(\frac{x_{1}\gamma^{\ell}+x_{2}\gamma^{\ell-1}+\ldots+x_{ \ell}\gamma}{\langle\vec{X},\vec{Y}^{*}\rangle}+v_{k}),\] the only unknown term is \(\gamma^{\ell+1}\). However, the coefficient of \(\gamma^{\ell+1}\) is \[-\frac{x_{j}}{x_{1}}\cdot\frac{x_{1}}{\langle\vec{X},\vec{Y}^{*}\rangle}+ \frac{x_{j}}{\langle\vec{X},\vec{Y}^{*}\rangle}=0,j=2,\ldots,\ell.\] Thus, \(K_{j,n}\) can be easily computed using the knowledge of \(\vec{X},\vec{Y}^{*}\) and the instance \((g,g^{\intercal},g^{\intercal^{2}},\ldots,g^{\intercal^{\prime}},g^{\intercal ^{\prime+2}},\ldots,g^{\intercal^{2\prime}})\) of the \(\ell\)-DBDHE problem;
3. Compute \[D_{1,n}=g^{\mathbb{R}_{n}}\cdot H(GID,\vec{X})^{\alpha_{0,n}}=g^{\mathbb{R}_{n }+\alpha_{0,n}t}.\] One can note that the exponent of \(D_{1,n}\) is \[ \begin{array}{l}\overline{\alpha}_{n}+\alpha_{0,n}t\\ =\gamma^{\ell+1}+(-\langle\overline{\alpha}_{n},\vec{Y}^{*}\rangle+\delta)\cdot \ t\\ =\gamma^{\ell+1}+(-\langle\overline{\alpha}_{n},\vec{Y}^{*}\rangle)\cdot(\frac{ x_{1}\gamma^{\ell}+x_{2}\gamma^{\ell-1}+\ldots+x_{\ell}\gamma}{\langle\vec{X},\vec{Y}^{*} \rangle}+v_{k})+\delta\ t\\ =\gamma^{\ell+1}-\frac{(\alpha_{1}y_{1}^{*}+\alpha_{2}y_{2}^{*}+\ldots+\alpha_ {\ell}y_{\ell}^{*})(x_{1}\gamma^{\ell}+x_{2}\gamma^{\ell-1}+\ldots+x_{\ell} \gamma)}{\langle\vec{X},\vec{Y}^{*}\rangle}-\langle\overline{\alpha}_{n},\vec {Y}^{*}\rangle\cdot v_{k}+\delta\ t\\ =\gamma^{\ell+1}-\frac{(\gamma y_{1}^{*}+\gamma^{2}y_{2}^{*}+\ldots+\gamma^{ \ell}y_{\ell}^{*})(x_{1}\gamma^{\ell}+x_{2}\gamma^{\ell-1}+\ldots+x_{\ell} \gamma)}{\langle\vec{X},\vec{Y}^{*}\rangle}-\langle\overline{\alpha}_{n},\vec {Y}^{*}\rangle\cdot v_{k}+\delta t\\ \end{array} \]  
Again, the coefficient of the unknown term \(\gamma^{\ell+1}\) is  
\[1-\frac{x_{1}y_{1}^{*}+x_{2}y_{2}^{*}+\ldots+x_{\ell}y_{\ell}^{*}}{\langle \vec{X},\vec{Y}^{*}\rangle}=1-\frac{\langle\vec{X},\vec{Y}^{*}\rangle}{\langle \vec{X},\vec{Y}^{*}\rangle}=0.\]  
Therefore, \(D_{1,n}\) can be also computed using the knowledge of \(\vec{X},\vec{Y}^{*}\) and the instance \((g,g^{\gamma},g^{\gamma^{2}},\ldots,g^{\gamma^{\ell}},g^{\gamma^{\ell+2}}, \ldots,g^{\gamma^{2\ell}})\) of the \(\ell\)-DBDHE problem. **Challenge. **  
\(\mathcal{A}\) submits two message \(M_{0}\) and \(M_{1}\) of the same length, and \(\mathcal{C}\) computes the challenge ciphertext as follows:  
1. Choose \(\beta\xleftarrow{\$}\{0,1\}\);
2. Set \(E_{2}=g^{s}\);
3.