In this paper, we present a strong universal designated multi verifier signature scheme based on bilinear pairings, which does not resort to random oracles. The security of the proposed scheme relies on the hardness of solving q- Strong Diffie-Hellman problem. The proposed scheme is more efficient than the existing universal designated multi verifier signature schemes. The signing and the designation phases of the proposed scheme are pairing-free and thus the scheme is ideal for devices with constrained computational capabilities. The proposed scheme finds several applica- tions such as in certification systems, software licensing and fair distributed contract signing etc.