Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages

Abstract

We put forth a new framework for building pairing-based non-interactive zero-knowledge (\(\mathsf {NIZK}\)) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a \(\varSigma \)-protocol into a \(\mathsf {NIZK}\). Our framework enjoys a number of interesting features: conceptual simplicity, parameters derive from the \(\varSigma \)-protocol; proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying \(\varSigma \)-protocol; fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS; yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments(ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions.