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

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≥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≥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).