Ligero: Lightweight Sublinear Zero-Knowledge Arguments

Speaker: Muthu Venkitasubramaniam

Abstract: Succinct non-interactive zero-knowledge (ZK) argument of knowledge or zk-SNARKs, a variant of ZK proof systems, have recently gained a lot of attention as a tool that enables anonymity and integrity in blockchain technologies and forms the backbone of the Zcash cryptocurrency. However, the current (efficient) solutions either rely on trusted setup or make heavy use of public-key primitives and/or complex combinatorial objects (eg, probabilistically checkable proofs).

We design and implement a simple zero-knowledge argument protocol for arbitrary statements (i.e., NP) whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography.

Our protocol is attractive not only for very large verification circuits but also for moderately large circuits (Boolean or Arithmetic) that arise in applications. For instance, for verifying a SHA-256 preimage in zero-knowledge with 2^{-40} soundness error, the proof length is roughly 44KB (or less than 34KB under a plausible conjecture), the prover running time is 140 ms, and the verifier running time is 62 ms. This proof is roughly 4 times shorter than a similar proof of ZKB++ (Chase et al., CCS 2017), an optimized variant of ZKBoo (Giacomelli et al., USENIX 2016).

I will describe several applications for blockchain technologies and general secure computation where our zero-knowledge argument will improve the state-of-the-art and present some on-going work.

Based on joint works with Scott Ames, Carmit Hazay and Yuval Ishai

Bio: Muthu Venkitasubramaniam is an Associate Professor at the University of Rochester. He received his BTech degree in computer science from the Indian Institute of Technology, Madras in 2004. He attended Cornell University, where he worked with Rafael Pass receiving his Ph.D. in computer science in 2011. Before arriving at the University of Rochester, he spent a year at the Courant Institute of Mathematical Sciences (NYU) as a postdoctoral researcher supported by the Computing Innovation Fellowship. Muthu's interests are in the theory and practice of Cryptography and Network Security. He is a recipient of the Google Faculty Research award and his work on "L-Diversity: Privacy beyond K-Anonymity" received the ICDE 2017 Influential Paper Award.