Learning with Aleo. Protocol with ZKP Based on the Open Key Agreement Scheme. Implementation Using the Diffie-Hellman Cryptosystem
Robust and user-friendly strict authentication protocols for remote users can be built on the basis of open key agreement schemes. Consider an implementation using the Diffie-Hellman scheme, in which the system parameters are a large prime number p and a primitive element α modulo p. In this scheme, each user selects a random secret key x and calculates the public key y using the formula
The public key is made publicly known, and theoretically, anyone can unequivocally calculate the value of the secret key x, although this is practically infeasible if p is, for example, no less than 3072 bits, and p — 1 contains a prime divisor q of at least 256 bits.
Consider a remote user authentication protocol with zero disclosure, which uses a value of α having an order modulo p equal to q, and includes the following two steps:
1. The verifier generates a random number k and calculates the value of their one-time public key
and
where y is the public key of the prover (i.e., the user whose authenticity is being verified), and then transmits the value U to the prover as their request, awaiting a response.
2. The prover checks if the equation
is satisfied (verifying that q is the order of the number U modulo p). If so, they calculate
and send Z to the verifier as their response to the received request. If the equation is not satisfied, the prover sends the response “Invalid Request”.
If the verifier receives the correct value of Z, i.e., the value they computed before sending their request to the prover, they conclude the authenticity of the prover. The verification of the number U at the second step is crucial. Without this check, the verifier could potentially calculate part or all of the prover’s secret key. Indeed, this can be done by sending as a request values of U’, the order of which q’ contains only small prime divisors of p — 1. Using the response:
and the baby-step giant-step algorithm, it is relatively easy to calculate:
By obtaining several such relations and using the Chinese remainder theorem, the secret key x can be easily calculated.
In the two-step protocol, the verifier can form as their request a random or specially selected number U’’, the order of which equals q, and receive the prover’s response:
which was not previously known to them. However, in this case, there is no leakage of information about the secret key. This can be demonstrated as follows. Suppose the verifier knows the value of the exponent k’’, such that
Under this assumption, the verifier can independently calculate Z’’. Thus, with additional information to what they already have, the prover’s response does not convey any information about the secret key to the verifier. This means that in the absence of additional information, there is zero leakage of information about the secret key.
To avoid burdening themselves with understanding such a proof of zero knowledge leakage about the secret key, one can implement a protocol based on the open key agreement scheme, using the calculation of a hash function value computed from the common one-time secret key Z. In this case, the protocol uses a specified hash function FH and includes the following two steps:
1. The verifier generates a random number k and calculates the value of their one-time public key
and
where y is the public key of the prover. Then, they calculate the hash function value of:
and send the pair (U, H) to the prover as their request.
2. The prover calculates
and
They then compare the values of H’ and H. If H’ = H, they send Z to the verifier as their response to the received request. If H’ ≠ H, the prover sends the response “Invalid Request”.
The downside of using a hash function is that it requires another algorithm. This can be significant in hardware implementation. However, the operation of calculating the hash function value is less computationally complex than the additional operation of raising the value of U to a large power q modulo p, which is performed to verify that the request value modulo p has an order equal to q.
It is easy to understand that if the first variant of the protocol based on the open key agreement scheme is implemented using a finite cyclic group of prime order, then it can dispense with the check that the received request has an order equal to q, since all values of such a group have an order equal to q. A possible implementation of two-step zero-disclosure protocols using groups of prime order is considered in the following subsection.
Stay curious, keep learning, and delve deeper into the Aleo ecosystem — the journey is just beginning. Join the community here:
