Constant Size Ring Signature Without Random Oracle

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 its security is provided 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 remained as an interesting open problem.

Our first contribution is a generic technique to convert a

compatible

signature scheme to a constant-sized ring signature scheme. The technique employs a constant size set membership check that may be of independent interest. Our construction is instantiated with asymmetric pairing over groups of composite order and 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 demonstrate a concrete instantiation of the scheme with Full Boneh-Boyen signature scheme.