# Practical Inner Product Encryption with Constant Private Key +
## 2 Preliminaries
### Bilinear Maps  
Let \(\mathbb{G}\) and \(\mathbb{G}_{T}\) be an additive and a multiplicative cyclic group, respectively; here, the order of \(\mathbb{G}\) and \(\mathbb{G}_{T}\) is a large prime \(p\) (i.e., \(|\mathbb{G}|=|\mathbb{G}_{T}|=p\)). Then, let \(P\) be a generator of \(\mathbb{G}\). A bilinear map (pairing) \(e:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_{T}\) is a mapping with the following properties:  
* Bilinearity: For \(a,b\in\mathbb{Z}_{p}\), \(e(aP,bP)=e(P,P)^{ab}\). * Nondegeneracy: \(\exists P\in\mathbb{G}\), such that \(e(P,P)\
eq 1_{\mathbb{G}_{T}}\). * Computability: The mapping \(e\) is efficiently computable. In this work, we take advantage of the generalized decisional Diffie-Hellman exponent (GDDHE) problem, based on [34]. The GDDHE problem is a generic framework within which new complexity assumptions can be created. We first give an overview of the GDDHE problem. Let  
* \(p\) be a prime;
* \(s,n\) be two positive integers;
* \(P,Q\in\mathbb{F}_{p}[X_{1},\ldots,X_{n}]^{s}\) be two \(s\)-tuple of \(n\)-variate polynomials over \(\mathbb{F}_{p}\); and
* \(f\) be an \(n\)-variate polynomial in \(\mathbb{F}_{p}[X_{1},\ldots,X_{n}]\). \(Q,Q_{T}\) are two ordered sets with multivariate polynomials, and thus, we define \(Q=(q_{1},q_{2},\ldots,q_{s})\) and \(R=(r_{1},r_{2},\ldots,r_{s})\). As stated in [34], we require \(p_{1}=q_{1}=1\) to be two constant polynomials. Consider a bilinear map \(e:\mathbb{G}\times\mathbb{G}\to\mathbb{G}_{T}\) with the generator \(P\) of \(\mathbb{G}\) and \(g_{T}=e(P,P)\in\mathbb{G}_{T}\). For a vector \((x_{1},x_{2},\ldots,x_{n})\in\mathbb{F}_{p}^{n}\), we define  
\[Q(x_{1},x_{2},\ldots,x_{n})P=(q_{1}(x_{1},x_{2},\ldots,x_{n})P,\ldots,q_{s}(x_ {1},x_{2},\ldots,x_{n})P)\in\mathbb{G}^{s},\]  
and  
\[g_{T}^{R(x_{1},x_{2},\ldots,x_{n})}=(g_{T}^{r_{1}(x_{1},x_{2},\ldots,x_{n})}, \ldots,g_{T}^{r_{s}(x_{1},x_{2},\ldots,x_{n})})\in\mathbb{G}_{T}^{s}.\]  
By \"\(f\) depends on \((Q,R)\)\" we mean that there are \(s^{2}+s\) constants \(\{a_{i,j}\}_{i,j=1}^{s}\) and \(\{b_{k}\}_{k=1}^{s}\) such that  
\[f=\sum_{i,j=1}^{s}a_{i,j}q_{i}q_{j}+\sum_{k=1}^{s}b_{k}r_{k}.\]  
We say that \(f\) is independent of \((Q,R)\) if \(f\) does not depend on \((Q,R)\). **Definition 1** (The \((Q,R,f)\)-GDDHE Problem). : _Given \((Q(x_{1},\ldots,x_{n})P,g_{T}^{R(x_{1},\ldots,x_{n})},Z)\in\mathbb{G}^{s} \times\mathbb{G}_{T}^{s}\times\mathbb{G}_{T}\), decide if \(Z\stackrel{{? }}{{=}}g_{T}^{f(x_{1},\ldots,x_{n})}\)._  
Then, for an algorithm \(\mathcal{A}\), the advantage of \(\mathcal{A}\) in solving the \((Q,R,f)\)-GDDHE problem is defined as  
\[Adv^{(Q,R,f)\text{-GDDHE}}(\mathcal{A})=\left|\mathcal{A}\left(Q(x_{1},\ldots, x_{n})P,g_{T}^{R(x_{1},\ldots,x_{n})},g_{T}^{f(x_{1},\ldots,x_{n})}\right)- \mathcal{A}\left(Q(x_{1},\ldots,x_{n})P,g_{T}^{R(x_{1},\ldots,x_{n})},Z \stackrel{{\xi}}{{=}}\mathbb{G}_{T}\right).\]  
[PERSON] et al. propose that the \((Q,R,f)\)-GDDHE problem is difficult if \(f\) is independent of \((Q,R)\) and demonstrate that a large class of hard problems can be fit into the framework of the GDDHE problem; for instance, the DDH problem over \(\mathbb{G}_{T}\). **Definition 2** (The decisional Diffie-Hellman problem over \(\mathbb{G}_{T}\) (DDH\({}_{\mathbb{G}_{T}}\) problem)). : _Let \(g_{T}=e(P,P)\) be a generator of \(\mathbb{G}_{T}\). Given \((P,g_{T},A=g_{T}^{a},B=g_{T}^{b},C)\in\mathbb{G}\times\mathbb{G}_{T}^{4}\), where \(a,b\stackrel{{\xi}}{{=}}\mathbb{Z}_{p}\), decide whether \(C=g_{T}^{ab}\) or an random element from \(\mathbb{G}_{T}\)._  
By setting \(Q=(1),R=(1,a,b),f=ab\), the DDH problem over \(\mathbb{G}_{T}\) is equivalent to the \((Q,R,f)\)-GDDHE problem. Observe that no constants exist such that the linear combination of \(1,a,b\) equals \(ab\); therefore, \(f\) is independent of \((Q,R)\). Given the result of [PERSON] et al., we conclude that no algorithm is available with which to solve the DDH\({}_{\mathbb{G}_{T}}\) problem with a nonnegligible advantage. See [34] for additional details.