# PriSign, A Privacy-Preserving Single Sign-On System for Cloud Environments
## 5 Construction of PriSign
### New Results and Building Blocks
#### 5.2.3 Threshold Inner-Product Functional Encryption  
Threshold inner-product functional encryption (TIPFE) is inspired by Inner-product functional encryption (IPFE) [35]. First, we realize the threshold key extraction algorithm using the linear feature of IPFE's key extraction algorithm. Of course, this modification sacrifices its traceability, which is unnecessary in this application. Second, we use the transformation in [36] to convert the predicate-only scheme into a full-fledged predicate encryption scheme.  
* \(-\mathsf{TIPFE}.\mathsf{Setup}(\mathcal{BL},n,t,k)\rightarrow(pk,sk)\): This algorithm is operated by a central authority to generate public parameters and a master key pair for the system.
* Set \(pp=(\mathcal{BL},n,t,k)\)
* Randomly choose \(sk=(s_{1},s_{2},\cdots,s_{k},e)\stackrel{{ R}}{{\leftarrow}} \mathbb{Z}_{p}^{*}\)
* Compute \(G=e(g,\widetilde{g})\), \(P=G^{\epsilon}\) and \(H_{i}=G^{\epsilon_{i}}\), \(i\in[1,k]\), and set \(pk=(G,P,H_{1},H_{2},\cdots,\)\(H_{k})\)
* \(-\mathsf{TIPFE}.\mathsf{IsKey}(pk,sk,n,t)\rightarrow(\{sk_{i},pk_{i}\}_{i=1}^{n}):\) This algorithm is operated by the central authority to issue shared keys for \(n\) policymakers, where \(t\) policymakers cooperate to recover the master key.
* Choose \(k+1\) polynomials of degree \(t-1\) with coefficients in \(\mathbb{Z}_{p}^{*}\), denoted as \(f_{1},f_{2}\), \(\cdots,f_{k},f_{e}\), and set \(f_{1}(0)=s_{1},f_{2}(0)=s_{2},\cdots,f_{k}(0)=s_{k},f_{e}(0)=e\)
* Compute \(s_{i,j}=f_{j}(i)\) and \(e_{i}=f_{e}(i)\) where \(i\in[1,n],j\in[1,k]\), and set \(sk_{i}=(s_{i,1},s_{i,2},\cdots,s_{i,k},e_{i})\)
* Compute \(P_{i}=G^{\epsilon_{i}}\), \(H_{i,j}=G^{s_{i,j}}\) where \(i\in[1,n],j\in[1,k]\), and set \(pk_{i}=(G,P_{i},H_{i,1},H_{i,2},\)\(\cdots,H_{i,k})\)
* \(-\mathsf{TIPFE}.\mathsf{Extract}(sk_{i},id,\widetilde{v})\to dk_{id, \overline{g},i}\): This algorithm is operated by a policymaker \(i\) to issue a share of a policy key for a receiver with identity \(id\) and a characteristic vector \(\widetilde{v}\).
* Set \(\widetilde{s_{i}}=(s_{i,1},s_{i,2},\cdots s_{i,k})\) and compute \(\theta_{id}=\mathsf{HASH}(id)\)
* Compute \(dk_{id,\overline{g},i}=\widetilde{g}^{<s_{i},\overline{g}>+\epsilon\theta_{id} }=\widetilde{g}^{\sum_{j=1}^{t}s_{i}\widetilde{g}^{\gamma_{j}}+\epsilon\theta_{id}}\)
* \(-\mathsf{TIPFE}.\mathsf{KeyAgg}(id,\widetilde{v},\{dk_{id,\overline{g},i},pk_{ i}\}_{i\in[1,t]})\rightarrowdk_{id,\overline{g}}\): This algorithm is operated by a receiver to aggregate \(t\) received shares of policy keys into a compact policy key.
* For each \(i\in[1,t]\), check \(e(g,dk_{id,\overline{g},i})=P_{i}^{\alpha}\prod_{j=1}^{t}R_{i,j}^{p_{i}}\)
* For each \(i\in[1,t]\), compute \(\lambda_{i}=[\prod_{j\in[1,t],j\
eq i}(j)[\prod_{j\in[t],j\
eq i}(j-i)]^{-1}\)* Compute \(dk_{id,\vec{u}}=\prod_{i\in[1,t]}dk_{id,\vec{g},i}^{\lambda_{i}}\)  
\(-\) TIPFE.Enc\((pp,pk,\vec{u},M)\to CT\). This algorithm is operated by a sender to encrypt a message \(M\) with an attribute vector \(\vec{u}\).
* Randomly choose \(r\xleftarrow{R}\Z_{p}^{*}\), then compute \(C_{0}=M\cdot P^{r}\)
* Compute \(C_{1}=g^{r},C_{2}=(H_{1}^{r}G^{u_{1}},H_{2}^{r}G^{u_{2}},\cdots,H_{1}^{r}G^{u_ {k}})\)
* Set \(CT=(C_{0},C_{1},C_{2})\)  
\(-\) TIPFE.Dec\((pp,id,tk_{id,\vec{u}},CT)\to M\): This algorithm is operated by a receiver to decrypt the ciphertext using a policy key.
* If \(<\vec{u},\vec{v}>=0\), compute \(M=C_{0}\cdot(\frac{\prod_{i=1}^{k}c_{2,i}^{v_{i}}}{e(C_{1},k_{id,\vec{g}})}) \theta_{id}^{-1}\)  
**Theorem 1**.: _Our TIPFE scheme satisfies attribute-hiding under the BDDH assumption._  
The correctness analysis and formal proof of our TIPFE scheme are provided in Supplemental Material D. In this paper, we use the TIPFE scheme to achieve token-hiding and proxy re-verification.