Paper 2022/1568

Extendable Threshold Ring Signatures with Enhanced Anonymity

Gennaro Avitabile, IMDEA Software Institute
Vincenzo Botta, University of Warsaw
Dario Fiore, IMDEA Software Institute

Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ''ring''. Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures (ETRS). ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers. An application of this primitive is anonymous count me in. A first signer creates a ring signature with a sufficiently large ring announcing a proposition in the signed message. After such cause becomes \emph{public}, other parties can anonymously decide to support that proposal by producing an updated signature. Crucially, such applications rely on partial signatures being posted on a \emph{publicly accessible} bulletin board since users may not know/trust each other. In this paper, we first point out that even if anonymous count me in was suggested as an application of ETRS, the anonymity notion proposed in the previous work is insufficient in many application scenarios. Indeed, the existing notion guarantees anonymity only against adversaries who just see the last signature, and are not allowed to access the ''full evolution" of an ETRS. This is in stark contrast with applications where partial signatures are posted in a public bulletin board. We therefore propose stronger anonymity definitions and construct a new ETRS that satisfies such definitions. Interestingly, while satisfying stronger anonymity properties, our ETRS asymptotically improves on the two ETRS presented in prior work [PKC 2022] in terms of both time complexity and signature size. Our ETRS relies on extendable non-interactive witness-indistinguishable proof of knowledge (ENIWI PoK), a novel technical tool that we formalize and construct, and that may be of independent interest. We build our constructions from pairing groups under the SXDH assumption.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2023
Threshold Ring SignaturesAnonymityMalleable Proof Systems
Contact author(s)
avitabilegenn @ gmail com
botta vin @ gmail com
dario fiore @ imdea org
2023-03-06: last of 2 revisions
2022-11-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gennaro Avitabile and Vincenzo Botta and Dario Fiore},
      title = {Extendable Threshold Ring Signatures with Enhanced Anonymity},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1568},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.