Paper Info
Title
Faster Multi-exponentiation through Caching: Accelerating (EC)DSA Signature Verification
Abstract
When verifying digital signatures, achieving a high throughput can be crucial. We present a technique that is useful for ECDSA and DSA signatures. It assumes that common domain parameters are used (which is typical of ECDSA) and that at least some signers recur (as in many application scenarios). We can achieve noticeable speedups in very different environments-- from highly restricted ones where memory is very scarce to larger machines without severe memory restrictions. Requirements for the target platform are very small for a beneficial application of our technique. This makes it attractive for embedded systems, where ECDSA is a signature scheme of choice.More generally, what we consider is the task of computing power products $\prod_{1 \leq i \leq k} g_i^{e_i}$ ("multi-exponentiation") where base elements g2, ..., gkare fixed while g1is 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 product. The first way applies to the first occurrence of any g1where, besides obtaining the actual result, we create a cache entry based on g1, investing very little memory or time overhead.The second way applies to any multi-exponentiation once such a cache entry exists for the g1in question and provides for a significant speed-up.
Year
DOI
Venue
2008
10.1007/978-3-540-85855-3_4
IACR Cryptology ePrint Archive
Keywords
DocType
Volume
different way,actual result,faster multi-exponentiation,beneficial application,severe memory restriction,dsa signature,dsa signature verification,cache entry,application scenario,different environment,ecient,leq k,new technique
Conference
2007
ISSN
Citations 
PageRank 
0302-9743
9
0.58
References 
Authors
19
2
Name
Order
Citations
PageRank
Bodo Möller121114.41
Andy Rupp219616.95