A Group Signature Scheme \(\system\) is the tuple of algorithms \((\keygen, \sign, \verify, \open)\) where:

• \(\keygen(1^\lambda, n) \to (gpk, gmsk, gsk_1, ..., gsk_n)\): On input security parameter \(1^\lambda\) and group size \(n\), outputs a group public key \(gpk\), the group manager's secret key \(gmsk\), and a group secret signing keys for each group member.
• \(\sign(gsk_i, \msg) \to \sigma\): Randomized algorithm that takes a group signing key \(gsk_i\) of a group member \(i \in [n]\) and message \(\msg\), outputs a signature under \(gsk_i\).
• \(\verify(gpk, \msg, \sig) \to \{0, 1\}\): Deterministic verification algorithm, takes as input the group public key \(gpk\), message \(m\), and signature \(\sigma\), returns \(1\) if \(m, \sigma\) is a valid message signature pair for \(gpk\).
• \(\open(gmsk, \msg, \sig) \to \{1, .., n\}\): On input the group manager's secret key \(gmsk\), message \(m\), and signature \(\sigma\), returns an identity \(i \in [n]\) if \(\sig\) was created for \(\msg\) by a group member, or \(\bot\) otherwise.