Question 44. What is an Undeniable Signature Scheme?

Undeniable signature scheme, devised by Chaum and van Antwerpen [CV90][CV92], are non-self-authenticating signature schemes (see Question 38), where signatures can only be verified with the signer's consent. However, if a signature is only verifiable with the aid of a signer, a dishonest signer may refuse to authenticate a genuine document. Undeniable signatures solve this problem by adding a new component called the disavowal protocol in addition to the normal components of signature and verification.

The scheme is implemented using public-key cryptography based on the discrete logarithm problem (see Question 52). The signature part of the scheme is similar to other discrete logarithm signature schemes. Verification is carried out by a challenge-response protocol where the verifier, Alice, sends a challenge to the signer, Bob, and views the answer to verify the signature. The disavowal process is similar; Alice sends a challenge and Bob's response shows that a signature is not his. (If Bob does not take part, it may be assumed that the document is authentic.) The probability that a dishonest signer is able to successfully mislead the verifier in either verification or disavowal is 1/p where p is the prime number in the signer's private key. If we consider the average 768-bit private key, there is only a minuscule probability that the signer will be able to repudiate a document he has signed.