### 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.