International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Bodo M?ller
Andy Rupp
Download:
URL: http://eprint.iacr.org/2007/470
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13750,
  title={Faster Multi-Exponentiation through Caching: Accelerating (EC)DSA Signature Verification},
  booktitle={IACR Eprint archive},
  keywords={implementation / Efficient implementation, elliptic curve cryptography, ECDSA verification, exponentiation, DSA verification},
  url={http://eprint.iacr.org/2007/470},
  note={ bmoeller@acm.org 13866 received 15 Dec 2007, last revised 19 Dec 2007},
  author={Bodo M?ller and Andy Rupp},
  year=2007
}