This is based on May’s IFT ZK Call. Visit the IFT ZK Meeting Notes for additional resources, and the video presentation.
In the past few years, the abbreviations FHE and SNARK has been treated as buzzwords. So, what are they? FHE and SNARK are classes of cryptographic techniques.
FHE
FHE is short for fully homomorphic encryptions. For decades, an open question was whether a FHE could be constructed. The first realized construction was done by Gentry in 2009. So, what is a FHE? A FHE allows for arithmetic operations to be performed in encrypted data in a meaningful manner. Of course, we can always add a scalar to a ciphertext produced via any encryption scheme, but it is unlikely meaningful. Rather, FHE ensures that the decryption of the result of arithmetic operations on our ciphertext is the same as if we had just performed the arithmetic operations directly to the plaintext (with some error term). Mathematically, \mathsf{Dec}(f(\mathsf{Enc(msg)})) = f(\mathsf{msg}).
At this point, FHE sounds like amazing and magical. But, it does have a couple of downsides: 1) error term grows with multiplication requiring bootstrapping, and 2) FHE does not provide any computational integrity guarantees. The lack of computational integrity means that a third-party that does computations on the ciphertext could use a different function than they claim.
SNARK
SNARK is short for \textbf{s}uccinct \textbf{n}on-interactive \textbf{arg}gument of \textbf{k}nowledge:
- Succinct. Short proof size and fast verification
- Non-interactive. No communication is required during proof generation and verification.
- Argument of knowledge. special kind of proof that the Prover possesses claimed knowledge.
SNARKs (appear) to first appear in the literature in the early 2010s. Often, SNARKs satisfy an additional property: zero-knowledge. Arguments can be made zero-knowledge by including blinding terms.
The downsides of SNARKs: 1) many SNARKs are not post-quantum secure (newer SNARKs are plausibly post-quantum secure), 2) SNARKs are rigid.
FHE with SNARK?
FHE’s lack of computational integrity can be mitigated by pairing FHE with a SNARK. But, we have options: 1) SNARK-FHE: should the SNARK be applied to the arithmetic operations done on the FHE ciphertext OR 2) FHE-SNARK: should FHE be checked on computations related to the plaintext?
It turns out that FHE-SNARK is more efficient than SNARK-FHE. 2^{20}-gate circuit takes 29 hours (with SNARK-FHE [2024/1684]) vs 20 minutes (FHE-SNARK [2025/302]). This can be attributed to SNARK and FHE using different algebraic structures. In particular, FHE ciphertext is an element in a cyclotomic rings while SNARKs work with values from small prime fields (often 128-bit, but there has been interest in 64-bit and 32-bit prime fields for SNARKs). Due to this, it is quite computationally expensive for SNARKs to be used to prove computations on the ciphertext. Instead, SNARKs can be used on commitments of the plaintext to maintain FHE’s security while bringing computational integrity.