SNARK-friendly Symmetric Encryption

Problem Statement

We want an encryption scheme that would work well in arithmetic circuits (for SNARKS). So both the key and the input to the encryption should be $m\in \mathbb{F}^n$ vectors (with $\mathbb{F}$ being the field).

Solution

Keygen: generate key $x\in \mathbb{F}$ uniformly at random

Encrypt:

• Input: message $m\in \mathbb{F}^n$, key $x\in \mathbb{F}$

• Sample a nonce $k\in \mathbb{F}$ uniformly at random. Compute $a=hash(k, x)\in \mathbb{F}$

• Compute $r_i = hash(a, i)$ for $i=1, 2, \ldots, n$ and let $r\in \mathbb{F}^n$ be the resulting vector

• Compute $e = m + r$ (note $e\in \mathbb{F}^n$)

• Output $(k, e)$

Decrypt:

• Input: ciphertext $(k,e)$, key $x\in \mathbb{F}$,

• Compute $r\in \mathbb{F}^n$ based on $k, x$ as above

• compute $m=e-r$

• Output $m$

Total cost for encryption and decryption is: $\approx n\cdot G_{hash}$ where $G_{hash}$ is the number of gates one hashing costs.