# PriSign, A Privacy-Preserving Single Sign-On System for Cloud Environments
## 4 System and Security Model
### Formal Definition  
The notation used in the scheme is summarized in Table 3. The PriSign scheme consists of the following PPT algorithms:  
* \(\mathsf{PriSign.Setup}(1^{\lambda},q,n,t,k)\rightarrow(pp,msk,mpk,\mathcal{L})\): This algorithm is operated by CA, which inputs a security parameter \(1^{\lambda}\), a number of user attributes \(q\), a number of policymakers \(n\) and threshold value \(t\), and a policy length \(k\), then outputs the system parameters \(pp\), a main key pair \((msk,mpk)\), and a user registration list \(\mathcal{L}\), where \(pp\) contains a matching function \(\mathcal{F}\) over the set of attribute vectors \(\Sigma\) and the set of policies \(\Delta\). To simplify the description, the remaining algorithms take \(pp\) as the input by default. * \(\mathsf{PriSign.IssuerKeyGen}()\rightarrow(isk,ipk)\): This algorithm is operated by the ticket issuer and outputs a secret key \(isk\) and public key \(ipk\). * \(\mathsf{PriSign.IssuerReg}(\{(isk,ipk)\leftrightarrow\mathsf{CA}(msk,mpk)\} \to icred/\bot\): This algorithm operates by interacting between I and CA to issue a public key credential for I. I takes \((isk,ipk)\) as inputs, while CA takes \(msk\) and \(mpk\) as inputs. It returns either a credential \(icred\) for I if the execution of the algorithm succeeds, or \(\bot\) if the execution fails. * \(\mathsf{PriSign.PolMakKeyGen}(msk,mpk)\rightarrow(\{psk_{i},pvk_{i}\}_{i\in[1,n]})\): This algorithm is operated by CA to issue keys for \(n\) policymakers. It inputs \(msk\), \(mpk\), and outputs a private key \(psk_{i}\) and a verification key \(pvk_{i}\) for each \(\mathrm{P}_{i}\), where \(i\in[1,n]\). Note that \(t\) policymakers can cooperate to recover the complete key used to generate policy keys for verifiers. * \(\mathsf{PriSign.IsPolKey}(psk_{i},vid,\vec{v})\to tk_{vid,\vec{v},i}\). This algorithm is operated by a policymaker \(\mathrm{P}_{i}\) with index \(i\) to generate a share of a policy key for a verifier with identity \(vid\) and policy \(\vec{v}\). It inputs \(psk_{i}\), a verifier's identity \(vid\), and a policy \(\vec{v}\), and outputs a share of policy key \(tk_{vid,\vec{v},i}\). * \(\mathsf{PriSign.AggrPolKey}(vid,\vec{v},\{tk_{vid,\vec{v},i},pvk_{i}\}_{i\in[1, t]})\to tk_{vid,\vec{v}}\). This algorithm is operated by V, which receives \(t\) shares of the policy key from I policymakers and aggregates them into a complete policy key. It inputs \(vid\), \(\vec{v}\), \(t\) shares of policy key \(\{tk_{vid,\vec{v},i}\}_{i\in[1,t]}\), and \(\{pvk_{i}\}_{i\in[1,t]}\), then outputs a complete policy key \(tk_{vid,\vec{v}}\). * \(\mathsf{PriSign.UserKeyGen}()\rightarrow(usk,\mu pk,utk)\): This algorithm is operated by U and outputs a private key \(usk\), a public key \(upk\), and a tracing key \(utk\). * \(\mathsf{PriSign.UserReg}(\mathsf{U}(uid,usk,upk,utk,\{m_{j}\}_{j\in[1,q]}) \leftrightarrow\mathsf{CA}(msk,mpk,\mathcal{L}))\rightarrow(ucred,\mathcal{L} ^{\prime})\) /\(\bot\): This algorithm is operated by interacting between U and CA to issue an attribute-based credential for U. U takes the identity \(uid\), \(usk\), \(upk\), \(utk\) and set of attributes \(\{m_{j}\}_{j\in[1,q]}\) as inputs, while CA takes \(msk\), \(mpk\), and \(\mathcal{L}\) as inputs. It returns either a credential \(ucred\) for U and updated user registration list \(\mathcal{L}^{\prime}\) if the execution of the algorithm succeeds, or \(\bot\) if the execution fails. * \(\mathsf{PriSign.OptTkt}\{\mathsf{U}(usk,upk,ucred,\{m_{j}\}_{j\in[1,q]}, \mathcal{D},\mathsf{CTX})\leftrightarrow\mathsf{I}(isk,ipk,icred)\} \rightarrow(pst,ktkt,dsid,VP)/\bot\): This algorithm operates by interacting between U and I to issue a ticket for U. U takes \(usk\), \(upk\), \(ucred\), \(\{m_{j}\}_{j\in[1,q]}\), an attribute disclosure policy \(\mathcal{D}\) (\(\mathcal{D}\subseteq[1,q]\)), and a context CTX as inputs, while I takes \(isk\), \(ipk\), and \(icred\) as inputs.