# 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
*у = a*mod^{a}*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 ф m*mod^{a}*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,X**2*€ {1.2,...*,q -*1}, and computes*z =*

*s ^{Xl}y^{x}*2 mod

*p,*and sends

*z to A.*

- 3.
*A*computes*w = (z)*mod^{a}*p*(where*aa~*= 1 (mod^{[4]}^{[5]}*q))*and sends*w*to*B.* - 4. If
*w*=*m*mod^{Xl}a^{x}'^{(i) *}*p, В*accepts the signature*s*and the protocol halts. - 5.
*В*selects random secret integers*x[, x'*€ {1,2,... ,_{2}*q*- 1}, and computes*z'*=mod_{s}^{x}iy^{x}>*p,*and sends*z'*to*A.* - 6.
*A*computes*vJ*=*(z')*mod^{a}*p*and sends*w'*to*B.* - 7. If
*w'*=*m*mod^{x}>a^{x}-*p, В*accepts the signature s and the protocol halts. - 8.
*В*computes c =*(wa~*mod^{X2})^{x}>*p*and*d*=*(w'a~*mod^{x}i)^{Xl}*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-*used in the protocol. A third party_{2}*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*,*x*and_{2}*l*in the interval [1,^—1], and computes*s =*((m^{1}'*a*)^{X2})^{l}y~^{x}'^{2}^{x}i mod*p.*The protocol message front В to A would be*z = s*2 mod^{Xl}y^{x}*p,*and from A to В would be*w*=*z*mod^{1}*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.