Exploring a Digital Signature Scheme Based on the Computational Difficulty of the Discrete Logarithm Problem
Let’s delve into a transformation of a three-step ZK protocol, which hinges on the computational difficulty of the discrete logarithm problem, into a digital signature scheme. This scheme revolves around an ordered set (y0, y1, …, yi, …, yz−1) of z values yi, determined by the formula:
Here, i ranges from 1 to z; α is a sufficiently large prime number of order q modulo p. The user’s secret key is an ordered array (x0, x1, …, xi, …, xz−1) of random values xi, where 1 ≤ xi < q for i = 1, 2, …, z.
Digital signature formation is defined as a response to a random query, determined by the value of the document and a one-time public key (fixator). This renders the query value from the document unknown until the fixator formation step. The query’s bit string can be taken from a specified hash function’s value, calculated from the signed document with the attached one-time public key. This approach prevents a potential intruder from establishing the query value from the document (i.e., R value) in advance, which would otherwise make signature forgery feasible.
The digital signature generation by the owner of the public key includes the following steps:
1. The signer generates a one-time secret k, calculates the fixator value
which is the first (randomizing) element of the digital signature. Then, they combine the fixator with the message M to be signed and calculate the hash function value F(E,R,M), which is treated as an ordered sequence of one-bit queries set by the signed document.
2. The second element of the digital signature, S, is computed using the formula:
The verification procedure for a digital signature (R, S) to a message M includes:
1. Calculating the hash function value from the first signature element with the attached message M: F(E,R,M) = (e0, e1, e2,…, ei,…, ez-1)
2. Verifying the validity of the comparison:
If this comparison holds, the signature is deemed authentic; otherwise, it’s rejected.
Signature size reduction is achievable by modifying the last digital signature scheme: substituting the query value E for the fixator value R as the first signature element. Then, the fixator value can be deduced from the verification equation, and if the calculated fixator value R∼ equals the true fixator value R = α^k mod p, the signature is considered authentic. The feasibility of the equality R=R∼ can be verified by the equality of two hash function values F(E,M,R)=F(E∼,M,R∼). For z values ≥ 80 bits, the probability that E=E∼ while R=R∼ is negligibly small.
The last digital signature scheme’s downside is the relatively large size of the public and secret keys. This issue can be addressed based on the following idea: A secret key x is generated, and a public key y is calculated by the formula y = α^x mod p. The secret key array (x0, x1, …, xi, …, xz−1) is computed during digital signature formation according to the formula
and the public key array (y0, y1, …, yi, …, yz−1) is computed during the authenticity verification according to the formula
Adopting this convention for expanding the secret and public keys allows us to demonstrate that the following scheme is derived from the previous one:
Digital Signature Generation Procedure for a Message M:
1. The signer generates a one-time secret k, calculates the fixator value R = α^k mod p (a one-time public key). They then combine the fixator with the message M to be signed and calculate the hash function value F(E,M,R), which becomes the first element of the signature.
2. The second element of the digital signature, S, is computed using the formula:
The authenticity verification procedure for a signature (E, S) to a message M includes:
2. Calculating the value:
2. Calculating the hash function value from the R∼ value of the first signature element with the attached message M: F(E∼,M,R∼).
3. Verifying the execution of the equality E=E∼. If this equality holds, the signature is deemed authentic; otherwise, it’s rejected.
The equation used for calculating the second element of the digital signature effectively realizes the computations set by the expanded form of the secret key x is represented as:
The equation used for calculating the second element of the digital signature effectively realizes the computations set by the expanded form of the secret key y is represented as:
Furthermore, if the formula for calculating the first element of the signature is modified from its original version to a new version E = FH(M,R), the resulting scheme precisely aligns with the Schnorr scheme. Placing the fixator R before the signed message is deemed more effective, as it offers protection against attacks involving pre-prepared pairs of messages with identical hash function values, thereby safeguarding against attacks based on pre-prepared collisions.
