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
UR - https://www.scopus.com/pages/publications/79751527812
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 -