Batch Groth-Sahai

Olivier Blazy; Georg Fuchsbauer; Malika Izabachène; Amandine Jambert; Hervé Sibert; Damien Vergnaud

doi:10.1007/978-3-642-13708-2_14

Batch Groth-Sahai

Olivier Blazy
, Georg Fuchsbauer
, Malika Izabachène
, Amandine Jambert
, Hervé Sibert
, Damien Vergnaud

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

Abstract

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to the number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and succeed to improve significantly the complexity of proof verification. We give explicit batch-verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) as well as for specific popular protocols relying on their methodology (namely Groth's group signatures and the P-signatures by Belenkiy, Chase, Kohlweiss and Lysyanskaya).

Original language	English
Title of host publication	Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings
Pages	218-235
Number of pages	18
DOIs	https://doi.org/10.1007/978-3-642-13708-2_14
Publication status	Published - 1 Dec 2010
Event	8th International Conference on Applied Cryptography and Network Security, ACNS 2010 - Beijing, China Duration: 22 Jun 2010 → 25 Jun 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6123 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Conference on Applied Cryptography and Network Security, ACNS 2010
Country/Territory	China
City	Beijing
Period	22/06/10 → 25/06/10

Keywords

Batch verification
Groth-Sahai proof system
Pairing-based cryptography

Access to Document

10.1007/978-3-642-13708-2_14

Cite this

Blazy, O., Fuchsbauer, G., Izabachène, M., Jambert, A., Sibert, H., & Vergnaud, D. (2010). Batch Groth-Sahai. In Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings (pp. 218-235). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6123 LNCS). https://doi.org/10.1007/978-3-642-13708-2_14

@inproceedings{e00cb90e37d44391ad3686e245f4f5c3,

title = "Batch Groth-Sahai",

abstract = "In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to the number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and succeed to improve significantly the complexity of proof verification. We give explicit batch-verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) as well as for specific popular protocols relying on their methodology (namely Groth's group signatures and the P-signatures by Belenkiy, Chase, Kohlweiss and Lysyanskaya).",

keywords = "Batch verification, Groth-Sahai proof system, Pairing-based cryptography",

author = "Olivier Blazy and Georg Fuchsbauer and Malika Izabach{\`e}ne and Amandine Jambert and Herv{\'e} Sibert and Damien Vergnaud",

year = "2010",

month = dec,

day = "1",

doi = "10.1007/978-3-642-13708-2\_14",

language = "English",

isbn = "3642137075",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "218--235",

booktitle = "Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings",

note = "8th International Conference on Applied Cryptography and Network Security, ACNS 2010 ; Conference date: 22-06-2010 Through 25-06-2010",

}

Blazy, O, Fuchsbauer, G, Izabachène, M, Jambert, A, Sibert, H & Vergnaud, D 2010, Batch Groth-Sahai. in Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6123 LNCS, pp. 218-235, 8th International Conference on Applied Cryptography and Network Security, ACNS 2010, Beijing, China, 22/06/10. https://doi.org/10.1007/978-3-642-13708-2_14

Batch Groth-Sahai. / Blazy, Olivier; Fuchsbauer, Georg; Izabachène, Malika et al.
Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings. 2010. p. 218-235 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6123 LNCS).

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

TY - GEN

T1 - Batch Groth-Sahai

AU - Blazy, Olivier

AU - Fuchsbauer, Georg

AU - Izabachène, Malika

AU - Jambert, Amandine

AU - Sibert, Hervé

AU - Vergnaud, Damien

PY - 2010/12/1

Y1 - 2010/12/1

N2 - In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to the number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and succeed to improve significantly the complexity of proof verification. We give explicit batch-verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) as well as for specific popular protocols relying on their methodology (namely Groth's group signatures and the P-signatures by Belenkiy, Chase, Kohlweiss and Lysyanskaya).

AB - In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to the number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and succeed to improve significantly the complexity of proof verification. We give explicit batch-verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) as well as for specific popular protocols relying on their methodology (namely Groth's group signatures and the P-signatures by Belenkiy, Chase, Kohlweiss and Lysyanskaya).

KW - Batch verification

KW - Groth-Sahai proof system

KW - Pairing-based cryptography

U2 - 10.1007/978-3-642-13708-2_14

DO - 10.1007/978-3-642-13708-2_14

M3 - Conference contribution

AN - SCOPUS:79751527812

SN - 3642137075

SN - 9783642137075

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 218

EP - 235

BT - Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings

T2 - 8th International Conference on Applied Cryptography and Network Security, ACNS 2010

Y2 - 22 June 2010 through 25 June 2010

ER -

Blazy O, Fuchsbauer G, Izabachène M, Jambert A, Sibert H, Vergnaud D. Batch Groth-Sahai. In Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings. 2010. p. 218-235. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-13708-2_14

Batch Groth-Sahai

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this