Introduction: Digital signatures [W. Diffie and M. E. Hellman, IEEE Trans. Inf. Theory 22, 644–654 (1976; Zbl 0435.94018)] – unlike handwritten signatures and banknote printing - are easily copied exactly. This property can be advantageous for some uses, such as dissemination of announcements and public keys, where the more copies distributed the better. But it is unsuitable for many other applications. Consider electronic replacements for all the written or oral commitments that are to some extent personally or commercially sensitive. In such cases the proliferation of certified copies could facilitate improper uses like blackmail or industrial espionage. The recipient of such a commitment should of course be able to ensure that the issuer cannot later disavow it - but the recipient should also be unable to show the commitment to anyone else without the issuer’s consent. Undeniable signature are well suited to such applications. An undeniable signature, like a digital signature, is a number issued by a signer that depends on the signer’s public key and the message signed. Unlike a digital signature, however, an undeniable signature cannot be verified without the signer’s cooperation. The validity of an undeniable signature can be ascertained by anyone issuing a challenge to the signer and testing the signer’s response. If the test is successful, there is an exponentially high probability that the signature is valid. If the test fails, there are two cases: (a) the signature is not valid; or (b) the signer is giving improper responses, presumably in an effort to falsely deny a valid signature. But even if the signer has infinite computing power, the challenger can distinguish case (a) from case (b), with exponentially high certainty, by means of a second challenge. Quite efficient and practical undeniable signature protocols based on the “discrete log” problem [Zbl 0435.94018] are presented below. Since all signers can use the same group, signatures created by different signers commute with each other - a useful property D. Chaum [“Blinding for unanticipated signatures.” Eurocrypt 1987, Lect. Notes Comput. Sci. 304, 227–233 (1988)], that has not yet been achieved for digital signatures. Furthermore, a new type of “blinding” D. Chaum and J.-H. Evertse [“A secure and privacy-protecting protocol for transmitting personal information between organizations.” Crypto 1986, Lect. Notes Comput. Sci. 263, 118–167 (1987)], can be applied in the signing as well as in the challenge and response.
For the entire collection see Zbl 0719.00029.