# Undeniable signature schemes

Undeniable signature schemes are distinct from digital signatures in the sense of § 11.2 in that the signature verification protocol requires the cooperation of the signer. The following example describes two scenarios where an undeniable signature could be applied.

• 11.120 Example (scenarios for undeniable signatures)
• (i) Entity A (the customer) wishes to gain access to a secured area controlled by entity В (the bank). The secured area might, for example, be a safety-deposit box room. В requires A to sign a time and date document before access is granted. If A uses an undeniable signature, then В is unable to prove (at some later date) to anyone that A used the facility without A’s direct involvement in the signature verification process.
• (ii) Suppose some large corporation A creates a software package. A signs the package and sells it to entity B, who decides to make copies of this package and resell it to a third party С. C is unable to verify the authenticity of the software without the cooperation of A. Of course, this scenario does not prevent В from re-signing the package with its own signature but the marketing advantage associated with corporation A’s name is lost to B. It will also be easier to trace the fraudulent activity of B.
• 11.121 Algorithm Key generation for Algorithm 11.122

SUMMARY: each entity selects a private key and corresponding public key.

Each entity A should do the following:

• 1. Select a random prime p = 2q + 1 where q is also a prime.
• 2. (Select a generator a for the subgroup of order q in Z*.)
• 2.1 Select a random element /3 e Z* and compute a = 0^p~1 )/ч mod p.
• 2.2 If a = 1 then go to step 2.1.
• 3. Select a random integer ae{l,2,...,g — 1} and compute у = aa mod p.
• 4. A’s public key is (p, a, y) A’s private key is a.
• 11.122 Algorithm Chaum-van Antwerpen undeniable signature scheme [1] [2] [3]

Proof that signature verification works. as required.

Fact 11.123 states that, with high probability, an adversary is unable to cause В to accept a fraudulent signature.

• 11.123 Fact (detecting forgeries of undeniable signatures) Suppose that s is a forgery of A's signature for a message m, i.e., s ф ma mod p. Then the probability of В accepting the signature in Algorithm 11.122 is only l/q this probability is independent of the adversary’s computational resources.
• 11.124 Note (disavowing signatures) The signer A could attempt to disavow a (valid) signature constructed by Algorithm 11.122 in one of three ways:
• (i) refuse to participate in the verification protocol of Algorithm 11.122;
• (ii) perform the verification protocol incorrectly; or
• (iii) claim a signature a forger)' even though the verification protocol is successful.

Disavowing a signature by following (i) would be considered as an obvious attempt at (wrongful) repudiation, (ii) and (iii) are more difficult to guard against, and require a disavowal protocol (Protocol 11.125).

Protocol 11.125 essentially applies the verification protocol of Algorithm 11.122 twice and then performs a check to verify that A has performed the protocol correctly.

11.125 Protocol Disavowal protocol for Chaum-van Antwerpen undeniable signature scheme

SUMMARY: this protocol determines whether the signer A is attempting to disavow a valid signature s using Algorithm 11.122, or whether the signature is a forgery.

• 1. В obtains A’s authentic public key (p, a, y).
• 2. В selects random secret integers xi,X2 € {1.2,... ,q - 1}, and computes z =

sXlyx2 mod p, and sends z to A.

• 3. A computes w = (z)a mod p (where aa~[4] [5] = 1 (mod q)) and sends w to B.
• 4. If w = mXl ax'(i) * mod p, В accepts the signature s and the protocol halts.
• 5. В selects random secret integers x[, x'2 € {1,2,... , q - 1}, and computes z' = sxiyx > mod p, and sends z' to A.
• 6. A computes vJ = (z')a mod p and sends w' to B.
• 7. If w' = mx>ax- mod p, В accepts the signature s and the protocol halts.
• 8. В computes c = (wa~X2)x> mod p and d = (w'a~xi)Xl mod p. If c = d, then В concludes that s is a forgery; otherwise, В concludes that the signature is valid and A is attempting to disavow the signature s.
• 3
• 11.127 Note (security> of undeniable signatures)
• (i) The security of Algorithm 11.122 is dependent on the intractability of the discrete logarithm problem in the cyclic subgroup of order q in Z* (see §3.6.6).
• (ii) Suppose verifier В records the messages exchanged in step 2 of Algorithm 11.122, and also the random values xi, x-2 used in the protocol. A third party C should never accept this transcript from В as a verification of signature s. To see why this is the case, it suffices to show how В could contrive a successful transcript of step 2 of Algorithm 11.122 without the signer A’s participation. В chooses a message m, integers x, x2 and l in the interval [1,^—1], and computes s = ((m1' aX2 )l y~x'2 )xi mod p. The protocol message front В to A would be z = sXlyx2 mod p, and from A to В would be w = z1 mod p. Algorithm 11.122 will accept s as a valid signature of A for message m. This argument demonstrates that signatures can only be verified by interacting directly with the signer.

• [1] SUMMARY: A signs a message m belonging to the subgroup of order q in Z*. Any entityВ can verify this signature with the cooperation of A.
• [2] Signature generation. Entity A should do the folio whig: (a) Compute s = ma mod p. (b) A’s signature on message m is s.
• [3] Verification. The protocol for В to verify A’s signature s on m is the following: (a) В obtains A’s authentic public key (p, a, y). (b) В selects random secret integers x,X2 € {1,2,... ,q - 1). (c) В computes г = sXl yXl mod p and sends г to A. (d) A computes w = (z)a~' mod p (where aa~1 = 1 (mod q)) and sends w to B. (e) В computes «/ = mXlaX2 mod p and accepts the signature if and only if w =
• [4] Fact 11.126 states that Protocol 11.125 achieves its desired objectives. 11.126 Fact Let m be a message and suppose that .s is A’s (purported) signature on m.
• [5] If s is a forgery, i.e., s f ma mod p, and if A and В follow Protocol 11.125 correctly,then w = w' (and hence, B’s conclusion that s is a forgery is correct). (ii) Suppose that s is indeed A’s signature for m, i.e., s = ma mod p. Suppose thatВ follows Protocol 11.125 correctly, but that A does not. Then the probability thatw = w' (and hence A succeeds in disavowing the signature) is only 1 jq.