International Association for Cryptologic Research

International Association
for Cryptologic Research


Tracing a Linear Subspace: Application to Linearly-Homomorphic Group Signatures

Chloé Hébant , Cosmian
David Pointcheval , École normale supérieure Paris
Robert Schädlich , École normale supérieure Paris
DOI: 10.1007/978-3-031-31368-4_12
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: When multiple users have power or rights, there is always the risk of corruption or abuse. Whereas there is no solution to avoid those malicious behaviors, from the users themselves or from external adversaries, one can strongly deter them with tracing capabilities that will later help to revoke the rights or negatively impact the reputation. On the other hand, privacy is an important issue in many applications, which seems in contradiction with traceability. In this paper, we first extend usual tracing techniques based on codes so that not just one contributor can be traced but the full collusion. In a second step, we embed suitable codes into a set~$\mathcal V$ of vectors in such a way that, given a vector~$\mathbf U \in \mathsf{span}(\mathcal V)$, the underlying code can be used to efficiently find a minimal subset~$\mathcal X \subseteq \mathcal V$ such that~$\mathbf U \in \mathsf{span}(\mathcal X)$. To meet privacy requirements, we then make the vectors of~$\mathsf{span}(\cV)$ anonymous while keeping the efficient tracing mechanism. As an interesting application, we formally define the notion of linearly-homomorphic group signatures and propose a construction from our codes: multiple signatures can be combined to sign any linear subspace in an anonymous way, but a tracing authority is able to trace back all the contributors involved in the signatures of that subspace.
  title={Tracing a Linear Subspace: Application to Linearly-Homomorphic Group Signatures},
  author={Chloé Hébant and David Pointcheval and Robert Schädlich},