International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Logarithmic-Size (Linkable) Threshold Ring Signatures in the Plain Model

Abida Haque , North Carolina State University
Stephan Krenn , Austrian Institute of Technology
Daniel Slamanig , Austrian Institute of Technology
Christoph Striecks , Austrian Institute of Technology
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2022
Abstract: A $1$-out-of-$N$ ring signature scheme, introduced by Rivest, Shamir, and Tauman-Kalai (ASIACRYPT '01), allows a signer to sign a message as part of a set of size $N$ (the so-called ``ring'') which are anonymous to any verifier, including other members of the ring. Threshold ring (or ``thring'') signatures generalize ring signatures to $t$-out-of-$N$ parties, with $t \geq 1$, who anonymously sign messages and show that they are distinct signers (Bresson et al., CRYPTO'02). Until recently, there was no construction of ring signatures that both $(i)$ had logarithmic signature size in $N$, and $(ii)$ was secure in the plain model. The work of Backes et al. (EUROCRYPT'19) resolved both these issues. However, threshold ring signatures have their own particular problem: with a threshold $t \geq 1$, signers must often reveal their identities to the other signers as part of the signing process. This is an issue in situations where a ring member has something controversial to sign; he may feel uncomfortable requesting that other members join the threshold, as this reveals his identity. Building on the Backes et al. template, in this work we present the first construction of a thring signature that is logarithmic-sized in $N$, in the plain model, and does not require signers to interact with each other to produce the thring signature. We also present a linkable counterpart to our construction, which supports a fine-grained control of linkability. Moreover, our thring signatures can easily be adapted to achieve the recent notions of claimability and repudiability (Park and Sealfon, CRYPTO'19).
Video from PKC 2022
  title={Logarithmic-Size (Linkable) Threshold Ring Signatures in the Plain Model},
  author={Abida Haque and Stephan Krenn and Daniel Slamanig and Christoph Striecks},