1 Introduction
1.1 Application scenario
-
A user creates a single secret key on a secure token (e.g., smart card).
-
The user registers to a given domain only once using his secure token and might derive a unique public key, called pseudonym, in each domain he registers in.
-
Using the secure token, the user may personalize his mobile devices.
-
Having a personalized device, the user may authenticate himself to each domain to which he has registered a pseudonym. Moreover,
-
in case the user registers to a new domain, no device needs to be updated in order to authenticate to the new domain, and
-
adding a new devices does not require updating any public key information in any service nor any other device.
-
-
Finally, we also require that a user must be able to revoke each of his devices in case of theft, key leakage, etc.
1.2 Privacy and unlinkability issues
1.3 Previous attempts to replace passwords
1.4 Group signatures
1.5 Ad hoc solution based on group signatures
-
the user can delegate his rights to authenticate on behalf of him to any number of his devices—indeed, the number of group members is typically unlimited,
-
the devices are indistinguishable from the point of view of the verifier—this is the basic feature of group signatures,
-
in case of a misbehavior, the user may open a signature and find which device has created it.
1.6 Contribution and paper overview
2 Preliminaries
2.1 Bilinear groups
-
bilinear: for \(a, b \in \mathbb {Z}_p\), we have \(e(g_1^a, g_2^b) = e(g_1, g_2)^{a \cdot b}\),
-
non-degenerate: the element \(e(g_1, g_2) \in \mathbb {G}_T\) is a generator of \(\mathbb {G}_T\).
2.2 Forking lemma
2.3 Security assumptions
3 Formal model of Pseudonymous Public Key Group Signature
-
Setup\((1^{\lambda })\): On input a security parameter \(\lambda \), it outputs global parameters param.
-
CreateUser(param): On input the global parameters param, it creates and outputs the user’s master secret key mSK.
-
ComputePseudonym\((param, mSK, \mathtt {dom})\): On input the global parameters param, the master secret key mSK and a domain name \(\mathtt {dom}\), it returns a pseudonym nym within domain \(\mathtt {dom}\) for the user holding mSK.
-
AddDevice(param, mSK, i): On input the global parameters param, the master secret key mSK and a device identifier i, this procedure returns a device secret key \(uSK_i\).
-
CreateRevocationToken\((param, mSK, \mathtt {dom}, i,j)\): On input the global parameters param, user index i and his secret key mSK, the domain name \(\mathtt {dom}\) and a device identifier j, this procedure computes and outputs a device revocation token \(uRT_{i,j,\mathtt {dom}}\) within the domain \(\mathtt {dom}\).
-
Sign\((param, uSK, \mathtt {dom}, m)\): On input the global parameters param, a device secret key uSK, a domain name \(\mathtt {dom}\) and a message m, it returns a signature \(\sigma \) on the message m.
-
Verify\((param, nym, \mathtt {dom}, \sigma , m, uRT)\): On input the global parameters param, a pseudonym nym with regard to a domain name \(\mathtt {dom}\), a signature \(\sigma \) on a message m, and a revocation token uRT, this algorithm returns 1 (accept), or 0 (reject).
-
\((i^*,\cdot ) \not \in \mathcal {U}_{SET}\) or \(j_0^* = j_1^*\), or
-
\((i^*, j_0^*,\cdot ) \not \in \mathcal {D}_{SET}\) or \((i^*, j_1^*,\cdot ) \not \in \mathcal {D}_{SET}\), or
-
\((i^*, j_0^*) \in \mathcal {C}\mathcal {D}\) or \((i^*, j_1^*) \in \mathcal {C}\mathcal {D}\), or
-
the \(\mathcal {O}_{\textsf {GetRT}}\) oracle was called on input \((i^*, j_0^*, \mathtt {dom}^*)\) or \((i^*, j_1^*, \mathtt {dom}^*)\),
4 Efficient construction
4.1 Scheme specification
-
Setup\((1^{\lambda })\):1.Choose groups \(\mathbb {G}_1\), \(\mathbb {G}_2\) of a prime order p, a bilinear map \(e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T\), and choose a generator \(g_1 {\mathop {\leftarrow }\limits ^{\mathcal {R}}}\mathbb {G}_1\) at random.2.Define a hash function \(\mathsf {H}_0\) which maps into \(\mathbb {G}_2\) and a hash function \(\mathsf {H}\) which maps into \(\mathbb {Z}_p\).3.Output the global parameters param\(=\) (p, \(\mathbb {G}_1\), \(\mathbb {G}_2\), e, \(g_1\), \(\mathsf {H}_0\), \(\mathsf {H})\).
-
\(\textsf {CreateUser}(param)\):1.Choose \(z \in \mathbb {Z}_p\) at random and output \(mSK \leftarrow z\).
-
ComputePseudonym\((param, mSK, \mathtt {dom})\):1.Compute \(\hat{g_2} \leftarrow \mathsf {H}_0(\mathtt {dom})\) and output \(nym \leftarrow \hat{g_2}^z\).
-
AddDevice(param, mSK, i):2.Compute \(A_i = g_1^{1/(u_i + z)}\), return \(uSK[i] \leftarrow (A_i, u_i)\) and store \(u_i\) for future use.
-
CreateRevocationToken\((param, mSK, \mathtt {dom}, i)\):1.Retrieve the user secret key \(u_i\), compute \(\hat{g_2} \leftarrow \mathsf {H}_0(\mathtt {dom})\) and return \(uRT \leftarrow \hat{g_2}^{u_i}\).
-
Sign\((param, uSK, \mathtt {dom}, m)\):1.Compute \(\hat{g_2} \leftarrow \mathsf {H}_0(\mathtt {dom})\).2.Choose \((r_1, r_2) \in \mathbb {Z}_p^2\) at random and compute \(R_1 \leftarrow A_i^{r_1}\), \(R_2 \leftarrow g_1^{r_2}\) and \(R_3 \leftarrow e(R_2, \hat{g_2})^{u_i}\).3.Compute the following signature of knowledge:$$\begin{aligned} S \leftarrow SoK\{(\alpha , \beta , \gamma ): R_1 = g_1^{\beta /(z + \alpha )} \wedge \\ R_2 = g_1^{\gamma } \wedge R_3 = e(g_1, \hat{g_2})^{\alpha \cdot \gamma }\}(m) \end{aligned}$$(a)Choose \(t_1, t_2, t_3 \in \mathbb {Z}_p\) at random and compute$$\begin{aligned}&T_1 \leftarrow e\left( A_i, \hat{g_2}\right) ^{-t_1 \cdot r_1} \cdot e\left( g_1, \hat{g_2}\right) ^{t_2}, \\&T_2 \leftarrow g_1^{t_3} \text { and } \\&T_3 \leftarrow e\left( R_2, \hat{g_2}\right) ^{t_1}. \end{aligned}$$(b)Compute the challenge c\(=\)\(\mathsf {H}(param\), m, \(\mathsf {dom}\), \(T_1\), \(T_2\), \(T_3)\).(c)Compute \(s_1 \leftarrow t_1 + c \cdot u_i\), \(s_2 \leftarrow t_2 + c\cdot r_1\) and \(s_3 \leftarrow t_3 + c\cdot r_2\).(d)Set \(S = (c, s_1, s_2, s_3)\)4.Output the signature \(\sigma = (S, R_1, R_2, R_3)\).
-
Verify\((param, nym, \mathtt {dom}, \sigma , m, uRT)\):1.Compute \(\hat{g_2} \leftarrow \mathsf {H}_0(\mathtt {dom})\).2.Parse the signature as \(\sigma = (S, R_1, R_2, R_3)\), where \(S = (c, s_1, s_2, s_3)\).3.Restore the values$$\begin{aligned} \begin{aligned} \tilde{T_1}&= e\left( R_1, nym\right) ^{-c} \cdot e\left( R_1, \hat{g_2}\right) ^{-s_1} \cdot e\left( g_1, \hat{g_2}\right) ^{s_2} \\ \tilde{T_2}&= g_1^{s_3} \cdot R_2^{-c} \\ \tilde{T_3}&= e\left( R_2, \hat{g_2}\right) ^{s_1} \cdot R_3^{-c} \end{aligned} \end{aligned}$$4.If \(c \not =\mathsf {H}(param, m, \mathsf {dom}, \tilde{T_1}, \tilde{T_2}, \tilde{T_3})\), then return 0 (reject).5.If \(e(R_2, uRT) = R_3\), then return 0 (reject).6.Return 1 (accept).
Scheme |
\(\mathbb {G}_1\)
|
\(\mathbb {G}_2\)
|
\(\mathbb {G}_T\)
|
\(\mathbb {Z}_q\)
| Bit size |
---|---|---|---|---|---|
Our | 2 | 0 | 1 | 4 | 4608 |
[9] | 2 | – | – | 5 | 1792 |
[6] | 3 | – | – | 2 | 1280 |
[26] | 3 | – | 1 | 8 | 5888 |
Scheme | Exp. | Mul. | Pairing |
\(\psi : \mathbb {G}_2 \rightarrow \mathbb {G}_1\)
|
\(M_p\)
| Impl. (ms) |
---|---|---|---|---|---|---|
Our |
\(3 \cdot \mathbb {G}_1 + 4 \cdot \mathbb {G}_T\)
|
\(1 \cdot \mathbb {G}_T\)
| – | – | 45,276 | 176 |
[9] |
\(6 \cdot \mathbb {G}_1 + 2 \cdot \mathbb {G}_2\)
|
\(2 \cdot \mathbb {G}_1 + 1 \cdot \mathbb {G}_2 + 1 \cdot \mathbb {G}_T\)
| 2 | 2 | 62,385 | 482 |
[6] |
\(3 \cdot \mathbb {G}_1 + 1 \cdot \mathbb {G}_T\)
| – | – | – | 35,970 | 165 |
[26] |
\(13 \cdot \mathbb {G}_1 + 4 \cdot \mathbb {G}_T\)
|
\(6 \cdot \mathbb {G}_1 + 2 \cdot \mathbb {G}_T\)
| 1 | – | 89,062 | 477 |
Scheme | Exp. | Mul. | Pairing |
\(\psi : \mathbb {G}_2 \rightarrow \mathbb {G}_1\)
|
\(M_p\)
| Impl. (ms) |
---|---|---|---|---|---|---|
Our |
\(6 \cdot \mathbb {G}_1 + 1 \cdot \mathbb {G}_T\)
|
\(2 \cdot \mathbb {G}_1 + 2 \cdot \mathbb {G}_T\)
| 3 | – | 74,818 | 457 |
[9] |
\(6 \cdot \mathbb {G}_1 + 2 \cdot \mathbb {G}_2 + 1 \cdot \mathbb {G}_T\)
|
\(2 \cdot \mathbb {G}_1 + 3 \cdot \mathbb {G}_T\)
| 3 | 2 | 88,052 | 552 |
[6] |
\(3 \cdot \mathbb {G}_1\)
|
\(1 \cdot \mathbb {G}_1 + 1 \cdot \mathbb {G}_T\)
| 4 | – | 73,623 | 442 |
[26] |
\(12 \cdot \mathbb {G}_1 + 2 \cdot \mathbb {G}_2 + 3 \cdot \mathbb {G}_T\)
|
\(7 \cdot \mathbb {G}_1 + 2 \cdot \mathbb {G}_2 + 4 \cdot \mathbb {G}_T\)
| 2 | – | 106,815 | 667 |
4.2 Notes on the construction
4.2.1 Efficiency and optimizations
4.2.2 Implementation
4.2.3 Additional procedures and scheme variants
5 Security analysis
5.1 Unforgeability
-
Hash Queries: In case the adversary queries the \(\mathsf {H}\) hash oracle, \(\mathsf {B}\) responds with a random value and saves the response for a future call. In case the adversary queries the \(\mathsf {H}_0\) hash oracle on input \(\mathtt {dom}\), the solver chooses \(r {\mathop {\leftarrow }\limits ^{\mathcal {R}}}\mathbb {Z}_p\) at random, programs the oracle to return \(g_2^{r}\) and saves the pair \((r, \mathtt {dom})\) for a future call.
-
\(\mathcal {O}_{\textsf {CreateUser}}\): The adversary requests to create the ith user. The solver runs \(mSK_i\)\(\leftarrow \)CreateUser(param) as in the protocol description and adds the pair \((i, mSK_i)\) to \(\mathcal {U}_{SET}\).
-
\(\mathcal {O}_{\textsf {GetNym}}\): The adversary requests the pseudonym of the ith user with regard to domain \(\mathtt {dom}\). The solver runs \(nym_{i, \mathtt {dom}}\)\(\leftarrow \)ComputePseudonym(param, \(\mathtt {dom}\), \(mSK_i)\) and returns \(nym_{i, \mathtt {dom}}\).
-
\(\mathcal {O}_{\textsf {AddDevice}}\): The adversary requests to add a device j by the ith user. If \(i \ne i'\), then \(\mathsf {B}\) runs \(uSK_{i, j}\)\(\leftarrow \)AddDevice(param, mSK, j) as in the original protocol. If \(i = i'\), then \(\mathsf {B}\) acts as follows:Finally, the solver adds the tuple \((i, j, uSK_{i, j})\) to \(\mathcal {D}_{SET}\).
-
if \(j \ne j'\), then \(\mathsf {B}\) runs \(uSK_{i', j}\)\(\leftarrow \)AddDevice(param, mSK, j) as in the original protocol.
-
if \(j = j'\), then \(\mathsf {B}\) sets \(uSK_{i', j'} \leftarrow \perp \) (the solver will later simulate the signatures for this device).
-
-
\(\mathcal {O}_{\textsf {GetRT}}\): The adversary requests the domain revocation token of the ith user, jth device with regard to domain \(\mathtt {dom}\). If \(i = i'\) and \(j = j'\), then the solver restores the pair \((r, \mathtt {dom})\) from the \(\mathsf {H}_0\) hash oracle, computes \(uRT \leftarrow \varLambda ^{r}\), and outputs uRT. Otherwise, the solver computes uRT\(\leftarrow \)CreateRevocationToken(param, mSK, \(\mathtt {dom}\), i) as in the protocol description and returns uRT.
-
\(\mathcal {O}_{\textsf {Sign}}\): The adversary requests a signature for the ith user, jth device within domain \(\mathtt {dom}\) and message m. If \(i = i'\) and \(j = j'\), then \(\mathsf {B}\) simulates the signature of knowledge. Otherwise, the solver computes \(\sigma \)\(\leftarrow \)Sign(param, \(uSK_{i, j}\), \(\mathtt {dom}\), m) as in the protocol description. Finally, the solver outputs \(\sigma \).
-
\(\mathcal {O}_{\textsf {CorruptDevice}}\): The adversary requests a secret key of the ith group manager and jth user. If \(i = i'\) and \(j = j'\), then the solver aborts. Otherwise, \(\mathsf {B}\) returns \(uSK_{i, j}\).
5.2 Seclusiveness
5.3 Anonymity
5.4 Domain unlinkability
6 The \(\varSigma \)-protocol
-
Common Input: The common input to the Prover and Verifier CV consists of groups \(\mathbb {G}_1\) and \(\mathbb {G}_2\) of prime order p, group generators \(g_1 \in \mathbb {G}_1\) and \(\hat{g_2} \in \mathbb {G}_2\), and a bilinear map \(e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T\). Furthermore, there is an element \(Z \in \mathbb {G}_2\).
-
Private Input: The private input of the Prover consists of a pair \((A, u) \in \mathbb {G}_1 \times \mathbb {Z}_p\), such that \(e(A, \hat{g_2}^{u} \cdot Z) = e(g_1, \hat{g_2})\).
-
The protocol:1.(Prover) The Prover chooses \((r_1, r_2) {\mathop {\leftarrow }\limits ^{\mathcal {R}}}\mathbb {Z}_p^2\) at random and computes \(R_1 \leftarrow A^{r_1}\), \(R_2 \leftarrow g_1^{r_2}\) and \(R_3 \leftarrow e(R_2, \hat{g_2})^u\).2.(Prover \(\rightarrow \) Verifier) The Prover and Verifier execute the following proof of knowledge:$$\begin{aligned} PoK\Big \{\left( \alpha , \beta , \gamma \right) : R_1&= g_1^{\beta /\left( z + \alpha \right) } \wedge R_2 = g_1^{\gamma } \wedge \\ R_3&= e\left( g_1, \hat{g_2}\right) ^{\alpha \cdot \gamma } \Big \} \end{aligned}$$(a)The Prover chooses \((t_1, t_2, t_3) {\mathop {\leftarrow }\limits ^{\mathcal {R}}}\mathbb {Z}_p^3\) and computesThen the Prover sends \(R_1\), \(R_2\), \(R_3\), \(T_1\), \(T_2\) and \(T_3\) to the Verifier.$$\begin{aligned}&T_1 \leftarrow e\left( A, \hat{g_2}\right) ^{-t_1 \cdot r_1} \cdot e\left( g_1, \hat{g_2}\right) ^{t_2} \text { , } \\&T_2 \leftarrow g_1^{t_3} \text { and } \\&T_3 \leftarrow e\left( R_2, \hat{g_2}\right) ^{t_1}~~. \end{aligned}$$(b)(Verifier \(\rightarrow \) Prover) The Verifier chooses \(c {\mathop {\leftarrow }\limits ^{\mathcal {R}}}\mathbb {Z}_p\) and sends c to the Prover.(c)(Prover \(\rightarrow \) Verifier) The Prover now computes \(s_1 \leftarrow t_1 + c \cdot u\), \(s_2 \leftarrow t_2 + c\cdot r_1\) and \(s_3 \leftarrow t_3 + c\cdot r_2\).3.(Verifier) The Verifier accepts if the following equations hold:$$\begin{aligned}&T_1 = e\left( R_1, Z\right) ^{-c} \cdot e\left( R_1, \hat{g_2}\right) ^{-s_1} \cdot e\left( g_1, \hat{g_2}\right) ^{s_2} \\&T_2 = g_1^{s_3} \cdot R_2^{-c} \\&T_3 = e\left( R_2, \hat{g_2}\right) ^{s_1} \cdot R_3^{-c} \end{aligned}$$