Cryptology ePrint Archive: Report 2014/718

Square Span Programs with Applications to Succinct NIZK Arguments

George Danezis and Cedric Fournet and Jens Groth and Markulf Kohlweiss

Abstract: We propose a new characterization of NP using square span programs (SSPs). We first characterize NP as affine map constraints on small vectors. We then relate this characterization to SSPs, which are similar but simpler than Quadratic Span Programs (QSPs) and Quadratic Arithmetic Programs (QAPs) since they use a single series of polynomials rather than 2 or 3.

We use SSPs to construct succinct non-interactive zero-knowledge arguments of knowledge. For performance, our proof system is defined over Type III bilinear groups; proofs consist of just 4 group elements, verified in just 6 pairings. Concretely, using the Pinocchio libraries, we estimate that proofs will consist of 160 bytes verified in less than 6 ms.

Category / Keywords: public-key cryptography / square span program, quadratic span program, SNARKs, non-interactive zero-knowledge arguments of knowledge

Original Publication (in the same form): IACR-ASIACRYPT-2014

Date: received 14 Sep 2014, last revised 15 Sep 2014

Contact author: markulf at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20140916:161054 (All versions of this report)

Short URL: ia.cr/2014/718

Discussion forum: Show discussion | Start new discussion