Single-Server Private Outsourcing of zk-SNARKs

Succinct zero-knowledge arguments (zk-SNARKs) enable a prover to convince a verifier of the truth of a statement via a succinct and efficiently verifiable proof without revealing any additional information about the witness. A barrier to the practical deployment of zk-SNARKs is their high proving cost. With this motivation, we study server-aided zk-SNARKs, where a client/prover outsources most of its work to a single, untrusted server, while the server learns nothing about the witness, the statement, or even the final proof. We formalize this notion and show how to efficiently realize server-aided proving for widely deployed zk-SNARKs such as Nova, Groth16, and Plonk. The key building block underlying our designs is a new primitive, encrypted multi-scalar multiplication (EMSM), that enables private delegation of multi-scalar multiplications (MSMs). We construct an EMSM from variants of the LPN assumption in which the client does $O(1)$ group operations, while the server's work matches that of the plaintext MSM. We implement and evaluate our constructions. Compared to local proving, our techniques lower the client's computation by up to $18 \times$ and reduce the proving latency by up to $8 \times$.