### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2007/470

CC BY

BibTeX

@misc{cryptoeprint:2007/470,
author = {Bodo Möller and Andy Rupp},
title = {Faster Multi-Exponentiation through Caching: Accelerating (EC)DSA Signature Verification},
howpublished = {Cryptology ePrint Archive, Paper 2007/470},
year = {2007},
note = {\url{https://eprint.iacr.org/2007/470}},
url = {https://eprint.iacr.org/2007/470}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.