Problem: Outsourcing ZK proof generation to an untrusted server

I have a secret witness $w$, and I need to generate a SNARK proof that $C(w) = 0$. Suppose I want to generate this proof on my phone, but I don’t have enough resources to do it. Therefore, I want to have the proof be generated by an untrusted server, but I want to keep my witness secret. How can we do this?

We know a few ways to solve this already:

Method 1: Collaborative proofs (https://eprint.iacr.org/2021/1530) (also GGJPS‘23, CLMZ‘23) – The prover splits the secret witness into several secret shares, and sends each share to a different server. This is secure against malicious servers, unless all $n$ servers collaborate.

But what if the servers cheat and collaborate?

Method 2: Using FHE (this is a classic way to offload work to an untrusted server) – Client generates FHE keys, encrypts the witness and sends it to the server. The server runs the proof-generation algorithm inside FHE, which is not very practical.

• Challenge: design a SNARK prover that is as FHE-friendly as possible. For example:
  • FHE likes shallow circuits
  • FHE likes to work modulo small primes

---

Notes:

• This paper shows that you can run FRI on linearly-homomorphically encrypted values; don’t need the full FHE.
• Another idea: We want to make the computation shallow because FHE works better on low-depth circuits. Maybe we can make the computation shallow by adding rounds of interaction with the client.
• Yet another idea: Take the witness, blind it somehow, say by adding a random vector, and have the server compute on the sum.
• Side note: An iPhone has 10 GPUs on it, but no existing SNARK implementations use them.