Paper 2024/2014

On the Traceability of Group Signatures: Uncorrupted User Must Exist

Abstract

Group signatures (GS) are a well-known cryptographic primitive that provide both anonymity and traceability. Several implication results have been established, mainly focusing on different security levels of anonymity. For example, fully anonymous GS implies public-key encryption (PKE), and selfless anonymous GS can be constructed from one-way functions and non-interactive zero-knowledge proofs, among others. In this paper, we explore a winning condition for full traceability: an adversary must produce a valid group signature whose opening reveals an uncorrupted user. We present a generic construction of GS that is secure in the Bellare-Micciancio-Warinschi (BMW) model, except for the above condition, based solely on PKE. We emphasize that the proposed construction is highly artificial and practically meaningless because the verification algorithm always outputs 1 regardless of the input. This result suggests that the winning condition is essential for full traceability, namely that an uncorrupted user must exist.

Note: Since a flaw was found in the definition of public verifiability given in the previous version, in the current version we describe the issue and leave providing a formal definition of public verifiability as future work.