Encore: Aggregatable FHE-over-SNARK with Constant Proof Size

Verifiable fully homomorphic encryption (FHE) enables a client to verify the correctness of homomorphic computation by an untrusted server. A promising paradigm, FHE-over-SNARK, proves correctness at the FHE plaintext level and has proofs scaling at least logarithmically with circuit size. The alternative, proving at the ciphertext level (i.e., SNARK-over-FHE), forces non-arithmetic FHE maintenance operations into the proven relation and inflates circuit size by orders of magnitude, yet offers constant proof size. Proving FHE computation with the classical LPCP approach introduced by Bitansky et al., later enhanced in LUNA, follows this paradigm.

We revisit the LPCP framework and lift it into the FHE-over-SNARK paradigm, obtaining proofs of constant size, independent of the circuit size. Our key technique, an encoding-ciphertext multiplication, allows us to prove arithmetic relations on the plaintext level by preserving the homomorphism of the underlying messages of both the encodings and the ciphertexts. By leveraging this technique, our protocol leaves the costly maintenance operations entirely outside the proof relation. The resulting protocol, Encore, also natively supports SIMD operations and is agnostic to the circuit structure. The security of Encore is based on a multi-key variant of strict linear targeted malleability (LTM), which we show to be equivalent to the standard LTM assumption of prior LPCP-based SNARKs. We further present a distributed prover framework, d-Encore, so that the proof generation is distributed for efficiency to multiple sub-provers, while the verifier checks one succinct proof.

On a $2^{20}$-gate circuit mixing multiplication and addition, with SIMD ring dimension $2^{14}$, Encore produces a 4.64 MB proof in 9.38 single-core hours and verifies it in under 10 ms. This improves on Phalanx and Blind ZK by three to five orders of magnitude in prover time, proof size and verification time; on RAA by five orders of magnitude in proof size and 2.09× in prover time; on Laminate by 2.87× in proof size and 1.19× in prover time; and on Lasagne by 30.7× and 2.55×, respectively.