 Fiat-Shamir signature schemes

As described in Note 10.30, any identification scheme involving a witness-challenge response sequence can be converted to a signature scheme by replacing the random challenge of the verifier with a one-way hash function. This section describes two signature mechanisms which arise in this way. The basis for this methodology is the Fiat-Shamir identification protocol (Protocol 10.24).

Feige-Fiat-Shamir signature scheme

The Feige-Fiat-Shamir signature scheme is a modification of an earlier signature scheme of Fiat and Shamir, and requires a one-way hash function h: {0,1}* —> {0,1}л for some fixed positive integer k. Here {0, l}fc denotes the set of bitstrings of bitlength A:, and {0,1}* denotes the set of all bitstrings (of arbitrary bitlengths). The method provides a digital signature with appendix, and is a randomized mechanism.

11.39 Algorithm Key generation for the Feige-Fiat-Shamir signature scheme     

11.40 Algorithm Feige-Fiat-Shamir signature generation and verification

SUMMARY: entity A signs a binary message m of arbitrary length. Any entity В can verify this signature by using A’s public key.

• 1. Signature generation. Entity A should do the folio whig:
• (a) Select a random integer r, 1 < r < n — 1.
• (b) Compute и = r mod n.
• (c) Compute e = (ei, ег,... , e*,) = /r(m||u); each e* € {0,1}.
• (d) Compute s = r ■ IIj=i s<j mod n.
• (e) A’s signature for m is (e, s).
• 2. Verification. To verify A’s signature (e, s) on m, В should do the following:
• (a) Obtain A’s authentic public key (wi, i/2> • • ■ , щ) and n.
• (b) Compute w = A' • П/=1 v<jJ mod 71.
• (c) Compute e' = /i(m||u’).
• (d) Accept the signature if and only if e = e'.

Proof that signature verification works. Hence, w = и and therefore e = e'.

11.41 Example (Feige-Fiat-Slianiir signature generation with artificially small parameters) Key generation. Entity A generates primes p = 3571, q = 4523, and computes n = pq = 16151633. The following table displays the selection of Sj (ri’s private key) and integers Vj (ri’s public key) along with intermediate values sj1.

 j 1 2 3 4 5 si 42 73 85 101 150 sj1 mod n 4999315 885021 6270634 13113207 11090788 vj = sj mod n 503594 4879739 7104483 1409171 6965302

Signature generation. Suppose h: {0,1}* —> {0, l} is a hash function. A selects a random integer r = 23181 and computes и = r mod n = 4354872. To sign message m, A evaluates e = /r(m||u) = 10110 (the hash value has been contrived for this example). A forms s = г«1«з«4 mod n = (23181)(42)(85)(101) mod n = 7978909; the signature for m is (e = 10110, s = 7978909).

Signature verification. В computes s mod n = 2926875 and V1V3V4 mod n = (503594) (7104483)(1409171) mod n = 15668174. В then computes w = sviV3V4 mod » = 4354872. Since w = u, it follows that e' = /r(m||u>) = /i(ra||u) = e and, hence, В accepts the signature. □

• 11.42 Note (security of Feige-Fiat-Shamir signature scheme)
• (i) Unlike the RSA signature scheme (Algorithm 11.19), all entities may use the same modulus 71 (cf. §8.2.2(vi)). In this scenario, a trusted third party (TTP) would need to generate the primes p and q and also public and private keys for each entity.
• (ii) The security of the Feige-Fiat-Shamir scheme is based on the intractability of computing square roots modulo n (see §3.5.2). It has been proven to be secure against an adaptive chosen-message attack, provided that factoring is intractable, h is a random function, and the sfs are distmct.
• 11.43 Note (parameter selection and key storage requirements) If n is a t-bit integer, the private key constructed in Algorithm 11.39 is kt bits hi size. This may be reduced by selecting the random values Sj, 1 < j < k, as numbers of bitlength t' < t t', however, should not be chosen so small that guessing the sj is feasible. The public key is (k + 1 )t. bits in size. For example, if t = 768 and к = 128, then the private key requires 98304 bits and the public key requires 99072 bits.
• 11.44 Note (identity-based Feige-Fiat-Shamir signatures) Suppose a TTP constructs prunes p and q and modulus n; the modulus is common to all entities in the system. Algorithm 11.39 can be modified so that the scheme is identity-based. Entity A’s bitstring I, contains information which identifies A. The TTP computes Vj = /(/,i||j), 1 < j < к, where / is a one-way hash function from {0,1}* to Q„ and j is represented in binary, and computes a square root Sj of v~l modulo n, 1 < j < к. A’s public key is simply the identity information I a, while A’s private key (transported securely and secretly by the TTP to A) is the fc-tuple (.si, s 2,... ,«fc). The functions h, /.and the modulus n are system-wide quantities.

This procedure has the advantage that the public key generated hi Algorithm 11.39 might be generated from a smaller quantity I a, potentially reducing the storage and transmission cost. It has the disadvantages that the private keys of entities are known to the TTP, and the modulus n is system-wide, making it a more attractive target.

11.45 Note (small prime variation of Feige-Fiat-Shamir signatures) This improvement aims to reduce the size of the public key and hicrease the efficiency of signature verification. Unlike the modification described in Note 11.44, each entity A generates its own modulus ?гд and a set of к small prunes vi,V2, ■.. ,vkQn (each prime will require around 2 bytes to represent). Entity A selects one of the square roots Sj of v~L modulo n for each j, 1 < j <

these form the private key. The public key consists of ?гд and the values vi,V2, • • • ,ufc- Verification of signatures proceeds more efficiently since computations are done with much smaller numbers.

11.46 Note (performance characteristics of Feige-Fiat-Shamir signatures) With the RSA scheme and a modulus of length t = 768, signature generation using naive techniques requires, on average, 1152 modular multiplications (more precisely, 768 squarings and 384 multiplications). Signature generation for the Feige-Fiat-Shamir scheme (Algorithm 11.40) requires, on average, к/2 modular multiplications. To sign a message with this scheme, a modulus of length t = 768 and к = 128 requires, on average, 64 modular multiplications, or less than 6% of the work required by a naive implementation of RSA. Signature verification requires only one modular multiplication for RSA if the public exponent is e = 3, and 64 modular multiplications, on average, for Feige-Fiat-Shamir. For applications where signature generation must be performed quickly and key space storage is not limited, the Feige-Fiat-Shamir scheme (or DSA-like schemes — see §11.5) may be preferable to RSA.

•  SUMMARY: each entity creates a public key and corresponding private key. Each entity A should do the following:
•  Generate random distinct secret primes p, q and form n = pq.
•  Select a positive integer к and distinct random integers si, s2, ■ ■ • , sfc € Z*.
•  Compute Vj = s~2 mod n, 1 < j < к.
•  ,4’s public key is the /.--tuple (v1,v2,... , t>r) and the modulus n; A’s private key isthe fc-tuple (si,s2, • • • ,«*)•
•  2
•  2
•  2
•  2
•  2
•  2