You are looking at a specific version 20071219:141000 of this paper. See the latest version.

Paper 2007/470

Faster Multi-Exponentiation through Caching: Accelerating (EC)DSA Signature Verification

Bodo Möller and Andy Rupp

Abstract

We consider the task of computing power products $\prod_{1 \leq i \leq k} g_i^{e_i}$ ("multi-exponentiation") where base elements $g_2, ..., g_k$ are fixed while $g_1$ is variable between multi-exponentiations but may repeat, and where the exponents are bounded (e.g., in a finite group). We present a new technique that entails two different ways of computing such a result. The first way applies to the first occurrence of any $g_1$ where, besides obtaining the actual result, we create a cache entry based on $g_1$, investing very little memory or time overhead. The second way applies to any multi-exponentiation once such a cache entry exists for the $g_1$ in question: the cache entry provides for a significant speed-up. Our technique is useful for ECDSA or DSA signature verification with common domain parameters and recurring signers.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Efficient implementationelliptic curve cryptographyECDSA verificationexponentiationDSA verification
Contact author(s)
bmoeller @ acm org
History
2007-12-19: revised
2007-12-19: received
See all versions
Short URL
https://ia.cr/2007/470
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.