[Resource Topic] 2007/470: Faster Multi-Exponentiation through Caching: Accelerating (EC)DSA Signature Verification

Welcome to the resource topic for 2007/470

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

Authors: Bodo Möller, Andy Rupp


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.

ePrint: https://eprint.iacr.org/2007/470

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .