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 mFnm\in \mathbb{F}^n vectors (with F\mathbb{F} being the field).


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


  • Input: message mFnm\in \mathbb{F}^n, key xFx\in \mathbb{F}

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

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

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

  • Output (k,e)(k, e)


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

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

  • compute m=erm=e-r

  • Output mm

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

Last updated