International Association for Cryptologic Research

International Association
for Cryptologic Research


Extendable Threshold Ring Signatures with Enhanced Anonymity

Gennaro Avitabile , IMDEA Software Institute
Vincenzo Botta , University of Warsaw
Dario Fiore , IMDEA Software Institute
DOI: 10.1007/978-3-031-31368-4_11
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: 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 ($\ps$ 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.
  title={Extendable Threshold Ring Signatures with Enhanced Anonymity},
  author={Gennaro Avitabile and Vincenzo Botta and Dario Fiore},