RSA-based undeniable signatures

We present the first undeniable signatures scheme based on RSA. Since their introduction in 1989 a significant amount of work has been devoted to the investigation of undeniable signatures. So far, this work has been based on discrete log systems. In contrast, our scheme uses regular RSA signatures to generate undeniable signatures. In this new setting, both the signature and verification exponents of RSA are kept secret by the signer, while the public key consists of a composite modulus and a sample RSA signature on a single public message. Our scheme possesses several attractive properties. First, provable securit y, as forging the undeniable signatures is as hard as forging regular RSA s ignatures. Second, both the confirmation and denial protocols are zero-know ledge. In addition, these protocols are efficient (particularly, the confir mation protocol involves only two rounds of communication and a small numbe r of exponentiations). Furthermore, the RSA-based structure of our scheme p rovides with simple and elegant solutions to add several of the more advanc ed properties of undeniable signatures found in the literature, including c onvertibility of the undeniable signatures (into publicly verifiable ones), the possibility to delegate the ability to confirm and deny signatures to a third party without giving up the power to sign, and the existence of dis tributed (threshold) versions of the signing and confirmation operations. Due to the above properties and the fact that our undeniable signatures are identical in form to standard RSA signatures, the scheme we present become s a very attractive candidate for practical implementations.