The setup is the same as the identification scheme. Choose n to be the product of two large primes. Generate the public key, v_1, v_2,..., v_k, and the private key, s_1, s_2,..., s_k, such that s_i = sqrt (vi^-1) mod n.

(1)  Alice picks t random integers between 1 and n: r_1, r_2,..., r_t, and computes x_1, x_2,..., x_t such that x_i = r_i² mod n.

(2)  Alice hashes the concatenation of the message and the string of xis to generate a bit stream: H(m, x_1, x_2,..., x_t). She uses the first k * t bits of this string as values of b_ij, where i goes from 1 to t, and j goes from 1 to k.

(3)  Alice computes y_1, y_2,..., y_t, where
y_i = r_i * (s₁^bi1 * s₂^bi2 *...* s_k^bik) mod n
(For each i, she multiplies together the values of the s_j based on the random b_i,j values. If b_i,1 is a 1, then s₁ is multiplied; if b_i,1 is a 0, then s₁ is not multiplied.)

(4)  Alice sends Bob m, all the bit values of b_i,j, and all the values of y_i. He already has Alice’s public key: v_1, v_2,..., v_k.

(5)  Bob computes z_1, z_2,..., z_t, where
z_i = y_i² * (v₁^bi1 * v₂^bi2 *...* v_k^bik) mod n
(Again, Bob multiplies based on the b_{i, j} values.) Also note that z_i should be equal to x_i.

(6)  Bob verifies that the first k * t bits of H(m, z_1, z_2,..., z_t) are the b_{i, j} values that Alice sent him.

As with the identification scheme, the security of this signature scheme is proportional to 1/2^kt. 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 2^kt. 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 [1088]. They chose v_1, v_2,..., v_k to be the first k prime numbers. So

v₁ = 2, v₂ = 3, v₃ = 5, and so on.

This is the public key.

The private key, s_1, s_2,..., s_k is a random square root, determined by

s_i = sqrt (v_i^-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 [264]. Two other improvements to the Fiat-Shamir scheme are proposed in [1218]. Another variant is [1368].

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 [1200]. This scheme has been proposed for smart-card implementation [850].

Patents

Fiat-Shamir is patented [1427]. 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 JB^v ≡ 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 = r^v 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 = rB^d mod n, and sends it to Victor.

(4)  Victor computes T^´ = D^vJ^d mod n. If T ≡ T^´ (mod n), then the authentication succeeds.

The math isn’t that complex:

T^´ = D^vJ^d = (rB^d)^vJ^d = r^vB^dvJ^d = r^v(JB^v)^d = r^v ≡ T (mod n)

since B was constructed to satisfy

JB^v ≡ 1 (mod n)