Zero Knowledge Proofs: Succinct Verification, Distributed Proofs and Lookup Arguments

Abstract

Zero-Knowledge Proofs (ZKPs) are fundamental cryptographic tools enabling a prover to convince a verifier about the knowledge of a secret witness related to a public statement, without revealing any information beyond the validity of the claim. zk-SNARKs, acronym for zero-knowledge Succinct Non-interactive ARguments of Knowledge, offer efficient ZKPs with succinct communication, prover, and verifier complexities. Additionally, contrary to traditional ZKPs that tackles privacy concerns, there exists applications where privacy is not a requirement and efficiency is the primary concern - for instance to enable powerful (and potentially untrusted) server(s) to perform computationally expensive tasks and provide efficiently verifiable proofs of correct computation of the specified function. Furthermore, there are applications where proof generation being distributed enhances trust and security.

This thesis explores various efficiency dimensions in the context of zero-knowledge proofs. First, we study compressed sigma protocols, enhancing a core ZKP building block of sigma protocols, to achieve logarithmic verification complexity while maintaining logarithmic proof size. Second, we explore applications where privacy is a requirement in an event of distribution of proof generation. In particular, we elevate the building blocks for ZKPs for scenarios where the prover wishes to distribute the proof generation to a set of workers by secret-sharing its private witness; and explore its significance on the application of providing efficient framework for authentication of inputs used inside secure Multi-Party Computation (MPC). Finally, we investigate applications like scalable blockchain rollups, where the primary goal is obtaining efficiently verifiable proofs. We present a batching-efficient Random Access Memory (RAM) framework that proves the correctness of m updates on a RAM of size N (where m is significantly smaller than N), where we improve efficiency of proof generation while further improving proof size and preserving optimal verification complexity. This is achieved by realising efficient updatable lookup arguments, that helps us perform m lookups on a N-size table, even after the table has been updated at a few positions.