Seminars

View all Seminars  |  Download ICal for this event

Succinct Arguments and Doubly Efficient Zero-knowledge Arguments for RAM programs

Series: Department Seminar

Speaker: Akash Shah, Ph.D. candidate, University of California, Los Angeles

Date/Time: Mar 11 11:00:00

Location: CSA Conference Room, (Room No. 101, Ground floor)

Abstract:
Motivated by the goal of proving statements that involve small subsets of a big database, we introduce and study the notion of projection codes. A standard error-correcting code allows one to encode a message x into a codeword X such that even if a constant fraction of X is corrupted, the message x can still be recovered. In this work, we propose the notion of projection codes that extends this guarantee to any subset of the bits of x. Concretely, for every projection of x to a subset s of its coordinates, there is a subset S of comparable size such that the projected encoding X|_S forms a robust encoding of the projected message x|_s. We construct projection codes with a near-optimal increase in the length of x and size of s. Using projection codes, we construct succinct arguments for the computation of a RAM program on a (big) committed database, where the communication and the run-time of both the prover and the verifier are close to optimal even when the RAM program run-time is much smaller than the database size. Our solution makes only a black-box use of a collision-resistant hash function, providing the first black-box alternative to previous non-black-box constructions with similar asymptotic efficiency.


Next, we propose the notion of ??locally updatable projection codes? that extends and generalizes the notion of projection codes to support updates. Locally updatable projection codes maintain the guarantee of projection codes even while updating the codeword to support updates to the underlying message x. Using locally updatable projection codes, we propose the first fully succinct zero-knowledge arguments for RAM programs executed on a committed database that makes a black-box use of symmetric cryptography only. Specifically, in the offline phase, the prover commits to a database x of size n. During the subsequent online phase, it can prove in zero-knowledge statements of the form there exists w such that R(x,w)=1 where R is an NP relation verified by a RAM program within T steps. In our construction, the prover incurs an offline computation cost comparable to n. The online prover runtime scales with T, even when T is sublinear in n. Furthermore, the verifier is exceptionally lightweight in our construction, with computation and communciation being only polylog(n). Prior to our work, the best previous solutions had an online phase in which not only did the provers runtime scale with T, but also the communication (and, consequently, the verifiers runtime) scaled with T.

Speaker Bio:
Akash Shah is a Ph.D. candidate advised by Prof. Rafail Ostrovsky at UCLA. His research interests lie in Secure Multiparty Computation (MPC), with a current focus on addressing challenges related to MPC for RAM programs and Garbled Circuits. Previously, he earned his M.Tech (Research) in Computer Science from the Indian Institute of Science (IISc), supervised by Prof. Sanjit Chatterjee. He has also held positions as a Research Fellow at Microsoft Research, and as a research intern at IBM Research.

Host Faculty: Prof. Chaya Ganesh