Back to search

University of Waterloo

Batch Verification of Elliptic Curve Digital Signatures

Abstract

dc:description.abstract

This thesis investigates the efficiency of batching the verification of elliptic curve signatures. The first signature scheme considered is a modification of ECDSA proposed by Antipa et al.\ along with a batch verification algorithm by Cheon and Yi. Next, Bernstein's EdDSA signature scheme and the Bos-Coster multi-exponentiation algorithm are presented and the asymptotic runtime is examined. Following background on bilinear pairings, the Camenisch-Hohenberger-Pedersen (CHP) pairing-based signature scheme is presented in the Type 3 setting, along with the derivative BN-IBV due to Zhang, Lu, Lin, Ho and Shen. We proceed to count field operations for each signature scheme and an exact analysis of the results is given. When considered in the context of batch verification, we find that the Cheon-Yi and Bos-Coster methods have similar costs in practice (assuming the same curve model). We also find that when batch verifying signatures, CHP is only 11\% slower than EdDSA with Bos-Coster, a significant improvement over the gap in single verification cost between the two schemes.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wesolowski, Michael

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/9246

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wesolowski, Michael. Batch Verification of Elliptic Curve Digital Signatures. University of Waterloo, 2015. http://hdl.handle.net/10012/9246