I am currently implementing verifiable encryption in Cairo RM. Some team members have raised questions regarding it. In this post, I will provide a more detailed explanation of the implementation specifics for different types of RMs (Taiga, Cairo, and Risc0), despite already having a concise description in Taiga Doc
What is the Verifiable Encryption?
Verifiable encryption is an encryption scheme where one can prove that an encrypted plaintext satisfies certain properties, or relations. While a secure encryption scheme should not reveal any information about the original message, there are cases where it is necessary to check specific properties of the encrypted content before processing it. Verifiable encryption enables a verifier to validate these properties without compromising security. By providing a valid verifiable encryption proof, we can ensure that the ciphertext is properly formatted and can be successfully decrypted with the correct private key.
Why do we need the Verifiable Encryption in shielded RMs?
In Zcash and MASP, note encryption is performed out-of-band, where the ciphertext is not constrained by the proof system but rather serves as a classic encryption appended to transactions. This is acceptable because the sender and creator of the note are the same entity. The sender has no incentive to create a valid transaction with an invalid ciphertext (as validators cannot verify its validity), otherwise, the receiver could claim that they did not receive the note.
In the current RM design, transactions and resources are typically created and sent by different parties, including various users and third-party solvers. Without verifiable encryption, a dishonest party could provide an invalid encryption to other parties or just discard the ciphertext without affecting his own profits. Therefore, we need a mechanism to verify the encryption and ensure that the receiver can decrypt their owned resources.
Where should the Verifiable Encryption be located?
It depends on we want the Verifiable Encryption to be mandatory or optional.
If Verifiable Encryption is mandatory, all resources must be encrypted and included in the compliance proof. If it is optional, the application designer has the responsibility to decide how resources are encrypted in resource logic, providing more flexibility.
The general Verifiable Encryption scheme
The Verifiable Encryption scheme is typically constructed using Hybrid Encryption, which combines the efficiency of symmetric encryption with the convenience of public key cryptography. Anyone can encrypt data using the receiver’s public key, but only users with the private key can decrypt it.
Diffie–Hellman key exchange is chosen in practice to generate the symmetric key, and symmetric encryption depends on RM backends for efficiency considerations.
- Encryption
- symmetric\_key = DH(sender_{sk}, receiver_{pk})
- ciphertext = Symmetric\_Encryption(plaintext, symmetric\_key)
- Decryption
- symmetric\_key = DH(receiver_{sk}, sender_{pk})
- plaintext = Symmetric\_Decryption(ciphertext, symmetric\_key)
Specific Verifiable Encryption implementations for different backends
The DH would be used to generate the key for all RMs, with the only difference being that they could be over different elliptic curves depending on the backends. In non-circuit world, AES is commonly used for symmetric encryption. However, AES in circuits is highly inefficient, especially for backends operating over large finite fields like halo2 and cairo-stark. The encryption can be constructed using algebraic hash functions like Poseidon or Rescue instead of the traditional AES.
Verifiable Encryption in Taiga RM
We can use the Poseidon permutation of width 3 in the DuplexSponge mode.
- Key generation(DH key exchange)
1.1 Get the receiver’s public key K = [k] G
1.2 Generate a random r \in \mathbb{F}_q
1.3 Compute the shared encryption key K_s = [r]K = (K_x, K_y) \in \mathbb{F}_p^2 - Encryption
The encryption message: M \in \mathbb{F}_p^l
The encryption nonce: N < 2^{128}
2.1 Pad the message with zero to a multiple of RATE(2)
2.2 Init the Poseidon state S = (K_x, K_y, N + l * 2^{128})
2.3 Repeat for 0 \le i \le \lceil l / 2 \rceil
a) Iterate Poseidon permutation(P) on state S: S \leftarrow P(S)
b) Absorb two elements of the message: S[0] = S[0] + M[2i]; S[1] = S[1] + M[2i + 1]
c) Output two elements of ciphertext: C[2i] \leftarrow S[0]; C[2i+1] \leftarrow S[1]
2.4 Squeeze on S last time to get the MAC: S \leftarrow P(S)
2.5 Add the MAC to the ciphertext: C.add(S[0]) - Decryption
The decryption process is almost identical to encryption, except for the final step of verifying the MAC.
Reference:
Poseidon Paper
Duplexing the Sponge
Encryption with Poseidon
Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols
Verifiable Encryption in Cairo RM
Ideally, we can reuse the same construction in Taiga RM for Cairo RM. Unfortunately, we cannot extract the poseidon permutation from Cairo to construct poseidon encryption in Juvix since it is a built-in function there. We could potentially use poseidon hash instead of poseidon permutation, but this would sacrifice some performance. According to 2.3.b in Taiga encryption, each poseidon permutation can absorb two elements whereas each poseidon hash can only absorb one element. This means that by making this replacement, we would double the number of rounds required. While it may not be an optimal solution, using poseidon hash should still be fine as it is quite efficient.
Encryption Algorithm
The encryption message: M \in \mathbb{F}_p^l
The encryption nonce: N < 2^{128}
- Init the Poseidon state S = poseidon\_hash\_many(K_x, K_y, N + l * 2^{128})
- Repeat for 0 \le i \le l-1
a) Absorb one element of the message: S = S + M[i]
b) Iterate Poseidon single hash(H) on state S: S \leftarrow H(S)
c) Output one element of ciphertext: C[i] \leftarrow S - Squeeze on S last time to get the MAC: S \leftarrow H(S)
- Add the MAC to the ciphertext: C.add(S)
Verifiable Encryption in Risc0 RM
The Risc0 zkvm is based on the STARK system using a small finite field, and the sha2 benchmark shows its efficiency over bit-wise operations. It should be straightforward to benchmark AES in Rust within Risc0 zkvm. If the performance is acceptable, we can consider utilizing classic AES encryption for constructing the verifiable encryption scheme.