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

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

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 |
ACM, New York |

Seiten |
1547-1564 |

Projektinformation |
KASTEL_IoE (BMBF, 16KIS0346) |

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft

KITopen Landing Page