KIT | KIT-Bibliothek | Impressum
DOI: 10.1145/3133956.3134068

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

Herold, Gottfried; Hoffmann, Max; Klooß, Michael; Ràfols, Carla; Rupp, Andy

Abstract (englisch):
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 pr ... mehr

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Kompetenzzentrum für angewandte Sicherheitstechnologie (KASTEL)
Publikationstyp Proceedingsbeitrag
Jahr 2017
Sprache Englisch
Identifikator ISBN: 978-1-4503-4946-8
KITopen ID: 1000077890
Erschienen in 24th ACM Conference on Computer and Communications Security (ACM CCS 2017), Dallas, TX, October 30 - November 3, 2017
Verlag ACM, New York
Seiten 1547-1564
Projektinformation KASTEL_IoE (BMBF, 16KIS0346)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page