Exploring ZK Protocol Based on Sequential Squaring with Aleo
1. ZK Protocol Based on Sequential Squaring
Consider a two-pass protocol with ZK based on the difficulty of the factorization problem, for which the proof of zero knowledge leakage is relatively straightforward. The prover’s public key is a natural number n, the product of two large prime numbers r and q, which constitute his private secret. The idea of the proof that there is no leakage of information about the secret key is that the prover transmits to the verifier a value that was calculated before it was computed by the prover; thus, no new information is transmitted to the verifier. The protocol includes the following two steps:
1. The verifier generates a random number a < n and a ρ-bit number k, where:
(the value of ρ is chosen based on the communication channel’s delay time δ). Then, using the method of sequential squaring, they calculate the value:
and transmit the pair of values a and k to the prover as their request, awaiting a response;
2. The prover performs two consecutive exponentiation operations, quickly calculating the values:
where L(n) is the generalized Euler’s totient function of n, and
They immediately send the value T to the verifier as their response to the received request. If the verifier receives the correct value T within a time interval not exceeding a certain threshold value ∆, for example ∆ = 10δ−1000δ (where δ is the communication channel’s delay time), they conclude the authenticity of the prover. The value of ∆ is chosen to be significantly greater than δ. The bit length of k is chosen so that the process of calculating the value T without knowing the factorization of the modulus requires an attacker to perform computations for a duration exceeding ∆. Without the knowledge of the modulus’s factorization, the calculation of
is performed by sequential squaring, which requires k squarings (multiplications) modulo n.
2. Practical Application Considerations
The practical application of the authentication protocol described in the previous subsection requires consideration of the potential attacker’s computational resources. If it is assumed that the attacker may use specialized high-performance computers (the use of multiprocessor computers does not have an effect since the process of sequential squaring cannot be parallelized), the verifier needs to choose longer numbers k. This will require more time to calculate the value T. The chosen bit length of k is also determined by the performance of the communication channel used in the protocol. The faster the channel, the smaller the value of ∆ can be chosen, i.e., the smaller the bit length of k can be used. This will reduce the computation time required by the verifier before sending the request to the prover. Typically, in practice, one user connects with many other users whose authenticity they wish to verify. This means that they must establish their threshold value ∆ for each verified user or take a common threshold value ∆_common, equal to the maximum time required to receive a response from all verified users. In the first case, individual configuration of the authentication protocol parameters is required, but it achieves a lower average computation time on the first step. In the second case, the need for individual parameter configuration is eliminated, but the computation time on the first step is increased. In practical use of this protocol, a method of precomputations may be applied, which consists of the verifier precalculating a set of values (a, k, T) that will subsequently be used for authenticating remote users. It should be noted that the use of the technical parameter of the communication channel related to its performance introduces significant restrictions on the application area of this protocol.
Stay curious, keep learning, and delve deeper into the Aleo ecosystem — the journey is just beginning. Join the community here:
