Alex Ozdemir
May 13, 2022 at 11:00 AM on Zoom / Soda Hall
Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets
Abstract: We generalized zk-SNARKs (which support zero-knowledge proofs about one party's secrets) to collaborative zk-SNARKs (which support zero-knowledge proofs about many parties' secrets). We construct collaborative zk-SNARKs by lifting conventional zk-SNARKs into secure protocols among N provers to jointly produce a single proof over the distributed witness. We optimize the proof generation algorithm in pairing-based zk-SNARKs so that algebraic techniques for multiparty computation (MPC) yield efficient proof generation protocols. For some zk-SNARKs, optimization is more challenging. This suggests MPC "friendliness" as an additional criterion for evaluating zk-SNARKs. We implement three collaborative proofs and measure the cost of proof generation. We find that over a 3Gb/s link, security against a malicious minority of provers can be achieved with *approximately the same runtime* as a single prover. Security against N−1 malicious provers requires only a 2× slowdown. This efficiency is unusual since most computations slow down by orders of magnitude when securely distributed. This efficiency means that most applications that can tolerate the cost of a single-prover proof should also be able to tolerate the cost of a collaborative proof.
Bio: Alex Ozdemir is a Phd student at Stanford, studying cryptography and formal methods. Lately, he’s been investigating how cryptographic proof systems can be made more useful, sometimes by using techniques from formal methods and programming languages.