New techniques for structural batch verification in bilinear groups with applications to groth-Sahai proofs

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Herold, Gottfried
• dc.contributor.author Hoffmann, Max
• dc.contributor.author Klooß, Michael
• dc.contributor.author Ràfols, Carla
• dc.contributor.author Rupp, Andy
• dc.date.accessioned 2019-12-18T14:49:43Z
• dc.date.available 2019-12-18T14:49:43Z
• dc.date.issued 2017
• dc.description Comunicació presentada a: the 2017 ACM SIGSAC Conference on Computer and Communications Security, celebrada del 30 d'octubre al 3 de novembre de 2017 a Dallas, Texas, Estats Units d'Amèrica.
• dc.description.abstract 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. 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 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.en
• dc.description.sponsorship Gottfried Herold is supported by ERC Starting Grant 335086 Lattices: Algorithms and Cryptography (LattAC). Max Hoffmann is supported by DFG grant PA 587/10-1. Michael Klooß is supported by the Competence Center for Applied Security Technology (KASTEL). Carla Ràfols is supported by Marie Curie COFUND project “UPF Fellows” under grant agreement 600387. Andy Rupp is supported by DFG grant RU 1664/3-1 and the Competence Center for Applied Security Technology (KASTEL).en
• dc.format.mimetype application/pdf
• dc.identifier.citation Herold G, Hoffmann M, Klooss M, Ràfols C, Rupp A. New techniques for structural batch verification in bilinear groups with applications to groth-Sahai proofs. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security; 2017 Oct 30 - Nov 3; Dallas, Texas, USA. New York: ACM; 2017. p. 1547-64. DOI: 10.1145/3133956.3134068
• dc.identifier.doi http://dx.doi.org/10.1145/3133956.3134068
• dc.identifier.isbn 978-1-4503-4946-8
• dc.identifier.uri http://hdl.handle.net/10230/43208
• dc.language.iso eng
• dc.publisher ACM Association for Computer Machinery
• dc.relation.ispartof Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security; 2017 Oct 30 - Nov 3; Dallas, Texas, USA. New York: ACM; 2017. p. 1547-64.
• dc.relation.projectID info:eu-repo/grantAgreement/EC/FP7/335086
• dc.relation.projectID info:eu-repo/grantAgreement/EC/FP7/600387
• dc.rights © ACM, 2017. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security https://dl.acm.org/citation.cfm?doid=3133956.3134068
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Batch verificationen
• dc.subject.keyword Bilinear mapsen
• dc.subject.keyword Groth-Sahai proofsen
• dc.subject.keyword Structure-preserving cryptographyen
• dc.subject.keyword Beleniosen
• dc.subject.keyword P-signaturesen
• dc.title New techniques for structural batch verification in bilinear groups with applications to groth-Sahai proofsen
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/acceptedVersion