# PriSign, A Privacy-Preserving Single Sign-On System for Cloud Environments
## 5 Construction of PriSign
### New Results and Building Blocks  
#### 5.2.1 Attribute-Based Credentials with Traceability  
We construct an attribute-based credential with traceability (ABCT) scheme from the anonymous credential scheme in [34]. Compared with the original scheme [34], our ABCT scheme is improved in three aspects: (1) we enable users to generate public and private key pairs independently and obtain credentials of attributes set and the public key without disclosing their private keys; (2) we extend the feature to support malicious user identity tracing while protecting user privacy; and (3) we modify the credential presentation algorithm (Show) to support efficient selective disclosure, which is essential to support fine-grained access control. * \(\mathsf{ABCT.Setup}(1^{\lambda},q)\to pp\): On input of a security parameter \(1^{\lambda}\) and a positive integer \(q\), this algorithm generates a bilinear group \(\mathcal{BL}=(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},e,p,g,\widetilde{g})\) and sets \(pp=(\mathcal{BL},q)\), where \(q\) is the attribute number for user. * \(\mathsf{ABCT.CredKeyGen}(pp)\to(isk,ipk,\mathcal{L})\): This algorithm is operated by an issuer to generate their public private key pair. The issuer chooses \((x,y_{0},\cdots,y_{q})\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{p}^{*}\) and computes \(\widetilde{X}=\widetilde{g}^{x}\) and \(\widetilde{Y}_{i}=\widetilde{g}^{y_{i}}\) for \(i\in[0,q]\). Then, it initializes a user registration list \(\mathcal{L}=\mathcal{O}\) and outputs a private key \(isk=(x,y_{0},\cdots,y_{q})\) and public key \(ipk=(\widetilde{X},\widetilde{Y}_{0},\cdots,\widetilde{Y}_{q})\). * \(\mathsf{ABCT.UserKeyGen}(pp)\to(usk,upk,utk)\): This algorithm is operated by a user to generate their public private key pair. The user chooses a private key \(usk\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{p}^{*}\), then computes their public key \(upk=g^{usk}\) and tracing key \(utk=\widetilde{g}^{usk}\). * \(\langle\mathsf{ABCT.Issue.U}(uid,usk,upk,utk,\{m_{j}\}_{j=1}^{q})\leftrightarrow \mathsf{ABCT.Issue.I}(isk,ipk,\mathcal{L})\rangle\to(ucred,\mathcal{L}^{ \prime})\): This algorithm operates by interacting between a user and an issuer to create an attribute-based credential for the user. * \(\mathsf{ABCT.PreCred}(uid,usk,upk,utk,\{m_{j}\}_{j\in[1,\mathcal{A}]})\to(uid, \{m_{j}\}_{j=1}^{q},\Pi_{1})\): The user computes a ZKSoK \(\Pi_{1}=\mathsf{ZKSoK}\{usk:upk=g^{usk}\wedge utk=\widetilde{g}^{usk}\}\), then sends their identity \(uid\), attribute set \(\{m_{j}\}_{j=1}^{q}\), and \(\Pi_{1}\) to the issuer. Figure 7: Building blocks and roadmap [33; 34; 35; 36; 38]. * ABCT.SigCed\((isk,ipk,uid,\{m_{j}\}_{j\in[1,a]},\Pi_{1})\to\textit{ucred}\): After \(\Pi_{1}\) is verified, the issuer chooses \(r\xleftarrow{R}\mathbb{Z}_{p}^{*}\) and computes \(\sigma_{1}=g^{\prime}\), \(\sigma_{2}=(upk)^{r\cdot y_{0}}g^{r\cdot(x+\sum_{j-1}^{d}m_{j}y_{j})}\). Then, it sets \(\mathcal{L}^{\prime}=\mathcal{L}\cup(uid,uk)\) and returns \(ucred=(\sigma_{1},\sigma_{2})\). * ABCT.VyCred\((usk,\{m_{j}\}_{j\in[1,a]},\textit{ucred})\to\textit{ucred}\): The user accepts the credential \(ucred\) if \(e(\sigma_{2},\widetilde{g})=e(\sigma_{1},\widetilde{X}\widetilde{Y}_{0}^{ \textit{ask}}\,\Pi_{j=1}^{q}\,\widetilde{Y}_{j}^{m_{j}})\) holds. * ABCT.Show\((usk,upk,ucred,\{m_{j}\}_{j=1}^{q},\mathcal{D},\mathsf{CTX})\to\textit{tok}\): This algorithm is operated by a user to anonymously present a credential while disclosing a subset of attributes \(\{m_{j}\}_{j\in\mathcal{D}}\), where \(\mathcal{D}\subset[1,q]\).