![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
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 26 = 64 and
The Bos-Chaum Scheme requires an injective function φ that associates an n-subset of a 2n-set with each possible binary k-tuple x = (x1, ..., xk). 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 using Stirlings formula, we obtain the quantity
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 SignaturesUndeniable 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 Bobs 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.
We should explain the roles of p and q in this scheme. The scheme lives in 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, 22 = 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 e1 = 38, e2 = 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 PROOF First, we observe that each possible challenge c corresponds to exactly q ordered pairs (e1, e2) (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 (e1, e2) Alice used to construct c. We claim that, if 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 = αi, d = αj, x = αk, and 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 (e1, e2), Consequently, the probability that Bob gives Alice a response d that will be verified is exactly 1/q, and the theorem is proved.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |