International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Universal Ring Signatures in the Standard Model

Pedro Branco , Johns Hopkins University
Nico Döttling , Helmholtz Center for Information Security (CISPA)
Stella Wohnig , Helmholtz Center for Information Security (CISPA) and Universität des Saarlandes
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: Ring signatures allow a user to sign messages on behalf of an \emph{ad hoc} set of users - a ring - while hiding her identity. The original motivation for ring signatures was whistleblowing [Rivest et al. ASIACRYPT'01]: a high government employee can anonymously leak sensitive information while certifying that it comes from a reliable source, namely by signing the leak. However, essentially all known ring signature schemes require the members of the ring to publish a structured verification key that is compatible with the scheme. This creates somewhat of a paradox since, if a user does not want to be framed for whistleblowing, they will stay clear of signature schemes that support ring signatures. In this work, we formalize the concept of universal ring signatures (URS). A URS enables a user to issue a ring signature with respect to a ring of users, independently of the signature schemes they are using. In particular, none of the verification keys in the ring need to come from the same scheme. Thus, in principle, URS presents an effective solution for whistleblowing. The main goal of this work is to study the feasibility of URS, especially in the standard model (i.e. no random oracles or common reference strings). We present several constructions of URS, offering different trade-offs between assumptions required, the level of security achieved, and the size of signatures: \begin{itemize} \item Our first construction is based on superpolynomial hardness assumptions of standard primitives. It achieves compact signatures. That means the size of a signature depends only logarithmically on the size of the ring and on the number of signature schemes involved. \item We then proceed to study the feasibility of constructing URS from standard polynomially-hard assumptions only. We construct a non-compact URS from witness encryption and additional standard assumptions. \item Finally, we show how to modify the non-compact construction into a compact one by relying on indistinguishability obfuscation. \end{itemize}
Video from ASIACRYPT 2022
  title={Universal Ring Signatures in the Standard Model},
  author={Pedro Branco and Nico Döttling and Stella Wohnig},