Fherret: Proof of FHE Correct-and-Honest Evaluation with Circuit Privacy from MPCitH

The major Fully Homomorphic Encryption (FHE) schemes guarantee the privacy of the encrypted message only in the honest-but-curious setting, when the server follows the protocol without deviating. However, various attacks in the literature show that an actively malicious server can recover sensitive information by executing incorrect functions, tampering with ciphertexts, or observing the client's reaction during decryption.

Existing integrity solutions for FHE schemes either fail to guarantee circuit privacy, exposing the server's computations to the client, or introduce significant computational overhead on the prover by requiring proofs of FHE operations on ciphertexts.

In this work, we present Fherret, a novel scheme leveraging the MPC-in-the-Head (MPCitH) paradigm to provide a proof of correct-and-honest homomorphic evaluation while preserving circuit privacy. This proof guarantees that the client can safely decrypt the ciphertext obtained from the server without being susceptible to reaction-based attacks, such as verification and decryption oracle attacks. Additionally, this proof guarantees that the server's evaluation maintains correctness, thereby protecting the client from IND-CPA-D-style attacks.

Our solution achieves a prover overhead of approximately 110-170 homomorphic evaluations of random functions from the function space F, while retaining a competitive verifier overhead of approximately 58-93 homomorphic evaluations and a communication size proportional to approximately 40 times the size of a function from F.

Furthermore, Fherret is inherently parallelizable because its MPCitH views can be computed independently, achieving a parallel computation overhead similar to a homomorphic evaluation of a single random function from F for both the prover and the verifier.