Convertible Undeniable Signatures

We introduce a new concept called convertible undeniable signature schemes. In these schemes, release of a single bit string by the signer turns all of his signatures, which were originally undeniable signatures, into ordinary digital signatures. We prove that the existence of such schemes is implied by the existence of digital signature schemes. Then, looking at the problem more practically, we present a very efficient convertible undeniable signature scheme. This scheme has the added benefit that signatures can also be selectively converted.