Multi-Round Protocols with Zero-Knowledge Proof
Multi-round protocols with zero-knowledge proof involve repeated execution of three standard steps:
1. The prover generates a one-time random secret key and calculates a corresponding one-time public key, often termed as a commitment, which is then transmitted to the verifier.
2. The verifier generates a binary request (r = 0 or r = 1) with equal probability (0.5) and sends this bit r to the prover.
3. The prover computes a response w based on the request and sends w to the verifier.
After each three-step round, the verifier inserts the received response into a specific verification relationship that includes the values of the commitment, public key, and request r. If this relationship is satisfied, the verifier deems the current response correct.
Let us discuss a few of these protocols:
The Fiat-Shamir Protocol
The Fiat-Shamir protocol is based on the complexity of extracting square roots modulo a composite number with at least two large prime factors, under the condition that the factorization is unknown. The prover selects two large primes p and q, calculates the modulus n = pq, and then chooses a random number s (1 ≤ s ≤ n — 1) as their private secret key, computing
y = s² mod n
Here, y serves as the public key, asserting that the prover knows the square root of y.
The protocol consists of z iterations of the following steps:
1. The prover selects a random number k (1 ≤ k ≤ n — 1), calculates
u = k² mod n
(the commitment), and sends it to the verifier.
2. The verifier sends a randomly chosen binary bit r (r = 1 or r = 0) to the prover.
3. The prover calculates
w = ksr mod n
and sends it to the verifier. If r = 1, w = ks mod n. If r = 0, then w = k. The value k is discarded after each round or at the end of the protocol.
The verifier considers the response correct if the relationship
w² = uy^r mod n
is satisfied. During the protocol execution, z steps are performed. The probability that an intruder (who does not know the secret s) can give a positive response in one round is 2^−1, thus the probability of being mistaken for a user who knows the secret s is 2^−z. By choosing a sufficiently large number of verification rounds, the probability of deception can be made arbitrarily low.
There are two potential actions for an intruder in a single round:
1. In the first scenario, the intruder selects a random k and sends u = k² mod n to the verifier. If the request r = 0 is received, the correct response w = k is sent. However, the intruder cannot correctly respond to the request r = 1.
2. In the second scenario, the intruder selects a random k and sends
u’ = k²/y
If the request r = 1 is received, the response w’ = k will be accepted as correct by the verifier since
u’ y = (k²/y) y = k² = w’² mod n
However, the intruder cannot correctly respond to the request r = 0.
In the best case, an intruder can only correctly respond to one question, and with a 1/2 probability, the deception attempt is detected in a single round.
In this protocol, there is no leakage of key information. Indeed, for the verifier’s request r = 0, the prover sends a random number k, which the verifier could have independently generated. For the request r = 1, the prover sends a random number w, but the verifier could independently generate a random number w’ and calculate a random value
u’ = w’²/y mod n
If the verifier can calculate the square root of a random u’, then they can easily compute the secret key. Thus, the data received by the verifier from the prover during the protocol execution do not offer any new means for calculating the secret key. This is how the absence of secret information leakage during the protocol is understood.
Protocol Based on the Difficulty of Discrete Logarithm
In this protocol, the prover’s public key is calculated from their personal secret key x using the formula y = α^x mod p, where p is a sufficiently large prime number; α is a number of sufficiently large prime order q modulo p.
The zero-knowledge proof protocol may include z iterations of the following steps:
1. The prover selects the current one-time secret k (k < q), calculates the value of the commitment
R = α^k mod p
(serving as a one-time public key), and transmits R to the verifier.
2. The verifier sends a randomly chosen binary bit r (r = 1 or r = 0) as their request to the prover.
3. The prover calculates a response to the request as a number w using the formula
w = k + rx mod p
and sends it to the verifier.
The verifier verifies the fulfillment of the following verification relationship:
Ryr ≡ α^w mod p.
There are two potential actions for an intruder:
1. The intruder may select an arbitrary number k and send the commitment value
R = α^k mod p
to the verifier. If the request r = 0 is received, the correct response w = k is sent. However, there is no correct response to the request r = 1.
2. In another scenario, the intruder selects an arbitrary value w and sends the verifier the commitment value
R ≡ y^−1α^w mod p
If the request r = 1 is received, the response w will be accepted as correct since the verification equation
Ryr ≡ α^w mod p
is satisfied. However, the intruder cannot correctly respond to the request r = 0.
In each scenario, the intruder can correctly respond with a probability of 1/2. The probability that the intruder will give the correct response in all z rounds is 2^−z. Since the intruder cannot impose repeated authentication procedures on subscribers, values of z = 24, z = 32, and z = 40 may be sufficient for many practical applications.
Stay curious, keep learning, and delve deeper into the Aleo ecosystem — the journey is just beginning. Join the community here:
