Cryptography: Theory and Practice:Signature Schemes | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

The advantage of the Bos-Chaum Scheme is that signatures are shorter than with the Lamport Scheme. For example, suppose we wish to sign a message of six bits (i.e., k = 6). Since 2⁶ = 64 and , we can take n = 4. This allows a six-bit message to be signed with four y’s, as opposed to six with Lamport. As well, the key is shorter, consisting of eight z’s as opposed to twelve with Lamport.

Figure 6.5 Bos-Chaum Signature Scheme

The Bos-Chaum Scheme requires an injective function φ that associates an n-subset of a 2n-set with each possible binary k-tuple x = (x₁, ..., x_k). We present one simple algorithm to do this in Figure 6.6. Applying this algorithm with x = (0, 1, 0, 0, 1, 1), for example, yields

In general, how big is n in the Bos-Chaum Scheme as compared to k? We need to satisfy the inequality . If we estimate the binomial coefficient

using Stirling’s formula, we obtain the quantity . After some simplification, the inequality becomes

Figure 6.6 Computation of φ in the Bos-Chaum Scheme

Asymptotically, n is about k/2, so we obtain an almost 50% reduction in signature size by using the Bos-Chaum Scheme.

6.5 Undeniable Signatures

Undeniable signatures were introduced by Chaum and van Antwerpen in 1989. They have several novel features. Primary among these is that a signature cannot be verified without the cooperation of the signer, Bob. This protects Bob against the possibility that documents signed by him are duplicated and distributed electronically without his approval. The verification will be accomplished by means of a challenge-and-response protocol.

But if Bob’s cooperation is required to verify a signature, what is to prevent Bob from disavowing a signature he made at an earlier time? Bob might claim that a valid signature is a forgery, and either refuse to verify it, or carry out the protocol in such a way that the signature will not be verified. To prevent this from happening, an undeniable signature scheme incorporates a disavowal protocol by which Bob can prove that a signature is a forgery. Thus, Bob will be able to prove in court that a given forged signature is in fact a forgery. (If he refuses to take part in the disavowal protocol, this would be regarded as evidence that the signature is, in fact, genuine.)

Thus, an undeniable signature scheme consists of three components: a signing algorithm, a verification protocol, and a disavowal protocol. First, we present the signing algorithm and verification protocol of the Chaum-van Antwerpen Undeniable Signature Scheme in Figure 6.7.

Figure 6.7 Chaum-van Antwerpen Undeniable Signature Scheme

We should explain the roles of p and q in this scheme. The scheme lives in ; however, we need to be able to do computations in a multiplicative subgroup G of of prime order. In particular, we need to be able to compute inverses modulo |G|, which is why |G| should be prime. It is convenient to take p = 2q + 1 where q is prime. In this way, the subgroup G is as large as possible, which is desirable since messages and signatures are both elements of G.

We first prove that Alice will accept a valid signature. In the following computations, all exponents are to be reduced modulo q. First, observe that

Since

we have that

Similarly,

implies that

Hence,

as desired.

Here is a small example.

Example 6.5

Suppose we take p = 467. Since 2 is a primitive element, 2² = 4 is a generator of G, the quadratic residues modulo 467. So we can take α = 4. Suppose a = 101; then

Bob will sign the message x = 119 with the signature

Now, suppose Alice wants to verify the signature y. Suppose she chooses the random values e₁ = 38, e₂ = 397. She will compute c = 13, whereupon Bob will respond with d = 9. Alice checks the response by verifying that

Hence, Alice accepts the signature as valid.

We next prove that Bob cannot fool Alice into accepting a fradulent signature as valid, except with a very small probability. This result does not depend on any computational assumptions, i.e., the security is unconditional.

THEOREM 6.1

If (mod p), then Alice will accept y as a valid signature for x with probability 1/q.

PROOF First, we observe that each possible challenge c corresponds to exactly q ordered pairs (e₁, e₂) (this is because y and β are both elements of the multiplicative group G of prime order q). Now, when Bob receives the challenge c, he has no way of knowing which of the q possible ordered pairs (e₁, e₂) Alice used to construct c. We claim that, if (mod p), then any possible response d ∈ G that Bob might make is consistent with exactly one of the q possible ordered pairs (e₁, e₂).

Since α generates G, we can write any element of G as a power of α, where the exponent is defined uniquely modulo q. So write c = αⁱ, d = α^j, x = α^k, and , where and all arithmetic is modulo p. Consider the following two congruences:

This system is equivalent to the following system:

Now, we are assuming that

so it follows that

Hence, the coefficient matrix of this system of congruences modulo q has non-zero determinant, and thus there is a unique solution to the system. That is, every d ∈ G is the correct response for exactly one of the q possible ordered pairs (e₁, e₂), Consequently, the probability that Bob gives Alice a response d that will be verified is exactly 1/q, and the theorem is proved.

Table of Contents