Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

Like the previous protocol, a group of signers use a shared public large prime, p, and a primitive element, g. Alice has a unique private key, x, and a public key, g^x mod p. To sign a message, Alice computes z =m^x mod p.

To verify a signature:

(1)  Bob chooses two random numbers, a and b, both less than p, and sends Alice:

c = m^ag^b mod p

(2)  Alice chooses a random number, q, less than p, and computes and sends to Bob:

s₁ = cg^q mod p, s₂ = (cg^q)^x mod p

(3)  Bob sends Alice a and b, so that Alice can confirm that Bob did not cheat in step (1).

(4)  Alice sends Bob q, so that Bob can use m^x and reconstruct s₁ and s₂. If then the signature is valid.

s₁ ≡ cg^q (mod p)

s₂ ≡ (g^x)^{b +q}z^a (mod p)

Alice can also disavow a signature, z, for a message, m. See [329] for details.

Additional protocols for undeniable signatures can be found in [584,344]. Lein Harn and Shoubao Yang proposed a group undeniable signature scheme [700].

Convertible Undeniable Signatures

An algorithm for a convertible undeniable signature, which can be verified, disavowed, and also converted to a conventional digital signature is given in [213]. It’s based on the ElGamal digital signature algorithm.

Like ElGamal, first choose two primes, p and q, such that q divides p -1. Now you have to create a number, g, less than q. First choose a random number, h, between 2 and p -1. Calculate

g = h^{( p-1)/q} mod p

If g equals the 1, choose another random h. If it doesn’t, stick with the g you have.

The private keys are two different random numbers, x and z, both less than q. The public keys are p, q, g, y, and u, where

y = g^x mod p

u = g^z mod p

To compute the convertible undeniable signature of message m (which is actually the hash of a message), first choose a random number, t, between 1 and q -1. Then compute

T = g^t mod p

and

m' = Ttzm mod q.

Now, compute the standard ElGamal signature on m'. Choose a random number, R, such that R is less than and relatively prime to p -1. Then compute r =g^R mod p, and use the extended Euclidean algorithm to compute s, such that

m' ≡ rx + Rs (mod q)

The signature is the ElGamal signature (r, s), and T.

Here’s how Alice verifies her signature to Bob:

(1)  Bob generates two random numbers, a and b. He computes c = T^Tmag^b mod p and sends that to Alice.

(2)  Alice generates a random number, k, and computes h₁ = cg^k mod p, and h₂ = h₁ ^z mod p, and sends both of those numbers to Bob.

(3)  Bob sends Alice a and b.

(4)  Alice verifies that c = T^Tmag^b mod p. She sends k to Bob.

(5)  Bob verifies that h₁ = T^Tmag^b+k mod p, and that h₂ = y^rar^sau^b+k mod p.

Alice can convert all of her undeniable signatures to normal signatures by publishing z. Now, anyone can verify her signature without her help.

Undeniable signature schemes can be combined with secret-sharing schemes to create distributed convertible undeniable signatures [1235]. Someone can sign a message, then distribute the ability to confirm that the signature is valid. He might, for example, require three out of five people to participate in the protocol in order to convince Bob that the signature is valid. Improvements on this notion deleted the requirement for a trusted dealer [700,1369].

23.5 Designated Confirmer Signatures

Here’s how Alice can sign a message and Bob can verify it, such that Carol can verify Alice’s signature at some later time to Dave (see Section 4.4) [333].

First, a large prime, p, and a primitive element, g, are made public and used by a group of users. The product of two primes, n, is also public. Carol has a private key, z, and a public key is h =g^x mod p.

In this protocol Alice can sign m such that Bob is convinced that the signature is valid,but cannot convince a third party.

(1)  Alice chooses a random x and computes

a = g^x mod p

b = h^x mod p

She computes the hash of m, H(m), and the hash of a and b concatenated, H(a,b). She then computes

j = (H(m) ⊕ H(a, b))^1/3 mod n

and sends a, b, and j to Bob.

(2)  Bob chooses two random numbers, s and t, both less than p, and sends Alice

c = g^sh^t mod p

(3)  Alice chooses a random q less than p, and sends Bob

d = g^q mod p

e = (cd)^x mod p

(4)  Bob sends Alice s and t.

(5)  Alice confirms that

g^sh^t ≡ c (mod p)

Then she sends Bob q.

(6)  Bob confirms

d ≡ g^q (mod p)

e/a^q ≡ a^sb^t (mod p)

H(m) ⊕ H(a, b) ≡ j^1/3 mod n

If they all check out, he accepts the signature as genuine.

Bob cannot use a transcript of this proof to convince Dave that the signature is genuine, but Dave can conduct a protocol with Alice’s designated confirmer, Carol. Here’s how Carol convinces Dave that a and bconstitute a valid signature.

(1)  Dave chooses a random u and v, both less than p, and sends Carol

k = g^ua^v mod p

(2)  Carol chooses a random w, less than p, and sends Dave

l = g^w mod p

y = (kl)^z mod p

(3)  Dave sends Carol u and v.

(4)  Carol confirms that

g^ua^v ≡ k (mod p)

Then she sends Dave w.

(5)  Dave confirms that

g^w ≡ l (mod p)

y/h^w ≡ h^ub^v (mod p)

If they both check out, he accepts the signature as genuine.

In another protocol Carol can convert the designated-confirmer protocol into a conventional digital signature. See [333] for details.