KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Herold, Gottfried; Hoffmann, Max; Klooß, Michael ORCID iD icon; 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 protocols, e.g., due
... mehr

DOI: 10.1145/3133956.3134068
Zitationen: 8
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Kompetenzzentrum für angewandte Sicherheitstechnologie (KASTEL)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 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 Association for Computing Machinery (ACM)
Seiten 1547-1564
Projektinformation KASTEL_IoE (BMBF, 16KIS0346)
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page