Paper 2010/040

Batch Groth-Sahai

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

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 a number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and manage 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) and also for specific popular protocols relying on their methodology (namely Groth's group signatures and Belenkiy-Chase-Kohlweiss-Lysyanskaya's P-signatures).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Pairing-based cryptographyBatch verificationGroth-Sahai proof system
Contact author(s)
damien vergnaud @ ens fr
History
2010-02-03: last of 2 revisions
2010-01-29: received
See all versions
Short URL
https://ia.cr/2010/040
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/040,
      author = {Olivier Blazy and Georg Fuchsbauer and Malika Izabachène and Amandine Jambert and Hervé Sibert and Damien Vergnaud},
      title = {Batch Groth-Sahai},
      howpublished = {Cryptology ePrint Archive, Paper 2010/040},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/040}},
      url = {https://eprint.iacr.org/2010/040}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.