We put forward the notion of subvector commitments (SVC): An SVC allows one to open a committed vector at a set of positions, where the opening size is independent of length of the committed vector and the number of positions to be opened. We propose two constructions under variants of the root assumption and the CDH assumption, respectively. We further generalize SVC to a notion called linear map commitments (LMC), which allows one to open a committed vector to its images under linear maps with a single short message, and propose a construction over pairing groups.
Equipped with these newly developed tools, we revisit the “CS proofs” paradigm [Micali, FOCS 1994] which turns any arguments with public-coin verifiers into non-interactive arguments using the Fiat-Shamir transform in the random oracle model. We propose a compiler that turns any (linear, resp.) PCP into a non-interactive argument, using exclusively SVCs (LMCs, resp.). For an approximate 80 bits of soundness, we highlight the following new implications:
There exists a succinct non-interactive argument of knowledge (SNARK) with public-coin setup with proofs of size 5360 bits, under the adaptive root assumption over class groups of imaginary quadratic orders against adversaries with runtime $2^128$. At the time of writing, this is the shortest SNARK with public-coin setup.
There exists a non-interactive argument with private-coin setup, where proofs consist of 2 group elements and 3 field elements, in the generic bilinear group model.
Mr. Lai is a PhD candidate in the Friedrich-Alexander University Erlangen-Nuremberg advised by Prof. Dominique Schröder. He received his MPhil degree in Information Engineering in 2016, his BSc degree in Mathematics and BEng degree in Information Engineering in 2014, all from the Chinese University of Hong Kong. His recent research interests include succinct zero-knowledge proofs, privacy-preserving cryptocurrencies, searchable encryption, and password-based cryptography.