International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Batch Groth-Sahai

Authors:
Olivier Blazy
Georg Fuchsbauer
Malika Izabachène
Amandine Jambert
Hervé Sibert
Damien Vergnaud
Download:
URL: http://eprint.iacr.org/2010/040
Search ePrint
Search Google
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).
BibTeX
@misc{eprint-2010-22941,
  title={Batch Groth-Sahai},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Pairing-based cryptography, Batch verification, Groth-Sahai proof system},
  url={http://eprint.iacr.org/2010/040},
  note={ damien.vergnaud@ens.fr 14643 received 26 Jan 2010, last revised 3 Feb 2010},
  author={Olivier Blazy and Georg Fuchsbauer and Malika Izabachène and Amandine Jambert and Hervé Sibert and Damien Vergnaud},
  year=2010
}