Paper 2026/1037

On Publicly Verifiable Tokens in Group Signatures with Message-Dependent Opening

Abstract

Group signatures (GSs; Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove group membership, while still enabling a special authority, called the opener, to identify the signer when necessary. Group Signatures with Message-Dependent Opening (GS-MDO; Sakai et al., Pairing 2012) weaken the power of the opener by introducing another authority, the admitter, who issues a message-dependent token. In previous GS-MDO schemes, these tokens can be viewed as signatures. Therefore they can be publicly verified using the verification algorithm of the underlying signature scheme. However, no explicit notion of public verifiability for tokens, meaning the ability to publicly verify whether a token can be used for opening a group signature, has been defined so far. Clarifying this implicit security property is important for understanding the feasibility of GS-MDO. In this paper, we formally define public verifiability of tokens. We establish a proper relationship between verifying a token as a signature and verifying that the token can be used for opening, which typically requires the opener's secret key. We also show that the Ohara et al. pairing-based GS-MDO scheme (AsiaCCS 2013), the Libert et al. lattice-based GS-MDO scheme (ACNS 2016), and the Libert et al. pairing-based GS-MDO scheme (CT-RSA 2014) satisfy our definition, suggesting that our formalization is reasonable. Finally, we discuss how publicly verifiable tokens can be used to provide accountability for the admitter, enabling them to demonstrate that tokens have been honestly generated according to the token-generation algorithm.