Square Span Programs with Applications to Succinct NIZK Arguments

George Danezis; Cédric Fournet; Jens Groth; Markulf Kohlweiss

doi:10.1007/978-3-662-45611-8_28

Square Span Programs with Applications to Succinct NIZK Arguments

George Danezis, Cédric Fournet, Jens Groth, Markulf Kohlweiss

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I
Publisher	Springer
Pages	532-550
Number of pages	19
ISBN (Electronic)	978-3-662-45611-8
ISBN (Print)	978-3-662-45610-1
DOIs	https://doi.org/10.1007/978-3-662-45611-8_28
Publication status	Published - 2014
Event	20th Annual International Conference on the Theory and Application of Cryptology and Information Security - Kaohsiung, Taiwan, Province of China Duration: 7 Dec 2014 → 11 Dec 2014 http://des.cse.nsysu.edu.tw/asiacrypt2014/

Conference

Conference	20th Annual International Conference on the Theory and Application of Cryptology and Information Security
Abbreviated title	Asiacrypt 2014
Country/Territory	Taiwan, Province of China
City	Kaohsiung
Period	7/12/14 → 11/12/14
Internet address	http://des.cse.nsysu.edu.tw/asiacrypt2014/

Access to Document

10.1007/978-3-662-45611-8_28

Square Span ProgramsAccepted author manuscript, 398 KB

https://link.springer.com/chapter/10.1007%2F978-3-662-45611-8_28

Cite this

Danezis, G., Fournet, C., Groth, J., & Kohlweiss, M. (2014). Square Span Programs with Applications to Succinct NIZK Arguments. In Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I (pp. 532-550). Springer. https://doi.org/10.1007/978-3-662-45611-8_28

@inproceedings{878b68ba96cb4433aa589a400584c439,

title = "Square Span Programs with Applications to Succinct NIZK Arguments",

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.",

author = "George Danezis and C{\'e}dric Fournet and Jens Groth and Markulf Kohlweiss",

year = "2014",

doi = "10.1007/978-3-662-45611-8\_28",

language = "English",

isbn = "978-3-662-45610-1",

pages = "532--550",

booktitle = "Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I",

publisher = "Springer",

address = "United Kingdom",

note = "20th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2014 ; Conference date: 07-12-2014 Through 11-12-2014",

url = "http://des.cse.nsysu.edu.tw/asiacrypt2014/",

}

Danezis, G, Fournet, C, Groth, J & Kohlweiss, M 2014, Square Span Programs with Applications to Succinct NIZK Arguments. in Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I. Springer, pp. 532-550, 20th Annual International Conference on the Theory and Application of Cryptology and Information Security, Kaohsiung, Taiwan, Province of China, 7/12/14. https://doi.org/10.1007/978-3-662-45611-8_28

Square Span Programs with Applications to Succinct NIZK Arguments. / Danezis, George; Fournet, Cédric; Groth, Jens et al.
Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I. Springer, 2014. p. 532-550.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Square Span Programs with Applications to Succinct NIZK Arguments

AU - Danezis, George

AU - Fournet, Cédric

AU - Groth, Jens

AU - Kohlweiss, Markulf

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-662-45611-8_28

DO - 10.1007/978-3-662-45611-8_28

M3 - Conference contribution

SN - 978-3-662-45610-1

SP - 532

EP - 550

BT - Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I

PB - Springer

T2 - 20th Annual International Conference on the Theory and Application of Cryptology and Information Security

Y2 - 7 December 2014 through 11 December 2014

ER -

Danezis G, Fournet C, Groth J, Kohlweiss M. Square Span Programs with Applications to Succinct NIZK Arguments. In Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I. Springer. 2014. p. 532-550 doi: 10.1007/978-3-662-45611-8_28

Square Span Programs with Applications to Succinct NIZK Arguments

Abstract

Conference

Access to Document

Fingerprint

Cite this