Since its introduction in 1985 [11], the ElGamal signature scheme has been generalized and adapted to numerous different forms (see for instance [15] where an exhaustive survey of some 13000 ElGamal based signatures has been carried out.) For most ElGamal based schemes, the size of the signature (r, s) on a message is 2|p|, |q|+|p| or 2|q|, where p is a large prime and q is a prime factor of p???1