InfoSec Seminar: Short Accountable Ring Signatures Based on DDH

Speaker: Pyrros Chaidos

Date/Time: 18-Sep-2015, 14:30 UTC

Venue: Birbeck 30



Ring signatures and group signatures are prominent cryptographic primitives offering a combination of privacy and authentication. They enable individual users to anonymously sign messages on behalf of a group of users. In ring signatures, the signer chooses an arbitrary ad hoc group of users called a ring and signs as an anonymous member of the ring. In group signatures, group membership is controlled by a group manager. Group signatures additionally enforce accountability by providing the group manager with a secret tracing key that can be used to identify the otherwise anonymous signer in case of abuse.  

Accountable ring signatures, introduced by Xu and Yung (CARDIS 2004), bridge the gap between the two notions. They provide maximal flexibility in choosing the ring in an ad hoc manner, and at the same time maintain accountability by supporting a designated opener that can identify signers in case of abuse. 

We revisit accountable ring signatures and offer a formal security model for the primitive. Our security model offers strong security definitions incorporating protection against maliciously chosen keys and at the same time flexibility both in the choice of the ring and also in the choice of opener. We give a generic construction demonstrating how to realize accountable ring signatures from standard tools.

We give a highly efficient instantiation of our generic construction in the random oracle model by meticulously combining Camenisch's group signature scheme (CRYPTO 1997) with a generalization of the one-out-of-many proofs of knowledge by Groth and Kohlweiss (EUROCRYPT 2015). Our instantiation yields signatures of logarithmic size (in the size of the ring) while relying solely on the well-studied decisional Diffie-Hellman assumption.

In the process, we offer a number of optimizations for the recent Groth and Kohlweiss one-out-of-many proofs, which may be useful for other applications.

Accountable ring signatures imply traditional ring and group signatures. We therefore also obtain highly efficient instantiations of those primitives with signature sizes smaller than all existing ring and group signatures.

To appear at ESORICS 2015


Add to Calendar

This page was last modified on 27 Mar 2014.