New Techniques for Structural Batch Verification in Bilinear Groups with Applications to Groth-Sahai Proofs
Gottfried Herold, Max Hoffmann, Michael Klooß, Carla Ràfols, Andy Rupp · 2017
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.