Paper 2018/705

Succinct Arguments from Subvector Commitments and Linear Map Commitments

Russell W.F. Lai and Giulio Malavolta

Abstract

Succinct non-interactive arguments of knowledge (SNARK) allow a prover to convince a verifier of the validity of certain statements with a single short message. Revisiting the “CS proofs” paradigm [Micali, FOCS 1994], we leverage number-theoretic assumptions to construct arguments with significantly shorter proofs. With typical computational and statistical security parameters λ ≈ 100 and k ≈ 80 respectively, two main results in the random oracle model follow. 1. There exists a setup-free SNARK with proofs of size ∼4300 bits, under the adaptive root assumption over class groups of imaginary quadratic orders. This is the shortest setup-free SNARK at the time of writing. 2. There exists a pre-processing SNARK with proofs consisting of 2 group elements plus ∼250 bits (for a total of ∼750 bits), under the computational Diffie-Hellman (CDH) assumption over pairing groups. This matches the most efficient scheme in the same setting [Groth, EUROCRYPT 2016] but our verifier has to compute only 2 pairings, as opposed to 3. The common ground of both constructions is a 4-message protocol that compiles any (possibly linear) probabilistic checkable proof (PCP) into an argument of knowledge. The protocol is made non-interactive using the Fiat-Shamir transform. Our main technical tool is a generalization of vector commitments called subvector commitments (SVC). The latter allows to open a committed vector at a set of positions, where the opening size is independent of the size of the set. 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 to open a committed vector to its images under linear maps. We propose two constructions under different assumptions over pairing groups. LMC allows one to construct pre-processing SNARKs but with a more efficient prover. Apart from the new application in constructing succinct arguments, SVC and LMC have numerous other applications which may be of independent interest.