Paper 2015/164

Constant Size Ring Signature Without Random Oracle

Priyanka Bose, Dipanjan Das, and C. Pandu Rangan


Ring signature enables an user to anonymously sign a message on behalf of a group of users termed as ‘ring’ formed in an ‘ad-hoc’ manner. A naive scheme produces a signature linear in the size of the ring, but this is extremely inefficient when ring size is large. Dodis et al. proposed a constant size scheme in EUROCRYPT’13, but provably secure in random oracle model. Best known result without random oracle is a sub-linear size construction by Chandran et al. in ICALP’07 and a follow-up work by Essam Ghadafi in IMACC’13. Therefore, construction of a constant size ring signature scheme without random oracle meeting stringent security requirement still remains as an interesting open problem. Our first contribution is a generic technique to convert a compatible signature scheme to a constantsized ring signature scheme. The technique employs a constant size set membership check that may be of independent interest. Our construction is instantiated over asymmetric pairing of composite order and optimally efficient. The scheme meets strongest security requirements, viz. anonymity under full key exposure and unforgeability against insider-corruption without using random oracle under simple hardness assumptions. We also provide a concrete instantiation of the scheme based on Full Boneh-Boyen signatures.

Available format(s)
Publication info
Preprint. MINOR revision.
Ring SignatureSet MembershipGroth-Sahai protocolZero-Knowledge
Contact author(s)
its dipanjan das @ gmail com
2015-02-27: received
Short URL
Creative Commons Attribution


      author = {Priyanka Bose and Dipanjan Das and C.  Pandu Rangan},
      title = {Constant Size Ring Signature Without Random Oracle},
      howpublished = {Cryptology ePrint Archive, Paper 2015/164},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.