Paper 2004/370

Tracing-by-Linking Group Signautres

Victor K. Wei

Abstract

In a group signature \cite{CvH91}, any group member can sign on behalf of the group while remaining anonymous, but its identity can be traced in an future dispute investigation. Essentially all state-of-the-art group signatures implement the tracing mechnism by requiring the signer to escrow its identity to an Open Authority (OA) \cite{ACJT00,CL02scn,BMW03,KiayiasYu04,BSZ05,BBS04,KiayiasTsYu04}. We call them {\em Tracing-by-Escrowing (TbE)} group signatures. One drawback is that the OA also has the unnecessary power to trace without proper cause. In this paper we introduce {\em Tracing-by-Linking (TbL)} group signatures. The signer's anonymity is irrevocable by any authority if the group member signs only once (per event). But if a member signs twice, its identity can be traced by a public algorithm without needing any trapdoor. We initiate the formal study of TbL group signatures by introducing its security model, constructing the first examples, and give several applications. Our core construction technique is the successful transplant of the TbL technique from single-term offline e-cash from the blind signature framework \cite{Brands93,Ferguson93,Ferguson93c} to the group signature framework. Our signatures have size $O(1)$.