Cryptanalysis and Improvement of a Ring Signature Based on ElGamal Signature

The concept of ring signature was first introduced by Rivest et al. in 2001. In a ring signature, instead of revealing the actual identity of the message signer, it specifies a set of possible signers. The verifier can be convinced that the signature was indeed generated by one of the ring members; however, the verifier is unable to tell which member actually produced the signature. A convertible ring signature scheme allows the real signer to convert a ring signature into an ordinary signature by revealing secret information about the ring signature. Thus the real signer can prove the ownership of a ring signature if necessary, and the the other members in the ring can not prove the ownership of a ring signature. At WASA 2006, Jian Ren and Lein Harn proposed a ring signature based on ElGamal signature scheme. The authors claimed that the proposed scheme had the following advantage: the proposed ring signature is inherently a convertible ring signature and enables the actual message signer to prove to a verifier that only he is capable of generating the ring signature. Through our analysis, we find this ring signature scheme can´t satisfy this advantage, i.e., it isn´t convertible. In order to realize the advantage: convertibility, we improved the original scheme. The improved ring signature scheme can satisfy the advantage and is secure.