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

Bilinear groups form the algebraic setting for a multitude of im-
portant 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 ver-
ify 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 cor-
rectly. 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
... mehr
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.
[19], to k + 7. As our implementation and benchmarks demonstrate,
this may reduce the verification runtime to only 5% to 13% of the
original runtime.