Improving the Scalability and Deployability of Cryptographic Proof Systems

Abstract

Succinct zero-knowledge arguments (zk-SNARKs) enable a prover to convince a verifier of the truth of a statement via a succinct, efficiently verifiable proof without revealing any additional information about the witness. Despite their powerful capabilities, the practical deployment of zk-SNARKs remains limited to a narrow set of use cases due to high proving and verification costs. In this dissertation, we broaden the applicability of zk-SNARKs by introducing techniques that improve their concrete efficiency and enhance their viability for real-world deployment. First, we study proofs of training—a cryptographic tool that enables a verifier to check whether a (committed) model has been trained on a (committed) dataset as specified—and show how to realize this primitive efficiently for deep neural networks using recursive zk-SNARKs. Second, we study a further application of recursive zk-SNARKs to secure aggregation—a protocol that enables a server to learn the sum of clients' private inputs—and show how recursive zk-SNARKs can reduce the committee cost in state-of-the-art secure aggregation schemes. Finally, we introduce the notion of server-aided zk-SNARKs, which enable a prover (client) to outsource most of its work to an untrusted server while the server learns no information about the witness, the statement, or even the final proof. We propose a technique to achieve practical server-aided proving for several widely deployed zk-SNARKs in a single-server setting.