PPD and Where to find It?

This is a follow-up investigation of our PPD Project Plan back in Jan 2025.

PPD = Private Proof Delegation

Recall that we are in the situation where a weak client, who holds some secret witness to a (public) statement, would like to generate a (public verifiable) zero-knowledge proof of the knowledge of the witness (and that it satisfies some relation), but not able to do so, due to resource constraint such as low computational power, shortage of power (battery life), or low memory. While computational power or battery life are somewhat reasonable to circumvent, memory cap remains a hard constraint of such weak client.

In such a situation, the weak client, would like to find a way to delegate the proof generation to a strong server, while, at the same time, would like to keep the witness its own secret.

We call such service "Private Proof Delegation; and our team embarked on the quest to fulfill the wish of the client.

Existing PPD Solution

PPD is an instance of Secure 2-party Computation (2PC) and is solvable using Secret-Sharing-based MPC technique such as Collaborative zk-SNARKs (coSNARKs), firstly introduced in 2021, and used for Private Proof Delegation in 2023. Software-wise, such solutions are available at TACEO and EZKL.

Roughly speaking, coSNARKs have 2 deployment model: client delegates proof generation to 2-3 coSNARKs servers, or client participate as one of the coSNARKs servers. The first model encounters trust issue in the coSNARKs servers while the 2nd model takes the PPD issue back to square one: the client needs to have the capacity of a server.

Hence, we looked into Fully Homomorphic Encryption, FHE, -based solutions and investigate the landscape of FHE-SNARKs.

Existing FHE-SNARKs

As it can be summarized, a modern SNARK is composed of two components: Polynomial Interactive Oracle Proof (PIOP) and Polynomial Commitment Scheme (PCS). Thus composing FHE-SNARKs is equivalent to compose FHE-PIOP + FHE-PCS.

What's the general issues?

Big field size is a problem!

The first issue turned out to be that field size matters, A LOT! The MHEGA project by TACEO demonstrated infeasibility of computing FHE-FFT on big prime field, where the plaintext space has to be 254 bits which pumped up the ciphertext space of HE to be 1045 bits and even with that can only accomodate one level of HE multiplication. The very big ciphertext bitwidth constitute extremely high computational cost even though MHEGA had done many tricks to cut down multiplication depth of the FFT however at the cost of requiring many rotation keys.

Here we cite their MHEGA project's benchmarking results:

The results are somewhat sobering. The overhead of homomorphic encryption is more than 6 orders of magnitude despite using the optimized algorithms for evaluating the matrix-vector multiplications. A still comparably small FFT of size 32768 blows up from 12.35 ms without encryption to 1514.2 s with encryption.

Unfortunately, CPU overhead is not the only drawback of using HE, RAM requirements are also huge. The final benchmark with size 32768 required nearly everything of the 100 GB RAM of the benchmark server. The reason for that is (among the general size of HE ciphertexts) the size of the many key-switching keys required to evaluate all the ciphertext rotations in the babystep-giantstep optimized diagonal method. These need to be created by the party knowing the decryption key, thus, when HE is used for outsourcing computations, the communication of these keys already requires to upload several tens of GBs of data.

Small field size is feasible!

OK, let's forget about big field size and focus on small field size such as Goldilocks. This means that we can only do FHE-SNARKs for field-agnostic SNARKs such as STARKs or the similar.

There is a series of FHE-STARK (FHE-FRI-ish) in the recent years that shows feasibility for FHE-FRI-PIOP:

• In 2023, How to Prove Statements Obliviously?. This is the earliest that shows how to compute a FRI-PIOP on "hidden values". This means that we can compute an encrypted FRI-PIOP using witness encrypted under FHE. This result is somewhat generic and seminal.
• Also in 2023, HELIOPOLIS: Verifiable Computation over Homomorphically Encrypted Data from Interactive Oracle Proofs is Practical (Source code available at https://github.com/antoniocgj/HELIOPOLIS). This work is concurrent to the previous paper but caters for aligning FHE and FRI parameters. Here we cite that

  Aligning the security parameters of HE and FRI is a difficult task for which we introduce several optimizations. We demonstrate their efficiency with a proof-of-concept implementation and show that we can run FRI's commit phase for 4096 encrypted Reed Solomon codewords with degree bound

  $2^{11}$ in just 5.4 seconds (using 32 threads) on a c6i.metal instance using less than 4GB of memory. Verification takes just 12.3 milliseconds (single-threaded) for the same parameter set and can be reduced to just 5.6ms with parameters optimized for the verifier.

• In 2024, Blind zkSNARKs for Private Proof Delegation and Verifiable Computation over Encrypted Data further improved HELIOPOLIS, and here we cite them that "we show for the first time it is practical to privately delegate proof generation of zkSNARKs to a single server for computations of up to
  $2^{20}$ R1CS constraints." One of the authors gave a presentation here that we highly recommend watching for an intuition. Note that the source code is available here https://github.com/KULeuven-COSIC/blind_zkSNARKs/. But the FHE-PIOP computation is only an estimation.
• Most recently, in 2025, FHE-SNARK vs. SNARK-FHE: From Analysis to Practical Verifiable Computation claims that "We design an FHE-friendly SNARK that is: a) 3x lower multiplicative depth than FRI-based SNARKs; b) Compatible with FHE SIMD operations. Based on this novel SNARK, we construct an FHE-SNARK scheme that has: a) Stronger security: resistant against input-dependent attack; b) 8x speedup: 3.6-hour proof generation for
  $2^{20}$-gate circuits on a single core CPU (vs. 29 hours in the state-of-the-art); c) Practical verification: 65.3 MB proofs with 2.7 seconds verification (single core)."

It is too good to be true (yet!)

All the work above however only show how to compute FHE-PIOP on small field but they are only half the way to the true PPD.

In the following screenshot we highlight the gist of the FHE-SNARKs so far:

Per the diagram the Merkle Tree roots are computed from the ciphertexts of the witness not the witness itself. Hence the verifier needs to decrypt to be able to verify the generated proof, which makes the proof only designated verifier (to the client who has the FHE key). To circumvent the issue, the client needs to decrypt the queries and attach a proof of decryption.

Yes, we are somewhat back to square one, the client still needs to generate a zk-SNARK albeit of a smaller size. This at the same time also change the zk-SNARKs scheme itself to a new scheme.

What now, from here?

It is unfortunate that the best known methodology is only half the way to PPD:

We need to continue our investigation for PPD which should be now focused on the FHE-PCS part:

Several potential paths include:

• Perform scheme switching from arithmetic (BFV) to binary (TFHE) and compute SHA256 or Keccak inside FHE, this path is of high doubt to be efficient;
• Perform arithmetic based hash function such as Poseidon on Goldilocks, this path is vaguely feasible, and keeps the zk-SNARK somewhat the same;
• Change the zk-SNARKs scheme to a lattice-based PCS and leverage the similar structure of the HE and the PCS for potential efficiency.

Misc Notes

• Albeit in this note we highlight the difficulties of generating FHE-SNARK, this assumes the extended witness is already available, yet, in fact, computing witness extension could be problematic itself in some cases.
• We mainly focused on algorithmic development, we believe that hardware acceleration should significantly speedup the runtime.
• We are not strictly in FHE-SNARK space, namely, we can leverage client interaction to some extent for computation, e.g. if we pass back the ciphertext and ask the client to do the hash (in a semi-honest settings) then the hashing part is efficient. But client communication is an issue if we abuse this. Hence finding a balance is important here.
• Whereas in this note we focus mainly on FHE-PIOP, we also created a slidedeck that may provide a bigger picture of PPD.