Paper 2017/802

New Techniques for Structural Batch Verification in Bilinear Groups with Applications to Groth-Sahai Proofs

Gottfried Herold, Max Hoffmann, Michael Kloo\ss, Carla Ràfols, and Andy Rupp


Bilinear groups form the algebraic setting for a multitude of important cryptographic protocols including anonymous credentials, e-cash, e-voting, e-coupon, and loyalty systems. It is typical of such crypto protocols that participating parties need to repeatedly verify that certain equations over bilinear groups are satisfied, e.g., to check that computed signatures are valid, commitments can be opened, or non-interactive zero-knowledge proofs verify correctly. Depending on the form and number of equations this part can quickly become a performance bottleneck due to the costly evaluation of the bilinear map. To ease this burden on the verifier, batch verification techniques have been proposed that allow to combine and check multiple equations probabilistically using less operations than checking each equation individually. In this work, we revisit the batch verification problem and existing standard techniques. We introduce a new technique which, in contrast to previous work, enables us to fully exploit the structure of certain systems of equations. Equations of the appropriate form naturally appear in many protocols, e.g., due to the use of Groth-Sahai proofs. The beauty of our technique is that the underlying idea is pretty simple: we observe that many systems of equations can alternatively be viewed as a single equation of products of polynomials for which probabilistic polynomial identity testing following Schwartz-Zippel can be applied. Comparisons show that our approach can lead to significant improvements in terms of the number of pairing evaluations. Indeed, for the BeleniosRF voting system presented at CCS 2016, we can reduce the number of pairings (required for ballot verification) from $4k+140$, as originally reported by Chaidos et al., to $k+7$. As our implementation and benchmarks demonstrate, this may reduce the verification runtime to only $5\%$ to $13\%$ of the original runtime.

Note: Fix typos and minor corrections.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.ACM CCS 2017
Batch verificationbilinear mapsGroth-Sahai proofsstructure-preserving cryptographyBeleniosP-signatures
Contact author(s)
gottfried herold @ ens-lyon fr
2017-08-31: revised
2017-08-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gottfried Herold and Max Hoffmann and Michael Kloo\ss and Carla Ràfols and Andy Rupp},
      title = {New Techniques for Structural Batch Verification in  Bilinear Groups with Applications to Groth-Sahai Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/802},
      year = {2017},
      doi = {10.1145/3133956.3134068},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.