Paper 2023/138

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

Chloé Hébant, Cosmian, Paris, France
David Pointcheval, ENS, Paris, France
Robert Schädlich, ENS,Paris, France

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}(\mathcal V)$ 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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2023
Contact author(s)
chloe hebant @ cosmian com
david pointcheval @ ens fr
robert schaedlich @ ens fr
2023-02-15: approved
2023-02-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chloé Hébant and David Pointcheval and Robert Schädlich},
      title = {Tracing a Linear Subspace: Application to Linearly-Homomorphic Group Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/138},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.