PhD Defense: Improving the Scalability and Applicability of Cryptographic Proof Systems

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/verification costs. In this dissertation, we broaden the applicability of zk-SNARKs by proposing methodologies that improve their concrete efficiency and prepare them for large-scale, 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 another 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 proving work to an untrusted server while the server learns no information about the witness, the statement, or even the final proof. We propose a novel technique to achieve server-aided proving for several widely deployed zk-SNARKs in a practical manner.