New Convertible Undeniable Signature Schemes

Undeniable signatures are like ordinary digital signatures, except that testing validity of a signature requires interaction with the signer. This gives the signer additional control over who will benefit from being convinced by a signature, and is particularly relevant when signing sensitive, non-public data. Convertible undeniable signatures offer additional flexibility in that there is a separate verification key that can be used to verify a signature (without interaction). This allows the signer to delegate the ability to verify signatures to one or more participants, and ultimately to convert all signatures to ordinary ones by making the verification key public. While provably secure theoretical solutions exist for convertible schemes, earlier practical schemes proposed have either been broken or their status as far as security is concerned is very unclear. In this paper, we present two new convertible schemes, in which forging signatures is provably equivalent to forging El Gamal signatures. The difficulty of verifying signatures without interacting with the signer is based on the factoring problem for one of the schemes and on the Diffie-Hellman problem for the other scheme.