Paper 2024/2014

On the Traceability of Group Signatures: Uncorrupted User Must Exist

Abstract

Group signature (GS) is a well-known cryptographic primitive providing anonymity and traceability. Several implication results have been given by mainly focusing on the several security levels of anonymity, e.g., fully anonymous GS implies public key encryption (PKE) and selfless anonymous GS can be constructed from one-way functions and non-interactive zero knowledge poofs, and so on. In this paper, we explore an winning condition of full traceability: an adversary is required to produce a valid group signature whose opening result is an uncorrupted user. We demonstrate a generic construction of GS secure in the Bellare-Micciancio-Warinschi (BMW) model except the above condition from PKE only. We emphasize that the proposed construction is quite artificial and meaningless in practice because the verification algorithm always outputs 1 regardless of the input. This result suggests us the winning condition is essential in full traceability, i.e., an uncorrupted user must exist. We also explore a public verifiability of GS-based PKE scheme and introduce a new formal security definition of public verifiability by following BUFF (Beyond UnForgeability Features) security. Our definition guarantees that the decryption result of a valid cyphertext is in the message space specified by the public key. We show that the GS-based PKE scheme is publicly verifiable if the underlying GS scheme is fully traceable.