### Square Span Programs with Applications to Succinct NIZK Arguments

George Danezis, Cedric Fournet, 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.

Available format(s)
Category
Public-key cryptography
Publication info
Keywords
Contact author(s)
markulf @ microsoft com
History
Short URL
https://ia.cr/2014/718

CC BY

BibTeX

@misc{cryptoeprint:2014/718,
author = {George Danezis and Cedric Fournet and Jens Groth and Markulf Kohlweiss},
title = {Square Span Programs with Applications to Succinct NIZK Arguments},
howpublished = {Cryptology ePrint Archive, Paper 2014/718},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/718}},
url = {https://eprint.iacr.org/2014/718}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.