Paper 2025/730

Tetris! Traceable Extendable Threshold Ring Signatures and More

Abstract

Traceable ring signatures enhance ring signatures by adding an accountability layer. Specifically, if a party signs two different messages within the protocol, their identity is revealed. Another desirable feature is $\mathit{\text{extendability}}$. In particular, $\mathit{\text{extendable threshold}}$ ring signatures (ETRS) allow to $\mathit{\text{non-interactively}}$ update already finalized signatures by enlarging the ring or the set of signers. Combining traceability and extendability in a single scheme is unexplored and would offer a new tool for privacy-preserving voting schemes in scenarios where the voters are not known in advance. In this paper, we show how to reconcile both properties by introducing and constructing a new cryptographic primitive called Tetris. Notably, our Tetris construction simultaneously achieves strong anonymity and linear-size signatures, which is the main technical challenge in existing techniques. To solve this challenge, we develop a new approach to traceability that leads to several conceptual and technical contributions. Among those, we introduce and construct, based on Groth-Sahai proofs, $$ shuffle arguments that can be $$ updated by several provers.