The Fiat-Shamir digital signature scheme
This digital signature scheme is based on the complexity of computing square roots modulo n, which is the product of two large prime numbers, p and q. It can be viewed as the result of transforming a three-step zero-knowledge Fiat-Shamir protocol.
There are two possible scenarios:
- Each participant generates their individual modulus n = pq.
- All participants use the same composite modulus n, generated by a trusted center, and the original prime factors p and q are destroyed (knowledge of the modulus’s factorization is not required to create public and private keys).
The first case is preferable as it ensures that the modulus’s factorization remains unknown to potential attackers.
The secret key is formed as follows: a participant generates z random numbers x0, x1, …, xi, …, xz−1, such that (n div 2^64) ≤ xi ≤ n — 1, and GCD(xi, n) = 1 for i = 0, 1, …, z — 1.
The public key is formed by computing values that are inverses of the squares of numbers xi modulo n. The public key consists of a set of numbers y0, y1, …, yi, …, yz−1, where:
The process of generating a signature for a message m involves the following steps:
1. Generate a random number k, where k < n — 1. In a sense, k acts as a one-time secret key, providing obfuscation of the main (long-term) secret key.
2. Calculate the value of the commitment R = k² mod n (essentially, this is a one-time public key).
3. Append the number R to the message M, and compute a z-bit value of a specified hash function FH from the resulting new message: E = FH(M||R). This value E forms the first part of the signature (a random commitment generated based on the message to be signed).
4. Calculate the second part of the signature (the response to a random challenge) according to the following formula:
This completes the generation of the signature (E, S) for the message M. It’s worth noting that different signature values can be generated for the same message since a random number k is used.
Authentication of the signature’s validity (verification of the correct response to a random challenge) is performed as follows:
1. Calculate the value R’ as follows:
2. Append the number R’ to the message M and compute the hash value
E’ = FH(M||R’)
3. Compare values E and E’. If E = E’, the signature is considered valid.
It should be noted that instead of taking the signature as (R, S), one could calculate the value E based on R and S. However, in this variant, the signature becomes twice as long.
The advantage of this digital signature scheme is its relatively low computational complexity for signature generation and verification, which ensures high efficiency. The drawback is the large size of public and private keys. For a 1024-bit modulus and a 160-bit hash function, each key is approximately 164 Kbits in size. This can lead to substantial overhead in the storage of public keys when dealing with a large number of participants. Additionally, the hardware implementation of this signature scheme can become significantly more complex.
