Exploring Two-Step Zero-Knowledge Protocols with Aleo
1. Protocols Based on Public Key Encryption Algorithms
Zero-knowledge protocols can be implemented using well-known public key encryption algorithms. These protocols employ a secret key. The individual who correctly performs the encryption process will find that the decrypted message only confirms the knowledge of the secret key associated with the public key. However, an adversary could potentially choose any value, claim it as the ciphertext of a message M, and request the public key holder to decrypt it. If the latter complies and reveals the decrypted message, there’s a risk of inadvertently leaking information about the secret key. It’s impossible to assert that the message doesn’t contain information about the secret key since some data has been revealed. Therefore, zero-knowledge protocols necessitate a mechanism that allows the public key holder (the prover) to ensure, before revealing the decrypted message, that the verifier already knows it.
Such a mechanism could be hashing algorithms or predetermined tags embedded in the original messages. The first approach is used in zero-knowledge protocols, where a public encryption algorithm, denoted as Publ_Encr, is employed. The verifier can send the prover a random message M, first encrypting it with the prover’s public key, resulting in a ciphertext
where P is the prover’s public key. Only the authentic prover, who knows the secret associated with the public key P, can read this message. Upon receiving C as a random request, the prover must decrypt the ciphertext and send the original message M back to the verifier, who already knows this message. Since the verifier receives no new information, there’s no leak of the prover’s private secret key. Meanwhile, the verifier gains assurance of the prover’s authenticity.
To prevent the verifier from arbitrarily choosing a random request, the protocol mandates the formation of the request as a pair of values (C, H), where C is the ciphertext obtained by encrypting a message M with the prover’s public key, and H is the hash value computed from M using a specified hash function
When receiving the request (C, H), the prover can verify that the message M decrypted from the ciphertext C is known to the verifier by calculating the hash function of the decrypted message and comparing it with the second element of the request.
In a two-step zero-knowledge protocol, the process is as follows:
1. The verifier selects a random message M, encrypts it using the specified public encryption algorithm Publ_Encr and the prover’s public key P, resulting in the ciphertext
The verifier then computes the hash value
using the specified hash function and sends the pair (C, H) to the prover as a request.
2. The prover decrypts the ciphertext C using their private key, obtaining the decrypted message M’. They then calculate the hash value
and compare H’ with H. If H’ equals H, the prover sends M’ back to the verifier as their response.
The verifier, upon receiving M’, compares it with M. If M’ equals M, it concludes the prover’s authenticity.
Another approach proposed involves the use of tags m embedded in the encrypted message. The presence of such tags in the decrypted message M’ serves as evidence that M’ was known to the verifier at the time of request formation. The size of the tags, ranging from 80 to 512 bits, ensures that the probability Pr(m) of decrypting an improperly formed request with the tag present is negligibly small:
The use of tags eliminates the need for additional hash functions and hash code computations by both the verifier and the prover
2. Protocol Based on RSA Cryptosystem
Let’s consider a zero-knowledge protocol constructed using the RSA public key encryption algorithm, where the public key is a pair of numbers (n, e). The first number is the product of two strong prime numbers r and q, randomly generated, and the second is a 32-bit value chosen to be coprime with
where LCM is the least common multiple of r — 1 and q — 1; L(n) represents the value of the generalized Euler’s function for n. The secret key is calculated as follows:
After calculation, the secret values r and q are destroyed. The open encryption procedure for a message M < n is described by the formula
The decryption of the ciphertext C is described as
The correctness of this decryption procedure is easily proven using the generalized Euler’s theorem, which states that for any number M coprime with n, the following relation holds:
Consider a two-pass zero-knowledge protocol based on this encryption algorithm using a 128-bit tag
The tag consists of the 128 least significant bits of the prover’s public key. The protocol is described as follows:
1. The verifier generates a random message M of size |M|, ensuring
Then, they encrypt the message M along with the attached tag m, i.e., they encrypt the bit string M||m, using the prover’s public key (n, e), as per the formula
and send this value C to the prover as their request, awaiting a response.
2. The prover decrypts the ciphertext C using their private key d, as per
where m’ is the bit string defined by the least significant 256 bits of the decrypted value. The prover checks if m’ equals m. If m’ equals m, the prover sends the obtained M’ to the verifier as a response to the request. Otherwise, the prover responds with “Invalid Request.”
If the verifier receives the correct M’ = M as a response, i.e., the value they generated in the first step of the protocol before sending their request to the prover, it is taken as proof of the prover’s authenticity.
In this protocol, the use of a predefined tag m is crucial, enabling the prover to verify that the response value M’ is already known to the verifier. The fact that it’s already known to the verifier suggests that the verifier isn’t attempting to obtain a signature for some message using a blind signature mechanism, nor are they trying to execute an adaptive chosen ciphertext attack or any other form of attack.
Stay curious, keep learning, and delve deeper into the Aleo ecosystem — the journey is just beginning. Join the community here:
