Seminars

View all Seminars  |  Download ICal for this event

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

Series: Ph.D. Thesis Defense

Speaker: Moumita Dutta, Ph.D (Engg.) student, Dept. of CSA, IISc

Date/Time: Nov 07 11:30:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor: Prof. Chaya Ganesh & Prof. Arpita Patra

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.

Speaker Bio:
Moumita Dutta is a PhD student at Department of Computer Science and Automation, IISc Bangalore. Prior to this, she completed her BSc and MSc in Mathematics from Jadavpur University. Her research interest lies in the broad area of privacy-preserving techniques provided by powerful tools like Zero-Knowledge Proofs (ZKP) and secure Multi-Party Computation (MPC). Teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZDNiOGMwYjEtOTFiNy00ZTc1LWE1NmUtZWZlN2QzNzVlNWUw%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%221beaa166-3a14-437e-9106-75a2e2caebeb%22%7d Join the meeting ID Meeting ID: 471 837 523 109 4 Passcode: 49G7F8hT