Group signature
A group signature scheme lets each member of a group sign on behalf of the group: a signature verifies under one group public key and hides which member produced it, while a group manager holding an opening key can identify the signer — CvH91.
Syntax
In the static model of BMW03, a group signature scheme is a tuple of efficient algorithms , which BMW03 call , with respect to message space :
- , a randomized algorithm that outputs, for a group of members, a group public key , the group manager’s opening key , and a vector of signing keys, being the key of member ,
- , a randomized algorithm that outputs a signature on ,
- , a deterministic algorithm outputting a bit ,
- , a deterministic algorithm outputting a member or .
The group is fixed at key generation, which a trusted party runs, giving to member and to the group manager — BMW03.
Properties
Correctness
A group signature scheme is perfectly correct if for all , all output by , all and , every satisfies and — BMW03.
Full anonymity
The adversary receives the group public key and every member’s signing key, and has an opening oracle throughout. It names two members and a message , receives a signature on by member , and must guess — BMW03. It may not have opened, since the answer is .
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{anon}}_{\Pi,\calA}(\secpar, n)$}
\begin{algorithmic}
\State $(\mathsf{gpk}, \mathsf{gmsk}, \mathsf{gsk}) \gets \KeyGen(1^\secpar, 1^n)$; $b \getsr \bits$; $(m^*, \sigma^*) \gets (\bot, \bot)$
\State $(i_0, i_1, m^*, \stA) \gets \calA^{\calO}(1^\secpar, \mathsf{gpk}, \mathsf{gsk})$
\Comment{$i_0, i_1 \in [n]$}
\State $\sigma^* \gets \Sign(\mathsf{gsk}[i_b], m^*)$
\State $b' \gets \calA^{\calO}(\stA, \sigma^*)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO(m, \sigma)$}
\begin{algorithmic}
\If{$(m, \sigma) = (m^*, \sigma^*)$}
\Comment{the challenge may not be opened}
\Return $\bot$
\EndIf
\Return $\Open(\mathsf{gmsk}, m, \sigma)$
\end{algorithmic}
\end{algorithm}
A group signature scheme is fully anonymous if for every polynomial and all efficient ,
is negligible.
Full traceability
The adversary receives the group public key and the opening key, corrupts members of its choice adaptively, learning their signing keys, and has a signing oracle for every member. It wins with a valid signature that opens to , or to a member that it did not corrupt and never asked to sign — BMW03. A signature by a corrupted member, or one the signing oracle returned, is a trivial win, which the condition excludes.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{trace}}_{\Pi,\calA}(\secpar, n)$}
\begin{algorithmic}
\State $(\mathsf{gpk}, \mathsf{gmsk}, \mathsf{gsk}) \gets \KeyGen(1^\secpar, 1^n)$; $C \gets \{\}$; $\calQ \gets \{\}$
\State $(m^*, \sigma^*) \gets \calA^{\calO_{\mathrm{Corr}}, \calO_{\Sign}}(1^\secpar, \mathsf{gpk}, \mathsf{gmsk})$
\If{$\Vrfy(\mathsf{gpk}, m^*, \sigma^*) = 0$}
\Return $0$
\EndIf
\State $i \gets \Open(\mathsf{gmsk}, m^*, \sigma^*)$
\Return $[i = \bot \lor (i \notin C \land (i, m^*) \notin \calQ)]$
\Comment{$i$ not corrupted; $(i, m^*)$ not queried to $\calO_{\Sign}$}
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{Corr}}(i)$}
\begin{algorithmic}
\State $C \gets C \cup \{i\}$
\Return $\mathsf{gsk}[i]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\Sign}(i, m)$}
\begin{algorithmic}
\State $\calQ \gets \calQ \cup \{(i, m)\}$
\Return $\Sign(\mathsf{gsk}[i], m)$
\end{algorithmic}
\end{algorithm}
A group signature scheme is fully traceable if for every polynomial and all efficient ,
is negligible.
Full anonymity and full traceability together imply the informal requirements proposed for group signatures before them, among them unlinkability, exculpability and coalition resistance — BMW03. As an object, group signatures denote perfectly correct schemes that are fully anonymous and fully traceable.
Variations
CPA-full anonymity
Full anonymity without the opening oracle: in the adversary gets no access to , and still receives every member’s signing key — BBS04. The opening oracle plays the role of the decryption oracle of IND-CCA security, whence the name. As an object, CPA-anonymous group signatures denote perfectly correct schemes that are CPA-fully anonymous and fully traceable.
Dynamic groups
In the dynamic model, members join at any time through an interactive protocol with an issuer, a role separated from that of the opener, and security consists of anonymity, traceability and non-frameability — BSZ05.
Other results
- Fully anonymous and fully traceable group signatures exist if doubly enhanced, certified trapdoor permutations do (Doubly enhanced certified TDP ⇒ Group signatures) — BMW03, GR13. BMW03 state the construction from trapdoor permutations; the NIZK proofs for that it uses are known from doubly enhanced, certified ones (Doubly enhanced certified TDP ⇒ NIZK) — FLS90, GR13.
- In bilinear groups, -SDH and DLIN give CPA-anonymous group signatures in the random-oracle model whose signatures are about the size of an RSA signature at the same security level (Bilinear pairing + q-SDH + DLIN ⇒ CPA-anonymous group signatures) — BBS04.
- Group signatures imply public-key encryption (Group signatures ⇒ PKE) — AW04.
Participates in
Builds on Group signature
Produces Group signature