Paper 2025/2007

k-Anonymous Group Signatures

Abstract

We review $k$-anonymity in authentication schemes, group signatures, and ring signatures. Existing constructions either require a signer to maintain state across interactions, or admit tracing algorithms that cost $O(n^k)$ in the number $n$ of signatures. We introduce $k$-anonymous group signatures ($k$-AGS), that achieves stateless signing with a tracing cost $O(n+k)$, while necessarily sacrificing unlinkability. We present a generic construction of $k$-AGS together with an efficient instantiation. We additionally construct a proof-of-concept $k$-unlinkable group signature ($k$-UGS) scheme that achieve unlinkability at the expense of $O(n^2k)$ tracing overhead. We pose the question of whether stateless signing, $O(n+k)$ tracing, and unlinkability are simultaneously achievable, and leave it as an open problem. Building on our $k$-AGS framework, we introduce $k$-Anonymous Set Pre Constrained Group Signatures ($k$-ASPCGS), a threshold variant of Set Pre-Constrained Group Signatures introduced by Bartusek et al. (EUROCRYPT '23). As a proof-of-concept, we present two generic constructions of $k$-ASPCGS. We show that our notions arise naturally in the context of content moderation in end-to-end encrypted messaging platforms, where users must remain anonymous until a threshold number of distinct illegitimate contents have been reported.