Exploring Two-Step Zero-Knowledge Protocols with Aleo — part 2
1. Using the ElGamal Public Key Encryption Algorithm
Let’s examine the implementation of a zero-knowledge secret disclosure protocol based on the ElGamal public key encryption algorithm. In this algorithm, the public key is of the form
where p is a large prime number (1024 bits or more) such that the factorization of p — 1 includes a prime divisor of at least 160 bits; α is a primitive root modulo p. This method essentially represents a hybrid cryptosystem, where secret keys are distributed according to the Diffie–Hellman protocol, and message encryption is performed by modularly multiplying the message with the secret key.
The encryption of a message T, intended for the holder of the public key y, is performed as follows:
1. Generate a random number k, which serves as a one-time secret key of the message sender.
2. Compute the number:
it’s a one-time public key of the sender.
3. Using the recipient’s public key y, calculate a one-time shared secret key:
4. Encrypt the message M by multiplying it with the one-time secret key:
5. Send the ciphertext to the recipient as a pair of numbers (R, C).
The open encryption procedure using the public key y is denoted as Gamal_Encr(M, y). The recipient of the ciphertext (R, C), using their private key x, performs the decryption process Gamal_Decr(R, C, x), which involves the following steps:
1. Compute the one-time shared secret key:
2. Using the Extended Euclidean Algorithm, calculate the inverse value Q^-1, opposite to the value Q modulo p.
3. Decrypt the message M by multiplying the value C with the integer Q^-1:
ElGamal algorithm uses random values for encryption, implementing a probabilistic encryption procedure where multiple different ciphertexts corresponding to the same message M can be generated, all decrypting to the same value M.
Similarly to the protocol proposed in [4], we construct an authentication protocol with zero-knowledge based on the ElGamal algorithm using a 256-bit tag m. The tag is the least significant 160 bits of the prover’s public key y (i.e., specified as m = y mod 2¹⁶⁰), described as follows:
1. The verifier generates a random message M of size |M|, satisfying the condition:
Then, they encrypt the message M along with the attached tag m, i.e., encrypt the bit string M||m, using the prover’s public key y according to the formula:
They then send the pair (R, C) to the prover as their request, awaiting a response.
2. The prover decrypts the ciphertext (R, C) using their private key x:
where m’ is the bit string defined by the least significant 160 bits of the decrypted value, and checks if m’ equals m. If m’ equals m, the prover sends the obtained M’ back to the verifier as a response to the request. Otherwise, the prover responds with “Invalid Request.”
If the verifier’s intention is not to gain information about the prover’s secret key, they correctly perform the first step of the protocol using the specified tag m, which they attach to the selected message M and then execute the encryption procedure. In this case, upon decrypting the ciphertext, the prover will recover the original message, see the specified tag, discard it, and obtain M’ = M. The verifier then receives a known value from the prover and concludes the prover’s authenticity. The probability of the relation m’ = m being fulfilled for a randomly chosen request is negligibly small and equal to 2^-160.
2. Protocol Based on the Rabin Cryptosystem
In the Rabin public key encryption algorithm, calculations are performed modulo n = pq, which is used as the public key. The strong prime numbers p and q make up the private secret key and satisfy the conditions: p ≡ 3 mod 4 and q ≡ 3 mod 4. These two conditions simplify the decryption process compared to when values of p and q not meeting these conditions are chosen.
Encryption of a message M < n is done by squaring M modulo n:
The decryption process involves extracting the square root of the ciphertext C modulo n. First, the roots of C modulo p and q are calculated:
From these four values, four possible roots of C modulo n are computed:
where:
and
A two-step zero-knowledge protocol based on the Rabin public key encryption algorithm uses a 128-bit tag m, taken as the least significant 128 bits of the prover’s public key, i.e., m = n mod 2¹²⁸, and is structured as follows:
1. The verifier generates a random message M of size |M|, satisfying
and encrypts the message M along with the attached tag m, i.e., encrypts the value M||m, using the formula:
and sends this value C to the prover as a request.
2. The prover decrypts the ciphertext C using their secret key (p, q) by calculating the four square root values of C: M1, M2, M3, and M4. Each of these values is represented as Mi’ ||mi’, where mi’ is the bit string defined by the least significant 128 bits of the i-th root (i = 1,2,3,4). The prover then checks if mi’ equals m for any of the four values i. If so, the corresponding value Mi’ is sent back to the verifier as a response to the request. If mi’ ≠ m for i = 1,2,3,4, the prover responds with “Invalid Request.”
The use of a predefined tag allows the prover to identify the original message, thereby sending back to the verifier exactly the value known to the verifier. This ensures zero information leakage about the secret key when the prover sends their response to the verifier.
Stay curious, keep learning, and delve deeper into the Aleo ecosystem — the journey is just beginning. Join the community here:
