Cryptology ePrint Archive: Report 2015/164

Constant Size Ring Signature Without Random Oracle

Priyanka Bose and Dipanjan Das and C. Pandu Rangan

Abstract: 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.

Category / Keywords: applications / Ring Signature, Set Membership, Groth-Sahai protocol, Zero-Knowledge

Date: received 26 Feb 2015

Contact author: its dipanjan das at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150227:221940 (All versions of this report)

Short URL: ia.cr/2015/164

Discussion forum: Show discussion | Start new discussion