# PriSign, A Privacy-Preserving Single Sign-On System for Cloud Environments
## 3 Preliminaries
### Structure-Preserving Signatures  
[PERSON]'s structure-preserving signatures (SPS) [33] consist of the following probability polynomial-time (PPT) algorithms:  
* \(\mathsf{SPS.Setup}(1^{\lambda},l)\to pp\): On input a security parameter \(1^{\lambda}\) and a positive integer \(l\), this algorithm generates a bilinear group \(\mathcal{BL}=(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},e,p,g,\widetilde{g})\) and outputs public parameters \(pp=(\mathcal{BL},l)\).
* \(\mathsf{SPS.KeyGen}(pp)\to(sk,pk)\): On input public parameters \(pp\), this algorithm selects \((\alpha_{0},\alpha_{1},\ldots,\alpha_{l-1})\stackrel{{\text{ \tiny$\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{ \mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{ \mathsf{ \mathsf{     }}}}}}}}}}}}}}{Z} \mathcal{\mathsf{P}}}\) and a generator \(\gamma\stackrel{{\text{\tiny$\mathsf{\mathsf{\mathsf{\mathsf{ \mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{ \mathsf{ \mathsf{ \mathsf{ \mathsf{      \mathsf{ \mathsf{       }}}}}}}}}}}}} {Z}Z_{\mathsf{p}}}\), then computes \(\beta_{i}=g^{\alpha_{i}},0\leqslant i\leqslant l-1\). It outputs a secret key \(sk=(\alpha_{0},\alpha_{1},\ldots,\alpha_{l-1})\) and a public key \(pk=(\gamma,\{\beta_{i}\}_{i=0}^{l-1})\).
* \(\mathsf{SPS.Sign}(sk,\{m_{i}\}_{i=1}^{l})\to\delta\): To sign \(l\) messages \(m_{1},\ldots,m_{l}\) (\(m_{i}\in\mathbb{G}_{2},1\leqslant i\leqslant l\)), the signer selects \(r\stackrel{{\text{\tiny$\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{ \mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{\mathsf{ \mathsf{ \mathsf{ \mathsf{ }}}}}}}}}}}}}}}{( \mathsf{}\mathsf{}\mathsf{S}}_{p}\)), computes \(\delta_{1}=g^{r-1}\); \(\widetilde{\delta}_{2}=(\gamma\cdot\widetilde{g}^{\alpha_{0}})^{\gamma}\) and \(\widetilde{\delta}_{3}=(\gamma^{\alpha_{0}}m_{l}\cdot\prod_{i=1}^{l-1}m_{i}^{ \alpha_{i}})^{r}\), then outputs the signature \(\delta=(\delta_{1},\widetilde{\delta}_{2},\widetilde{\delta}_{3})\).
* \(\mathsf{SPS.Verify}(pk,\delta,\{m_{i}\}_{i=1}^{l})\to 0/1\): To verify the signature \(\delta=(\delta_{1},\widetilde{\delta}_{2},\widetilde{\delta}_{3})\) on messages \(\{m_{i}\}_{i=1}^{l}\), this algorithm checks two pairing equations, \(e(\delta_{1},\widetilde{\delta}_{2})=e(g,\gamma,e)(\beta_{0},\widetilde{g})\) and \(e(\delta_{1},\widetilde{\delta}_{3})=e(\beta_{0},\gamma)e(g,m_{l})\prod_{i=1}^ {l-1}e(\beta_{i},m_{i})\). If both equations are satisfied, it outputs \(1\); otherwise, it outputs \(0\).  
[PERSON]'s SPS scheme [33] is existentially unforgeable under chosen message attacks (EUF-CMA). In this paper, we use this signature scheme to create credentials for the public key of the ticket issuer.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Abbreviation** & **Description** \\ \hline CA & Central Authority \\ l & Issuer \\ P & Policymaker \\ U & User \\ V & Verifier \\ SDL & Symmetric Discrete Logarithm \\ DDH & Decisional Diffie-Hellman \\ BDDH & Bilinear Decisional Diffie-Hellman \\ PS & Pointcheval–Sanders \\ SPS & Structure-Preserving Signatures \\ EUF-CMA & Existentially Unforgeable under Chosen Message Attacks \\ ZKSoK & Zero-Knowledge Signature of Knowledge \\ ABCT & Attribute-Based Credential with Traceability \\ ABCB & Attribute-Based Credential with Blindness \\ IPFE & Inner-Product Functional Encryption \\ TIPFE & Threshold Inner-Product Functional Encryption \\ \hline \hline \end{tabular}
\end{table}
Table 2: Nomenclature.