Presenting zk-AES: ZK Prover for Symmetric Encryption (Part 2)

Encryption and decryption operations cannot be performed on a blockchain because that would mean revealing our key on the blockchain, which is undesirable. If we could produce an easily verifiable proof that an encryption operation was performed and then simply verify that proof on-chain, then we wouldn’t need to reveal the key at all. zk-SNARKs can help us in producing the easily verifiable proof.

The following article explains AES and it’s different modes, followed by how we are generating a zk-SNARK for the same.

The Advanced Encryption Standard (AES) is a specification of data encryption. AES is a block cipher in which the block size is always 128 bits and key size can be 128 bits, 192 bits or 256 bits. AES is a symmetric key algorithm.

There are 5 different modes of operation of block ciphers:

1. Electronic Codebook (ECB) — The plaintext is divided into blocks, and each block is encrypted separately. Encryption and decryption both are parallelizable.
2. Cipher Block Chaining (CBC) — Each block of plaintext is XOR’d with previous ciphertext before encryption. An initialization vector (IV/Nonce) is used for the first block. Encryption is not parallelizable whereas decryption is.
3. Cipher Feedback (CFB) — It is similar to CBC and in addition turns the block cipher into a self-synchronising stream cipher. IV is used for the first block. Encryption is not parallelizable whereas decryption is.
4. Output Feedback (OFB) — OFB converts block cipher into a synchronous stream cipher. Keystream blocks are generated which are then XOR’d with plaintext blocks to get the ciphertext. IV is used in this mode as well, Encryption and decryption both are not parallelizable.
5. Counter (CTR) — This mode also converts block cipher to a stream cipher. Next keystream blocks are generated by encrypting successive values of a counter. IV is concatenated with the counter which is then used to generate the keystream. Encryption and decryption both are parallelizable.

Out of the above 5, the former two require padding in the original message to make the plaintext’s length a multiple of block size (128 bits in case of AES). The rest of the modes do not require padding, as these modes XOR the plaintext blocks with keystreams, and the last partial plaintext block is XOR’d with the first few bytes of the keystream.

The above modes are also called cipher modes, as they hide the plaintext but they don’t validate the authenticity of encrypted data. There are other modes called authenticated encryption with additional data (AEAD) modes. These modes provide hiding and validation in a single cryptographic operation.

The Galois/counter mode (GCM) combines the CTR mode of encryption and the Galois mode of authentication. The authentication tag is created by sending blocks of data to the GHASH function followed by encrypting the output. Encryption and decryption both are parallelizable. The GCM method, though, is prone to the nonce misuse attack where if more than two messages are encrypted using the same IV, it can completely void the confidentiality of these two messages.

AES-GCM-SIV provides similar performance to AES-GCM and on top of that, it provides nonce-misuse resistance. AES-GCM-SIV creates the internal IV by using the additional authenticated data (AAD) and the plaintext. AES-GCM-SIV uses the POLYVAL hash function instead of the GHASH function as used by AES-GCM.

We, at Electron Labs, have implemented the AES-GCM-SIV encryption scheme in circom in order to be able to generate zk-SNARK for encryption, which can then in turn be verified on-chain. We chose AES-GCM-SIV because it is an NIST approved encryption scheme even though it is not SNARK friendly.

Our implementation is heavily inspired from this C implementation of AES-GCM-SIV. Even though this encryption scheme is essentially a stream cipher and doesn’t require padding, we do require the input plaintext length to be a multiple of 128 bits. As in the C implementation, we also use lookup tables for Rijndael s-box values rather than using bit slicing technique as used by Rust’s implementation of AES. As POLYVAL is defined over GF(²¹²⁸), it did not cause any implementation issues for us as circom’s prime field is bigger than that. The major challenge of the circom implementation was defining all the operations at bit level rather than byte level as operations like bitwise XOR on byte level generate non quadratic constraints. The input to the circuit is:

• The key, K1, 256 bits (32 bytes)
• The Nonce, N, 128 bits (16 bytes)
• The additional authenticated data, AAD, *m**8 bits (m bytes, m%16 == 0)
• The plaintext, MSG, *n**8 bits (n bytes, n%16 == 0)

The output of the circuit is

• CT, the concatenation of the ciphertext along with the authentication tag, (n+16)*8 bits (n+16 bytes)

The following table shows benchmarks for different input sizes. All computations were done on a 8-core 2.3GHz, 32G RAM machine (AWS t2.2xlarge instance).

Benchmarks

Check out our implementation in this repository. We are excited to see how the community uses zk-AES for different purposes. We will be happy to support any teams wanting to use this in their projects.