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

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.

(1)  Alice picks t random integers between 1 and n: r1, r2,..., rt, and computes x1, x2,..., xt such that xi = ri2 mod n.
(2)  Alice hashes the concatenation of the message and the string of xis to generate a bit stream: H(m, x1, x2,..., xt). She uses the first k * t bits of this string as values of bij, where i goes from 1 to t, and j goes from 1 to k.
(3)  Alice computes y1, y2,..., yt, where
yi = ri * (s1bi1 * s2bi2 *...* skbik) mod n
(For each i, she multiplies together the values of the sj based on the random bi,j values. If bi,1 is a 1, then s1 is multiplied; if bi,1 is a 0, then s1 is not multiplied.)
(4)  Alice sends Bob m, all the bit values of bi,j, and all the values of yi. He already has Alice’s public key: v1, v2,..., vk.
(5)  Bob computes z1, z2,..., zt, where
zi = yi2 * (v1bi1 * v2bi2 *...* vkbik) mod n
(Again, Bob multiplies based on the bi, j values.) Also note that zi should be equal to xi.
(6)  Bob verifies that the first k * t bits of H(m, z1, z2,..., zt) are the bi, j values that Alice sent him.

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

v1 = 2, v2 = 3, v3 = 5, and so on.

This is the public key.

The private key, s1, s2,..., sk is a random square root, determined by

si = sqrt (vi-1) mod n

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.

Other Enhancements

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 .

Patents

Fiat-Shamir is patented . Anyone interested in licensing the algorithm should contact Yeda Research and Development, The Weizmann Institute of Science, Rehovot 76100, Israel.

### 21.2 Guillou-Quisquater

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. Peggy’s identity consists of a set of credentials: a data string consisting of the card’s 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. Here’s the protocol:

(1)  Peggy picks a random integer r, such that r is between 1 and n - 1. She computes T = rv mod n and sends it to Victor.
(2)  Victor picks a random integer, d, such that d is between zero and v - 1. He sends d to Peggy.
(3)  Peggy computes D = rBd mod n, and sends it to Victor.
(4)  Victor computes T´ = DvJd mod n. If TT´ (mod n), then the authentication succeeds.

The math isn’t that complex:

T´ = DvJd = (rBd)vJd = rvBdvJd = rv(JBv)d = rvT (mod n)

since B was constructed to satisfy

JBv ≡ 1 (mod n)

[an error occurred while processing this directive]