Three-Step Protocols with ZKP
A notable advantage of the multi-round Fiat-Shamir protocol is its relatively low computational complexity — each participant in the protocol performs no more than 2z modular multiplications, where z is the predetermined number of rounds. However, a significant drawback of all multi-round protocols is the need for a very large number of alternating message transmissions between the prover and the verifier. This issue can be mitigated by combining all the verifier’s random one-bit requests into a single random bit string sent in entirety to the prover, and by condensing all responses into a single value sent from the prover to the verifier. Thus, the prover computes z distinct commitments and sends them in a specific order to the verifier. The prover then receives a z-bit random string from the verifier, calculates z responses corresponding to each pair of commitment and bit, and sends these responses back in the corresponding order. This method transforms any multi-round protocol into a three-step protocol, preserving its original computational complexity.
Some multi-round protocols can be converted into three-step versions more practically. This alternative method is realized by using a public key comprising z ordered values, calculated as independent public keys of the original multi-round protocol.
Three-Step Variant of the Fiat-Shamir Protocol
In this variant, each user’s private secret key consists of two large strong prime numbers, p and q, and z sequential values (s1, s2, …, sz). The public key is computed as z ordered values (y1, y2, …, yz) using the formula
i = 1, 2, …, z. The computational difficulty of extracting square roots modulo a composite number n is comparable to the computational difficulty of factoring n into its prime components. Hence, the described protocol is based on the computational challenge of factorization.
The authentication process for the owner of the public key, acting as the prover, occurs in three steps:
- The prover chooses a random number k, such that 1 ≤ k ≤ n — 1, calculates u = k² mod n, and sends it to the verifier.
- The verifier sends a random z-bit string R = (r1, r2, …, rz) to the prover as their request, where each bit ri is equally likely to be 1 or 0.
- The prover computes their response as
and sends it to the verifier.
The verifier considers the response positive if the relationship
is satisfied. It can be shown that the probability of deceiving the verifier in this protocol is 2^−z.
Three-Step Protocol Based on the Complexity of Discrete Logarithm
In this protocol, user authentication is performed using a public key composed of a set of z values,
where i = 1, 2, …, z; α is a number of sufficiently large prime order q modulo p. The user’s secret key is a set of values xi, i = 1, 2, …, z.
The protocol involves the following three steps:
- The prover selects the current one-time secret k, calculates the value
(serving as a one-time public key), and sends R to the verifier.
- The verifier generates a random request as a bit string E = (e1, e2, …, ez) and sends it to the prover.
- The prover computes the response as
and sends it to the verifier.
The verifier deems the received response correct, and the prover authentic, if the following verification relationship is satisfied:
The right side of the equation includes a product of certain public key elements, specifically those matching the indices of the one bits in the request.
The probability of an intruder deceiving the verifier, attempting to impersonate the authentic owner of the public key, is 2^−z. The intruder’s potential attack involves selecting a random number w and a random z-bit value E’, calculating
and then posing as the legitimate prover by sending the commitment value to the verifier. If the verifier’s random z-bit request coincidentally matches E’, the intruder can send the preselected response, making the verification equation valid, thereby being accepted as the authentic prover.
It is straightforward to demonstrate the statistical equivalence of the pairs (R, w) formed by the prover in the zero-knowledge protocol with a random equally probable request E and the pairs (R, w) formed by the intruder with an equally probable choice of values w and E’. Indeed, all possible triples (R, E, w) occur with equal probability, 2^−z q^−1, in the execution of the protocol involving the authentic prover. The intruder can statistically generate equivalent values (R, E’, w) without knowing the secret key. If such triples can be used to solve the discrete logarithm problem and compute the secret key for a given public key, it can be done without waiting for the real protocol to be executed the necessary number of times. The intruder can simply generate statistically equivalent data in the desired quantity and proceed to solve the discrete logarithm problem with equal success.
Stay curious, keep learning, and delve deeper into the Aleo ecosystem — the journey is just beginning. Join the community here:
