|Previous||Table of Contents||Next|
Guillou-Quisquater Signature Scheme
This identification can be converted to a signature scheme, also suited for smart-card implementation [671,672].
The public and private key setup is the same as before. Heres the protocol:
What if many people want to sign the same document? The easy solution has each of them signing separately, but this signature scheme can do better than that. Here Alice and Bob sign the same document and Carol verifies the signatures, but any number of people can be involved in the signature process. As before, Alice and Bob have their own unique J and B values: (JA, BA) and (JB, BB). The values n and v are common to the system.
This protocol can be extended to any number of people. For multiple people to sign, they all multiply their individual Ti values together in step (3), and their individual Di values together in step (7). To verify a multiple signature, multiply all the signers Ji values together in step (8). Either all the signatures are valid or there is at least one invalid signature.
Claus Schnorrs authentication and signature scheme [1396,1397] gets its security from the difficulty of calculating discrete logarithms. To generate a key pair, first choose two primes, p and q, such that q is a prime factor of p - 1. Then, choose an a not equal to 1, such that aq ≡ 1 (mod p). All these numbers can be common to a group of users and can be freely published.
To generate a particular public-key/private-key key pair, choose a random number less than q. This is the private key, s. Then calculate v = a-s mod p. This is the public key.
The security is based on the parameter t. The difficulty of breaking the algorithm is about 2t. Schnorr recommended that p be about 512 bits, q be about 140 bits, and t be 72.
Digital Signature Protocol
Schnorr can also be used as a digital signature protocol on a message, M. The public-key/private-key key pair is the same, but were now adding a one-way hash function, H(M).
In his paper, Schnorr cites these novel features of his algorithm:
Most of the computation for signature generation can be completed in a preprocessing stage, independent of the message being signed. Hence, it can be done during idle time and not affect the signature speed. An attack against this preprocessing stage is discussed in , but I dont think its practical.
For the same level of security, the length of signatures is less for Schnorr than for RSA. For example, with a 140-bit q, signatures are only 212-bits long, less than half the length of RSA signatures. Schnorrs signatures are also much shorter than ElGamal signatures.
Of course, practical considerations may make even fewer bits suitable for a given scheme: For example, an identification scheme where the cheater must perform an on-line attack in only a few seconds, versus a signature scheme where the cheater can calculate for years off-line to come up with a forgery.
A modification of this algorithm, by Ernie Brickell and Kevin McCurley, enhances its security .
Schnorr is patented in the United States  and in many other countries. In 1993, PKP acquired the worldwide rights to the patent (see Section 25.5). The U.S. patent expires on February 19, 2008.
There is a standard method of converting an identification scheme into a signature scheme: Replace Victor with a one-way hash function. The message is not hashed before it is signed; instead the hashing is incorporated into the signing algorithm. In principle, this can be done with any identification scheme.
|Previous||Table of Contents||Next|