|Table of Contents
The setup is the same as the identification scheme. Choose n to be the product of two large primes. Generate the public key, v1, v2,..., vk, and the private key, s1, s2,..., sk, such that si = sqrt (vi-1) mod n.
As with the identification scheme, the security of this signature scheme is proportional to 1/2kt. It also depends on the difficulty of factoring n. Fiat and Shamir pointed out that forging a signature is easier when the complexity of factoring n is considerably lower than 2kt. And, because of birthday-type attacks (see Section 18.1), they recommend that k * t be increased from 20 to at least 72. They suggest k = 9 and t = 8.
Improved Fiat-Shamir Signature Scheme
Silvio Micali and Adi Shamir improved the Fiat-Shamir protocol in . They chose v1, v2,..., vk to be the first k prime numbers. So
This is the public key.
The private key, s1, s2,..., sk is a random square root, determined by
In this version, every person must have a different n. The modification makes it easier to verify signatures. The time required to generate signatures, and the security of those signatures, is unaffected.
There is also an N-party identification scheme, based on the Fiat-Shamir algorithm . Two other improvements to the Fiat-Shamir scheme are proposed in . Another variant is .
Ohta-Okamoto Identification Scheme
This protocol is a modification of the Feige-Fiat-Shamir identification scheme and gets its security from the difficulty of factoring [1198,1199]. The same authors also wrote a multisignature scheme (see Section 23.1), by which a number of different people can sequentially sign a message . This scheme has been proposed for smart-card implementation .
Fiat-Shamir is patented . Anyone interested in licensing the algorithm should contact Yeda Research and Development, The Weizmann Institute of Science, Rehovot 76100, Israel.
Feige-Fiat-Shamir was the first practical identity-based protocol. It minimized computation by increasing the number of iterations and accreditations per iteration. For some implementations, like smart cards, this is less than ideal. Exchanges with the outside world are time-consuming, and the storage required for each accreditation can strain the limited resources of the card.
Louis Guillou and Jean-Jacques Quisquater developed a zero-knowledge identification algorithm more suited to applications like these [670,1280]. The exchanges between Peggy and Victor and the parallel accreditations in each exchange are both kept to an absolute minimum: There is only one exchange of one accreditation for each proof. For the same level of security, the computation required by Guillou-Quisquater is greater than by Feige-Fiat-Shamir by a factor of three. And like Feige-Fiat-Shamir, this identification algorithm can be converted to a digital signature algorithm.
Guillou-Quisquater Identification Scheme
Peggy is a smart card who wants to prove her identity to Victor. Peggys identity consists of a set of credentials: a data string consisting of the cards name, validity period, a bank account number, and whatever else the application warrants. This bit string is called J. (Actually, the credentials can be a longer string and hashed to a J value. This complexity does not modify the protocol in any way.) This is analogous to the public key. Other public information, shared by all Peggys who could use this application, is an exponent v and a modulus n, where n is the product of two secret primes. The private key is B, calculated such that JBv ≡ 1 (mod n).
Peggy sends Victor her credentials, J. Now, she wants to prove to Victor that those credentials are hers. To do this, she has to convince Victor that she knows B. Heres the protocol:
The math isnt that complex:
since B was constructed to satisfy
|Table of Contents