Reducing the Size of the Public Key in the Fiat–Shamir Signature Scheme
Abstract:
The Fiat–Shamir signature scheme is a widely used digital signature scheme known for its efficiency and security. However, one of its drawbacks is the large size of the public key. In this article, we explore a straightforward method to reduce the size of the public key in the Fiat–Shamir signature scheme. By generating multiple secret values from a single random value, we can maintain the scheme’s security while significantly decreasing the size of the public key. This optimization preserves all the steps of signature generation and verification, making it a practical enhancement for resource-constrained environments.
Introduction
Digital signatures play a crucial role in securing various online transactions and communications. The Fiat–Shamir signature scheme is a well-established method for generating digital signatures. However, it is known for having a relatively large public key size, which can be a concern in certain applications. In this article, we present a technique to reduce the size of the public key in the Fiat–Shamir signature scheme while maintaining its security.
The Fiat–Shamir Signature Scheme
The Fiat–Shamir signature scheme is based on the difficulty of computing square roots modulo n, where n is the product of two large prime numbers, p and q. The scheme can be thought of as a three-step zero-knowledge protocol based on Fiat–Shamir transformation [14]. There are two possible scenarios:
1. Each participant generates their individual modulus n = pq.
2. All participants use the same composite modulus n, generated by a trusted authority, with the original prime factors p and q destroyed.
The first scenario is preferable as it guarantees that the modulus factorization is unknown to potential attackers, enhancing security.
Public Key Size Reduction
To reduce the size of the public key, we introduce a method that involves generating multiple secret values x0, x1, …, xi, …, xz−1 from a single random value x, which serves as the private key of the signer. This generation follows the formula:
The public key consists of values y0, y1, …, yi, …, yz−1, calculated using either of the following formulas:
or
With the ordered sets of values (x0, x1, …, xi, …, xz−1) and (y0, y1, …, yi, …, yz−1), computed from the private key x and the public key y, respectively, we can fully preserve all steps of the signature generation and verification process.
In the specified method of calculating the values of xi and yi, the computation of the product of values xi (and yi) selected based on the bits of the value E is replaced by a single operation of raising the secret key x (public key y) to the power of E modulo n. Indeed, in step 4 of the signature generation procedure, we have:
In step 1 of the signature verification procedure, we have:
where the bit string E is treated as a binary number.
Taking into account the remarks made, we obtain a modified version of the Fiat–Shamir signature scheme, which is described as follows:
1. Secret Key Generation:
Generate a random number x such that (n div 2^64)≤x≤n−1
and GCD(xi,n)=1
2. Public Key Generation:
Calculate the value y, which is the modular inverse of x squared modulo n. The public key is represented as y=x−2modn.
3. Signature Generation for a Message m:
- Generate a random number k such that k<n−1.
- Calculate the value R = k^2 mod n.
- Append R to the message m and compute a z-bit value using a specified hash function FH: E=FH(M∣∣R), where E is represented as a sequence of bits ei : E=(e0,e1,…,ei,…,ez−1).
- Calculate the second part of the signature as S≡k x^e mod n.
- The signature for message m is represented as a pair of numbers (E, S)
4. Signature Verification for a Message m:
- Calculate the value R′≡y R mod n.
- Append R′ to the received message and compute E′=FH(M∣∣R′).
- Compare the values E and E’. If E=E′, the signature is considered authentic.
