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

Participates in

Builds on Group signature

Produces Group signature