Cryptology ePrint Archive, Report 2007/470,
http://eprint.iacr.org/

Faster Multi-Exponentiation through Caching:Accelerating (EC)DSA Signature Verification
Bodo Möller and Andy Rupp
Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
bmoeller@acm.org, arupp@crypto.rub.de

Abstract.
We consider the task of computing power productsQeig(“multi-exponentiation”)
where base elements g2 , . . ., gk arei
1≤i≤kfixed while g1 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 g1 where, 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 g1 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.
Keywords: Efficient implementation, elliptic curve cryptography,
ECDSA verification, exponentiation, DSA verification

1

Introduction

Consider a scenario where we repeatedly have to verify ECDSA signatures [1],trying to keep the computational delay small for each verification. A timeconsuming step in ECDSA signature verification is computing a linear combination u1 G + u2 Q of elliptic curve points G and Q, where G is specified by domain
parameters and where Q constitutes the signer’s public key, with integers u1
and u2 in the interval 0, ord(G) − 1} both depending on the specific signature.
The same group with the same point G will typically be shared by many signers since elliptic curve domain parameters are often taken from (intersecting)standards such as [19, Appendix 6], [1, Annex J], and [6] (with domain parameter specifications NIST P-192 aka prime192v1 aka secp192r1 and NIST P-256
aka prime256v1 aka secp256r1 common to all three of these). Also, we usually
can expect some signers and thus their Q values to recur. Consider public-key
infrastructures:– A verifying party will encounter end-entity certificates signed by possibly
very many different intermediate certification authorities. When a new certification authority appears for the first time, the verifying party does not
yet know how popular this particular certification authority is, i.e. if it hassigned many or just very few end-entity certificates.
1

– The same applies to signatures on documents, such as the ECDSA signatures stored on the new digital “e-passports”. When verifying a passport for
airport immigration procedures, then quite possibly the next passenger inline may be using a passport signed by the same agency. On the other hand,the current passenger could be the only one from his particular country.
Thus, for a given G, we have to compute linear combinations u1 G + u2 Q where
Q sometimes is “new” and sometimes is “old” (has been seen before); but whena new Q appears for the first time, we generally do not know if it will appear
again later on.
There are well-known techniques to compute u1 G + u2 Q much faster thanby computing both u1 G and u2 Q individually, and this can be done yet faster
if both G and Q are fixed and a one-time precomputation depending on thesepoints has been done. Performing such precomputation whenever a “new” Q
shows up may pay out if Q turns out to repeat, so that G and Q are fixed for anumber of linear combinations. However, precomputation depending on Q is aninvestment of resources that would be lost if this particular Q does in fact notrepeat.
We present a new technique that nearly avoids this drawback, provided thatspace for permanently fixed precomputation depending on G only is not severely
limited. The first occurrence of some point Q in a computation u1 G + u2 Q
will incur very little penalty in terms of memory or time, and yet will leavebehind useful precomputed data that can be cached to speed up subsequentlinear combination computations involving the same G and Q.
The ECDSA scenario best illustrates the practical use of our technique1 ,which we describe in more general form. It applies to any abelian group or(more generally) abelian semigroup with an identity element, henceforth written multiplicatively so that what we just described as linear combinations now
turns into power products. Computing power products sometimes is called multiexponentiation since it is a generalization of computing powers (exponentiation).
The computational task that we will consider is computing power products ofthe form
Y
giei
1≤i≤k

where base elements g2 , . . ., gk are fixed once and for all, whereas g1 is vari1

Another approach to speed up ECDSA signature verification is due to Antipa
et al. [2, 24]. It works best for a slightly modified variant of the original signaturescheme, dubbed ECDSA∗ , but under appropriate circumstances, it can be useful forthe verification of standard ECDSA signatures. Where it makes sense to use thetechnique from [2, 24], our technique may be preferable depending on the expected
proportion of “old” to “new” Q values. In fact, we can get some of the benefit of[2, 24] for any “new” Q and all of the benefit of our technique for any “old” Q by
using a combination of both techniques in the case of a “new” Q, using specificimbalanced-scalar parameterizations within [2, 24]. We omit further details on this.

2able between multi-exponentiations and may repeat, while all exponents ei are
assumed to be ephemeral. We will assume that the exponents are positive andat most ` bits long. (An appropriate value of ` is usually implied by the grouporder. A negative exponent for a group can be handled through inversion of thebase element, or by reduction of the exponent modulo o where o is some multipleof the order of the base element, such as the group order.) For our techniqueto work as intended, we also assume that the exponent to variable base g1 is
not pathologically short (i.e., its length not just a fraction of `); rare statisticaloutliers are no problem. Besides ECDSA signature verification, this setting also
covers DSA signature verification [19]; however, it only applies when using common domain parameters, which is customary for ECDSA but not necessarily for
DSA.
We assume that at least read-only memory is not severely limited, so that
precomputation depending on g2 , . . ., gk can be permanently stored. We also
assume that some memory is available for caching at least one group elementwith an integer. Such data
Q will be put into cache memory when performing
a multi-exponentiation 1≤i≤k giei involving a “new” g1 (i.e., one for which nocache entry currently exists), and can be used to speed up any subsequent multiexponentiation repeating the same g1 as long as the cache entry is kept. While
the method is easier to describe assuming that dedicated cache memory is available, Appendix C will show that the technique can be quite useful even if thisis not the case and a portion of fast read/write memory has to be sacrificed
instead: In a specific example scenario where read/write memory is very scarce(which is typical of smart cards and other embedded devices), we have a 10 %average speed advantage. The technique also is useful for devices without such
constraints.
Like many approaches for exponentiation using precomputation (such as the
Lim/Lee approach [12]), our technique has roots that can be traced back to
Pippenger [21, 22]; see also [4]. The novelty here in this regard is that for cachednprecomputation, we do not store powers of the form g12 as
Q by [21], which would
impose some computational overhead while computing 1≤i≤k giei when g1 isnew. Instead, we store other powers of g1 that happen to come up without effort
if we arrange the computation suitably.
Section 2 describes preliminaries for our technique: interleaved multiexponentiation, and radix-2 exponent splitting. Then, Section 3 presents thenovel multi-exponentiation technique, which relies on caching certain intermediate results that can be obtained by investing very little additional read/write
memory or time, allowing us to speed up later multi-exponentiations if an appropriate cache entry is available. Section 4 gives example performance figures forthe new technique in certain use scenarios. Appendix A provides a comprehensive
example to illustrate the technique. Appendix B discusses some implementation
aspects. Finally, Appendix C considers a particular scenario to demonstrate theperformance gain that can be obtained by using the new technique.
3

2Multi-Exponentiation

We show known techniques that we later will use and combine in a novel way.
Section 2.1 describes interleaved multi-exponentiation, an approach for computing power products. It also briefly describes some properties of radix-2 exponent representations that can be used in interleaved multi-exponentiation.
Section 2.2 describes the technique of radix-2 exponent splitting, which can beused to obtain shorter exponents by converting exponentiation tasks into multiexponentiation tasks, or converting k-fold multi-exponentiation tasks into k 0 -foldmulti-exponentiation tasks with k 0 > k. Radix-2 exponent splitting is a usefultechnique for fixed bases (namely, for exponentiation or multi-exponentiation
with precomputation that can be done in advance).
2.1

Interleaved Multi-Exponentiation

We build on the straightforward multi-exponentiation strategy that has beencalled interleaving in [14], which generalizes well-known methods for single exponentiations such as the (left-to-right) binary or sliding window methods. Assume
that radix-2 representations
Xei =bi,j · 2j ,bi,j ∈ Bi ,0≤j≤`of all exponents are given where each Bi is a set of integers. We write ei =(bi,` , bi,`−1 , . . ., bi,1 , bi,0 )2 and call the bi,j digits and Bi a digit set. We requirethat every gib for b ∈ Bi \ {0} be available from precomputed data. Note that ina group where inversion is particularly easy (such as those used in elliptic curve
cryptography where an inversion requires just obtaining an additive inverse in theunderlying field or performing a field addition), obtaining gi−b from precomputed
data is easy if gib has been stored; so both b and −b can be included in set Bi if
the single element gib has been stored in a precomputed table of powers. In thissetting, interleaved multi-exponentiation computes the power product as follows.
A ← 1G {Start with identity element}
for j = ` down to 0 do
A ← A2for i = 1 to k do
if bi,j 6= 0 thenb
A ← A · gi i,j {Multiply by [inverse of] precomputed element}
return A
This is a left-to-right technique in that it proceeds from the most significant
digits (“left”) down to the least significant digits (“right”).
Digit sets usually are quite small, typically of the form B ± (m) ={±1, ±3, ±5, ±7, . . ., ±m, 0} for groups where inversion is easy, or B(m) ={1, 3, 5, 7, . . ., m, 0} for semigroups in general. Here parameter m is an odd integer, often but not necessarily of the form 1, (11)2 , (111)2 , . . ., (11. . .11)2 , i.e.,42w − 1, w ≥ 1 an integer. This special form applies to the sliding window
technique (cf. [9]) and to various variants of it that employ signed-digit representations of exponents, such as those introduced in [13] using a right-to-leftconversion from binary to signed-digit representation and in [17, 3, 20] using leftto-right conversions. The general case with an arbitrary odd m was introduced as
fractional window representations in [15], with left-to-right conversions for thesigned-digit case suggested in [11, 23, 16]. Different digits sets can be used for
different exponents, so we have Bi = B(mi ) or Bi = B ± (mi ) with per-exponent
parameters mi when employing such representations.
The length of a representation is the number of digits that remain if wedrop any leading zeros (so the length of (b` , b`−1 , . . ., b1 , b0 )2 is ` + 1 if b` 6= 0).
Maximum length l +1 is sufficient to represent any l-bit integer e (2l−1 ≤ e < 2l )in any of the representations mentioned above [18] (length l is sufficient for
any of the unsigned-digit representations),
and the minimum length with these
representations is l + 1 − log2 m . Thus, the maximum outer loop index ` inthe algorithm as shown above is sufficient for integers up to ` bits.
The weight of a representation is the number of digits that are non-zero. The
conversion techniques mentioned above are known to achieve, for any integer e,
the minimum weight possible given the respective digit set [18, 16]. For unsigned
and signed fractional window representations using digit set {1, 3, 5, . . ., m, 0} or{±1, ±3, ±5, . . ., ±m, 0}, the average weight for random integers up to ` bits isslightly above`m + 1 − 2w(m)1 + w(m) +
2w(m)

and

`
,
m + 1 − 2w(m)2 + w(m) +2w(m)respectively, wherew(m) = log2 (m + 1) ;the average density (weight divided by `) converges to according estimates as` goes to ∞ (see [16]). For the special case m = 2w − 1 (i.e., the sliding window
technique and its non-fractional signed-digit counterparts), such that w(m) = w,
the above is simply `/(1 + w) and `/(2 + w), respectively.
Observe that in the interleaved multi-exponentiation algorithm as shown
above, (semi-)group operations need not actually be performed until after the
first multiplication of A by a precomputed element or its inverse, since A = 1G
holds up to this point. This means that the initial squarings of 1G can be skipped,bband the first operation A ← A · gi i,j amounts to an assignment A ← gi i,j .
To estimate the time required to perform an interleaved multiexponentiation, we thus need the maximum length of the representations of
the ei to determine the number of squarings, and the weight of the representation of each ei to determine the number of other multiplications by elements
available from precomputed data. (The maximum length is one more than thenumber of squarings, and the sum of the weights is one more than the numberof other multiplications.) This is not counting any group inversions, since wewould only use these in the algorithm if inversion is easy. In addition to this,5

we have to look at the time needed for precomputation. If gi is a fixed base,
we can assume that the required powers gib have been precomputed in advance(and possibly built into ROM) and thus do not enter the time estimate. However, if gi is not fixed, some effort goes into precomputing these powers: from gi ,the powers gi3 , . . ., gimi can be computed using one squaring (to obtain gi2 as anintermediate value) and mi2−1 other multiplications.
(Note that the minimum-weight property of a conversion technique does notmean that it always provides the best radix-2 representation possible given theparticular digit set. As discussed in [15, Section 5.1] and [16, Section 4], modified
signed fractional window representations can sometimes reduce length without
increasing weight. In certain situations, it may even be of advantage to accept
a slight increase of weight for the sake of length reduction if saved squarings[due to length reduction] outweigh the additional multiplications [due to weightincrease]. To pursue this approach, we can generalize the concept of radix-2
representations: e.g., (100000)2 = 25 could be converted into 3 · 22 + 5 · 22 , which3
is not a proper radix-2 representation but might be written as 5 00 using a2“double digit” of weight 2. Details are out of the scope of the present paper; wejust mention this as a reminder that minimum-weight radix-2 representations
can sometimes be improved by applying appropriate substitution rules.)2.2

Radix-2 Exponent Splitting

We have seen that the length of exponent representations is important to efficiency since it determines the number of squarings needed for interleaved multiexponentiation. For an exponent e, this length is around log2 e with any of therepresentations mentioned in Section 2.1 as long as parameter m is reasonably
small. Radix-2 exponent splitting, shown in the following, is a simple but effective idea (underlying [5] and made explicit in [8]) to get better performance if
all bases are fixed.
For exponentiations g e with exponent representations e = (b` , . . . , b0 )2 of
maximum length ` + 1, we can decide to split each such representation intosome number s of shorter exponent representations. To wit, let ` + 1 = L1 +· · · + Ls with positive integers Li ≈ `+1
s , and then let e1 = (bL1 −1 , . . ., b0 )2 ,e2 = (bL1 +L2 −1 , . . ., bL1 )2 , and so on:e = (b` , . . . , b0 )2 = (bL1 +···+Ls −1 , . . ., bL1 +···+Ls−1 ,
{z
}
|
es

bL1 +···+Ls−1 −1 , . . ., bL1 +···+Ls−2 , . . .,
|
{z
}
es−1

bL1 +L2 −1 , . . ., bL1 , bL1 −1 , . . ., b0 )2
|
{z
} |
{z
}
e2

Then from e =L1 +···+Li−1P1≤i≤s ei · 2

g e = g e1 · g

2L1

 e2

· ··· · ge1

it follows thates−1
L1 +···+Ls−1 es,· g2

2L1 +···+Ls−2

6

P1≤I<i LI

we haveQtransformed the task of comand thus by defining gi = g 2
puting g e into the s-fold multi-exponentiation 1≤i≤s giei . There is no need toactually evaluate the ei as integers here since we already have appropriate representations of them—namely, portions of the original representation as shown.
Thanks to exponent splitting, the maximum
length of exponent representa
iftheLtions can go down from ` + 1 to `+1
i are chosen accordingly. If g iss
fixed (and the parameters Li are constant), then so are the gi as defined here.
Thus, the powers gib needed by the interleaved multi-exponentiation algorithm
in Section 2.1 can be precomputed in advance. So using additional memory forprecomputed data (possibly ROM) allows us to save time in each exponentiation.
So far, we have looked at radix-2 exponent splitting applied to exponentiation, not to multi-exponentiation: each single exponentiation is converted
into a multi-exponentiation. Radix-2 exponent splitting can just as well be applied for any fixed base in multi-exponentiation tasks, converting a k-fold multiexponentiation into some k 0 -fold multi-exponentiation, k 0 > k. However, since
the exponent
splitting technique needs additional precomputed data (the powers
PL
2 1≤I<i Iof base g), it cannot be used to advantage for bases that are
gi = g
not fixed. Thus, if there is any base that is not fixed (as in the case of DSA
and ECDSA signature verification), long exponent representations may remain,
and radix-2 exponent splitting hence will typically provide essentially no speed
advantage in this situation.

3

Faster Multi-Exponentiation by Caching Intermediate
ResultsThis
section describes a novel technique for computing power products
Qei
1≤i≤k gi assuming that g2 , . . ., gk are fixed base elements, while g1 is a variable base element whose values may recur. The technique is based on interleaved
multi-exponentiation and on exponent splitting, but adds new features. It consists of two different multi-exponentiation algorithms. The first algorithm, described below in Section 3.1, is employed whenever a “new” g1 value appears.
This algorithm not only computes the multi-exponentiation result, but also outputs certain intermediate results, intended to be cached for later use. The second
algorithm, described below in Section 3.2, can be employed whenever an “old” g1
value appears, namely one for which a cache entry already exists. This algorithm
then exploits the cache entry created by the first algorithm to compute the newmulti-exponentiation result faster.
For both algorithms, we assume that parameters for radix-2 exponent splitting have been fixed, i.e. we have constant integers s and L1 , . . ., Ls as described in Section 2.2, used identically for all bases g2 , . . . , gk . We demand that
L1 + 1 ≥ max1≤i≤s Li . For these bases, we furthermore assume that digit setsfor exponent representations have been fixed (see Section 2.1), and that there isa fixed length limit ` + 1 for exponent representations. (This is enough for exponents up to ` bits, using any of the representations mentioned in Section 2.1.) We
also require that powers of g2 , . . ., gk as required for radix-2 exponent splitting
7

using the given digit sets and exponent splitting parameters are precomputed inadvance. These are constant elements, so they may be stored in ROM. Due toour assumption that at least read-only memory is not severely limited, it should
be possible to store quite a number of such precomputed elements, allowing us
to use reasonably large digit sets in the representations of exponents e2 , . . ., ek
that will undergo radix-2 exponent splitting.
Of course, since cache entries take up read/write memory, they eventually
may have to be expired as new g1 values occur. Once the cache entry for a certain g1 has been deleted, this particular value again will have to be considered“new” if it occurs once more later. In extreme cases, the cache might provide
space just for a single cache entry. Then, depending on the caching strategy implemented, g1 might be recognized as “old” only if two immediately consecutive
multi-exponentiations involve the same g1 value, since any new value might leadto an instant cache eviction to make space for a new entry. However, it would
also be possible to keep the existing cache entry for a while even if new g1 values
appear, meaning that any cacheable data created for such a new g1 value would
have to be discarded for lack of space. Which caching strategy is to be preferreddepends very much on the statistical properties of the application scenario.
3.1

Multi-Exponentiation for a New Base g1

Q
If no cache entry based on g1 is available, 1≤i≤k giei should be computed asfollows. As inPSection 2.1, we assume that the exponents are given in representations ei = 0≤j≤` bi,j · 2j , bi,j ∈ Bi .
First, apply radix-2 exponent splitting (Section 2.2) to the representationsof exponents e2 through ek such that all of the resulting exponent representations observe maximum length L = max1≤i≤s Li (≈ `+1s ). This transforms
the k-fold multi-exponentiation task into a multi-exponentiation task with morebases, where the exponent to g1 appears unchanged but all other exponent representations have been split into parts no longer than L digits. The list of bases
has expanded from (g1 , g2 , . . ., gk ) into
g1 ,

L1

g2 , g22 , . . ., g22

L1 +···+Ls−1

,

...,

L1

gk , gk2 , . . ., gk2

L1 +···+Ls−1

;

we will assume that g1 keeps its index (i = 1). Now apply the interleavedmulti-exponentiation algorithm from Section 2.1 to this new 1 + (k − 1)s fold power product. (Remember that appropriate precomputed powers of thebases except g1 areQassumed to be available e.g. from ROM.) This will generate
the desired result, 1≤i≤k giei . Additionally, it will generate certain intermediate
values that turn out to be very useful.
Observe that no loop iteration before j = L1 may involve non-zero exponent
digits for any base other than g1 (since we have L1 + 1 ≥ Li for any of the
exponent splitting parameters L2 , . . ., Ls ). In other words, before this round,A has never been multiplied with a power of a base other than g1 . In particular,(b ,...,b1,L1 )2
we have A = g1 1,`
just after the inner loop iteration for j = L1 , i = 1
8

(and still after the outer loop iteration for j = L1 if L1 ≥ maxi Li ). From thisand earlier loop iterations, we can obtain the following s − 1 intermediate values:(b1,` ,...,b1,L1 +···+Ls−1 )2

j = L1 + · · · + Ls−1 ⇒ A = g1
...

...
(b

,...,b1,L1 +L2 )2(b,...,b1,L1 )2

j = L1 + L2 ⇒ A = g1 1,`
j = L1 , i = 1 ⇒ A = g1 1,`

Thus, we can output the following data to be cached—a cache entry comprising
g1 itself (as index to the cache) and s − 1 pairs, each consisting of an integer andthe corresponding power of g1 :(b ,...,b1,L1 )2
g1 , (b1,` , . . ., b1,L1 )2 , g1 1,`,(b ,...,b1,L1 +L2 )2(b1,` , . . ., b1,L1 +L2 )2 , g1 1,`,. . .,
(b1,` ,...,b1,L1 +···+Ls−1 )2(b1,` , . . ., b1,L1 +···+Ls−1 )2 , g1

Note that when writing this to cache, the integers may be evaluated as such—there is no need to store the specific radix-2 representations. (However, since allof these integers are derived from e1 following a fixed rule, it is clear that at most` bits are sufficient to store complete information on all of them, should memory
efficiency be an utmost concern.) With any of the representations mentioned in
Section 2.1, these partial integers are guaranteed to be non-negative, with(b1,` , . . ., b1,L1 )2 ≥ . . . ≥ (b1,` , . . ., b1,L1 +···+Ls−1 )2 ≥ 0.
Furthermore, if e1 is uniformly random from some set (0, . . ., q) of integers
where q is an `-bit integer, then (unless Ls is very small) all of these integers will actually be positive with high probability (and will P
be reasonably
close to 2`−L1 , . . ., 2`−L1 −···−Ls−1 , respectively; i.e., since ` =1≤i≤s Li , toL2 +···+Ls
Ls
2, . . ., 2 ).
Depending on the assumed distribution of e1 , it may be a good idea to skip
writing a cache entry if it ever turns out that (b1,` , . . ., b1,L1 +···+Ls−1 )2 = 0. In
any case, writing a cache entry should be skipped if all of the integers in it would
be zero (and thus the corresponding powers of g1 trivial).
3.2

Multi-Exponentiation for an Old Base g1

If a cache
Q entry based on g1 is available (created as described in Section 3.1),
then 1≤i≤k giei may be computed as follows.
First, parse the cache entry asg1 , (λ1 , G1 ), . . ., (λs−1 , Gs−1 ) .
9Here we have Gi = g1λi for 1 ≤ i ≤ s − 1, and if one of the exponent representations mentioned in Section 2.1 was used while creating the cache entry
as specified in Section 3.1, we have λ1 ≥ . . . ≥ λs−1 ≥ 0. Now split e1 into
integers Ei (1 ≤ i ≤ s) as follows:– let d0 = e1 ;and di = di−1 − Ei λi ;– for 1 ≤ i ≤ s − 1, let Ei = dλi−1i– and finally, let Es = ds−1 .
. ByIn the exceptional case that λi = 0, Ei = 0 should be substituted for dλi−1ithis construction, we have e1 = E1 λ1 + · · · + Es−1 λs−1 + Es . It follows that
E

Es
s−1
1
g1e1 = GE
1 · · · · · Gs−1 · g1 ,and thus we have transformed the power g1e1 into a power product using new
exponents Ei . This step is similar to radix-2 exponent splitting; we call it modular
exponent splitting. Suitable digit sets for radix-2 representations of each of the
new exponents can be chosen depending on how much read/write memory isavailable for storing powers of the bases G1 , . . ., Gs−1 and g1 (cf. Section 2.1).
For the exponents to the fixed bases g2 , . . ., gk , we again (exactly
as in SecP
tion 3.1) assume that these are given in representations ei = 0≤j≤` bi,j · 2j ,bi,j ∈ Bi . We apply radix-2 exponent splitting to these, giving us exponent
representations of maximum length L.
In total, by applying both modular exponent splitting and radix-2 exponent splitting, we have converted the k-fold multi-exponentiation into a ks-foldmulti-exponentiation. The maximum length of exponent representations here
may exceed L since we do not have strict guarantees regarding the Ei . However,under the assumptions regarding the distribution of e1 stated in Section 3.1, themaximum length will remain around L with high probability.
This completes the description of our new technique. For an illustrative example we refer the reader to Appendix A.

4

Performance

Our multi-exponentiation technique can be used under many different
parameterizations—the number of bases may vary; the length of exponents
may vary; the amount of memory available for fixed precomputation (such as
ROM) may vary; the amount of memory available for cache entries (such as slow
read/write memory) may vary; the amount of memory available for variable
precomputed elements needed by the interleaved exponentiation algorithm mayvary; and under any of these parameterizations, we have to decide on parameterss and L1 , . . ., Ls for exponent splitting (s-fold exponent splitting with exponent
segment lengths Li ), and we have to decide on digit sets and representation
conversion techniques for the exponents to the fixed bases g2 , . . ., gk on the one
hand, and for any of the s partial exponents created from e1 when the algorithm
from Section 3.2 uses a cache entry on the other hand. This encompasses a large
variety of different settings.
10

In the present section, we will look at a specific range of rather simple use
scenarios for our new technique to assess its performance. For a comparison withother approaches, see also Appendix C.
Here, let us assume that we want to implement the multi-exponentiation technique in an environment where only a very limited amount of fast read/write
memory is available but where we have some slower memory suitable for thecache, and where we have plenty of read-only memory for permanently fixed precomputed elements. As powers of g1 are frequently needed in the course of thealgorithm, this is what we will use such fast memory for. As particular examples,
let us consider the cases where we have such fast memory space to store 4, 8, 16
or 32 group elements, and let ` be 160, 192 or 256, which are practical values for
ECDSA. Note that restricting the space for storing powers of a base also limits
the number of different digit values that we can use in exponent representations
for the interleaved multi-exponentiation algorithm. We have implemented our
new multi-exponentiation strategy and counted certain group operations underthese prerequisites for different values of the splitting parameter s, always using
reasonable Li ≈ `+1s and a left-to-right signed fractional window representation
using appropriate digit sets B ± (m) = {±1, ±3, . . ., ±m, 0} such as to fully utilize the fast memory. (See [11, 23, 16] for details regarding left-to-right signed
fractional window conversions.)
We have repeatedly simulated the behavior of our technique for uniformly
random exponents in the interval (0, . . ., 2` − 1), covering both the case of “newbases” to create cache entries (Section 3.1) and the case of “old bases” to observe
the performance given such cache entries (Section 3.2). In these simulations, wehave counted the following operations:– Squarings (S) and other multiplications (M ) used for precomputing powersof g1 (including powers of cache entries derived from g1 );– squarings (S) and multiplications (M ) by precomputed powers of g1 (or ofcache entries) within the interleaved multi-exponentiation algorithm.
We have excluded from counting any of the multiplications by fixed precomputed
elements (from ROM), since these are not a limiting factor given the assumptionthat plenty of space is available for these elements: low-weight exponent representations accordingly may be used for the corresponding exponents, so changesof the parameterization have less of an impact here. (Refer to Section 2.1 forapplicable weight estimates.)
The simulation results can be found in Table 1. The values in the first row(s = 1) reflect the special situation when no splitting at all is done. This applies
to the multi-exponentiation algorithm for a new base g1 for which no cache entry
is available (Section 3.1), where a signed-digit representation is used for the fulllength exponent e1 . The remaining rows contain operation counts for cases where
g1 is an old base, i.e., an existing cache entry is used (Section 3.2). As we cansee from the table, the number of squarings will be reduced to about `/s as
expected using the new modular exponent splitting technique. Moreover, thenumber of multiplications performed during the multi-exponentiation slightly
increases from row to row: this due to the fact that smaller digit sets have to be11

Table 1. Experimental performance figures (squarings and multiplications withpowers of g1 ) for s-fold exponent splitting with exponents up to `-bits, with space for4, 8, 16, or 32 elements for variable precomputation.
#var = 4#var = 8#var = 16#var = 32
1S + 3M
1S + 7M
1S + 15M
1S + 31M
precomp.
` = 160 159.9S + 31.5M 156.0S + 26.1M 155.0S + 22.3M 154.0S + 19.5M
s=1` = 192 188.9S + 37.9M 187.9S + 31.4M 187.0S + 26.9M 186.0S + 23.5M` = 256 252.9S + 50.6M 251.9S + 42.1M 251.0S + 36.0M 250.0S + 31.5M
precomp.
2S + 2M
2S + 6M
2S + 14M
2S + 30M` = 160 79.5S + 39.9M 79.1S + 32.0M 78.6S + 26.8M 78.6S + 23.2M
s=2` = 192 95.7S + 47.9M 94.7S + 38.5M 95.0S + 32.2M 93.7S + 27.8M` = 256 127.6S + 63.9M 126.9S + 51.4M 126.6S + 42.8M 126.8S + 36.8M
precomp.
1S + 1M
3S + 5M
3S + 13M
3S + 29M` = 160 54.7S + 49.4M 53.4S + 37.4M 52.8S + 30.5M 52.4S + 25.9M
s=3` = 192 64.3S + 59.1M 63.3S + 44.7M 62.9S + 36.6M 62.3S + 31.1M` = 256 85.8S + 78.6M 85.0S + 59.6M 84.5S + 48.5M 84.5S + 41.1M
precomp.
0S + 0M
4S + 4M
4S + 12M
4S + 28M` = 160 40.6S + 53.9M 40.7S + 40.7M 39.3S + 32.8M 38.8S + 27.8M
s=4` = 192 48.4S + 64.5M 47.6S + 48.6M 47.6S + 39.2M 46.9S + 33.1M` = 256 64.1S + 85.7M 64.1S + 64.7M 63.4S + 52.1M 62.9S + 43.8M
precomp.
3S + 3M
5S + 11M
5S + 27M` = 160
33.0S + 46.4M 31.9S + 36.0M 31.1S + 30.0M
s=5` = 192
39.7S + 55.8M 39.4S + 43.1M 38.4S + 35.7M` = 256
51.8S + 73.7M 51.4S + 56.9M 50.5S + 47.1M
2S + 2M
6S + 10M
6S + 26M
precomp.
` = 160
29.4S + 50.4M 29.0S + 38.8M 27.8S + 31.9M
s=6` = 192
32.0S + 59.6M 32.2S + 45.9M 31.7S + 37.7M` = 256
45.0S + 79.7M 45.7S + 60.9M 44.3S + 49.8M
1S + 1M
7S + 9M
7S + 25M
precomp.
` = 160
27.8S + 53.8M 26.9S + 40.8M 26.0S + 33.5M
s=7` = 192
30.1S + 64.0M 28.9S + 48.6M 28.4S + 39.5M` = 256
40.5S + 84.7M 39.4S + 64.1M 38.2S + 52.1M

used to obey the space limits while the splitting parameter is increased. (Notethat s ≥ 5 cannot be used with space for only 4 dynamically precomputed
elements, so the corresponding parts of the table are left empty.)
Note that the size of cache entries does not affect the statistics as reflectedin the table. With severe memory constraints for the cache, s = 2 might be theonly option. Comparing the row s = 1 (which describes the case of a multiexponentiation not using a cache entry) with the row s = 2 shows that our
technique provides for a noticeable speed-up even with just s = 2.
It also should be noted that our multi-exponentiation technique for oldbases g1 (Section 3.2) involves s − 1 divisions with remainder to perform s-foldmodular exponent splitting. This starts with an `-bit denominator and a divisor
around ` − s` bits; both operands will decrease by around s` in each subsequentdivision. Thus, the total extra cost of these modular divisions should usually be12reasonably small. The typical size of results means that around ` bits will still
suffice to store the resulting shorter exponents.
Please refer to Appendix B for certain implementation aspects. See Appendix C for a performance comparison of our technique with an immediateapproach in a particular scencario.

References
1. American National Standards Institute (ANSI). Public key cryptography
for the financial services industry: The elliptic curve digital signature algorithm(ECDSA). ANSI X9.62, 1998.
2. Antipa, A., Brown, D., Gallant, R., Lambert, R., Struik, R., and Vanstone, S. Accelerated verification of ECDSA signatures. In Selected Areas in
Cryptography – SAC 2005 (2006), B. Preneel and S. Tavares, Eds., vol. 3897 of
Lecture Notes in Computer Science, pp. 307–318.
3. Avanzi, R. M. A note on the sliding window integer recoding and its left-to-rightanalogue. In Selected Areas in Cryptography – SAC 2004 (2005), H. Handschuh and
M. A. Hasan, Eds., vol. 3357 of Lecture Notes in Computer Science, pp. 130–143.
4. Bernstein, D. J. Pippenger’s exponentiation algorithm. Draft, 2002. Available
from http://cr.yp.to/papers.html#pippenger.
5. Brickell, E. F., Gordon, D. M., McCurley, K. S., and Wilson, D. B. Fast
exponentiation with precomputation. In Advances in Cryptology – EUROCRYPT’92 (1993), R. A. Rueppel, Ed., vol. 658 of Lecture Notes in Computer Science,
pp. 200–207.
6. Certicom Research. Standards for efficient cryptography – SEC 2: Recommended elliptic curve cryptography domain parameters. Version 1.0, 2000. Available from http://www.secg.org/.
7. Cohen, H., Ono, T., and Miyaji, A. Efficient elliptic curve exponentiation using
mixed coordinates. In Advances in Cryptology – ASIACRYPT ’98 (1998), K. Ohta
and D. Pei, Eds., vol. 1514 of Lecture Notes in Computer Science, pp. 51–65.
8. de Rooij, P. Efficient exponentiation using precomputation and vector addition
chains. In Advances in Cryptology – EUROCRYPT ’94 (1995), T. Helleseth, Ed.,
vol. 950 of Lecture Notes in Computer Science, pp. 389–399.
9. Gordon, D. M. A survey of fast exponentiation methods. Journal of Algorithms
27 (1998), 129–146.
10. Institute of Electrical and Electronics Engineers (IEEE). IEEE standard specifications for public-key cryptography. IEEE Std 1363-2000, 2000.
11. Khabbazian, M., and Gulliver, T. A. A new minimal average weight representation for left-to-right point multiplication methods. Cryptology ePrint Archive
Report 2004/266, 2004. Available from http://eprint.iacr.org/.
12. Lim, C. H., and Lee, P. J. More flexible exponentiation with precomputation.
In Advances in Cryptology – CRYPTO ’94 (1994), Y. G. Desmedt, Ed., vol. 839
of Lecture Notes in Computer Science, pp. 95–107.
13. Miyaji, A., Ono, T., and Cohen, H. Efficient elliptic curve exponentiation. In
International Conference on Information and Communications Security – ICICS’97 (1997), Y. Han, T. Okamoto, and S. Qing, Eds., vol. 1334 of Lecture Notes in
Computer Science, pp. 282–290.
14. Möller, B. Algorithms for multi-exponentiation. In Selected Areas in Cryptography – SAC 2001 (2001), S. Vaudenay and A. M. Youssef, Eds., vol. 2259 of Lecture
Notes in Computer Science, pp. 165–180.

13

15. Möller, B. Improved techniques for fast exponentiation. In Information Security
and Cryptology – ICISC 2002 (2003), P. J. Lee and C. H. Lim, Eds., vol. 2587 of
Lecture Notes in Computer Science, pp. 298–312.
16. Möller, B. Fractional windows revisited: Improved signed-digit representations
for efficient exponentiation. In Information Security and Cryptology – ICISC 2004
(2005), C. Park and S. Chee, Eds., vol. 3506 of Lecture Notes in Computer Science,
pp. 137–153.
17. Muir, J. A., and Stinson, D. R. New minimal weight representations forleft-to-right window methods. In Topics in Cryptology – CT-RSA 2005 (2005),
A. Menezes, Ed., vol. 3376 of Lecture Notes in Computer Science, pp. 366–383.
18. Muir, J. A., and Stinson, D. R. Minimality and other properties of the width-w
nonadjacent form. Mathematics of Computation 75 (2006), 369–384.
19. National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS). FIPS PUB 186-2, 2000.
20. Okeya, K., Schmidt-Samoa, K., Spahn, C., and Takagi, T. Signed binary
representations revisited. In Advances in Cryptology – CRYPTO 2004 (2004),
M. Franklin, Ed., vol. 3152 of Lecture Notes in Computer Science, pp. 123–139.
21. Pippenger, N. The minimum number of edges in graphs with prescribed paths.
Mathematical Systems Theory 12 (1979), 325–346.
22. Pippenger, N. On the evaluation of powers and monomials. SIAM Journal on
Computing 9 (1980), 230–250.
23. Schmidt-Samoa, K., Semay, O., and Takagi, T. Analysis of fractional window
recoding methods and their application to elliptic curve cryptosystems. IEEE
Transactions on Computers 55 (2006), 48–57.
24. Struik, M., Brown, D. R., Vanstone, S. A., Gallant, R. P., Antipa, A.,
and Lambert, R. J. Accelerated verification of digital signatures and public keys.
United States Patent Application Publication US 2007/0064932 A1, 2007.

A

An Example

As an illustrative toy example, let us apply our new technique to multiexponentiations g1d · g2e with exponents of size at most ` = 18 bits. To keep
the example simple, we use unsigned-digit (instead of signed-digit) exponent
representations. Let the digit sets for the fixed base be B2 = {1, 3, 5, 7, 0}. For
radix-2 and modular exponent splitting, we use splitting parameter s = 3. Thus,
126
g2 is replaced a priori by three fixed bases g2 , g3 , g4 where g3 = g22 , g4 = g22 .
Accordingly, we precompute the powers(g2 , g23 , g25 , g27 , g3 , g33 , g35 , g37 , g4 , g43 , g45 , g47 )and save this data in ROM. We consider an environment with a limited amount offast read/write memory and assume that we have only space to store 8 powers ofthe variable base g1 . Hence, we can choose digit set B1 = {1, 3, . . . , 15, 0} for exponentiations with a new base (Section 3.1) and digit sets B1 = {1, 3, 0}, BG1 =
BG2 = {1, 3, 5, 0} for exponentiations with an old base (Section 3.2).
14

Multi-Exponentiation for a New Base g1 . Let us now consider the computation of g1d · g2e for d = 205802 = (110010001111101010)2 and e = 245153 =(111011110110100001)2 where g1 is a new base, i.e. no cached precomputed data
based on g1 is available. Before the actual multi-exponentiation, we compute thepowers(g1 , g13 , . . . , g115 )and save these in fast read/write memory. Encoding e1 := d using B1 yields
e1 = (3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 15, 0, 0, 5, 0, 1, 0)2 .
Encoding e using B2 and then splitting into three parts e2 , e3 , e4 yields(7, 0, 0, 0)2 ,e4 =e3 = (7, 0, 0, 5, 0, 0)2 ,e2 = (5, 0, 0, 0, 0, 1)2 .
The following Qtable shows what happens while performing the multi4
exponentation i=1 giei as described in Section 3.1, based on interleaved multiexponentiation as explained in Section 2.1:
j A
Cache entry (so far)
17 1
(g1 )
16 g133
13 (g13 )2 g1 = g125`´
25 2
12 (g1 ) = g150
g1 , (50, g150 )`´
6
g1 , (3215, g13215 ), (50, g150 )
6 (g150 )2 g115 = g13215
6430 5 73215 2 5 7
5 (g1 ) g2 g3 = g1 g2 g3
2
3 (g16430 g25 g37 )2 g15 g47 = g125725 g220 g328 g47
25725 20 28 7 2 5
2 (g1g2 g3 g4 ) g3 = g151450 g240 g361 g414
51450 40 61 14 2
1 (g1
g2 g3 g4 ) g1 = g1102901 g280 g3122 g428
102901 80 122 28 2
0 (g1g2 g3 g4 ) g2 = g1205802 g2161 g3244 g456

As we can see here, until and including round j = 6, the variable A contains nopowers of bases other than g1 . Intermediate powers of g1 for caching are available
at the points j = 12 and j = 6 of the computation.
Multi-Exponentiation for an Old Base g1 . Let us compute g1d ·g2e for d = 73660 =(10001111110111100)2 , e = 236424 = (111001101110001000)2 where g1 is an oldbase for which the cache entry(g1 , (λ1 = 3215, G1 = g13215 ), (λ2 = 50, G2 = g150 ))as created above is available. First, the powers(g1 , g13 , G1 , G31 , G51 , G2 , G32 , G52 )15

are precomputed and stored in fast read/write memory. Next, we perform modular exponent splitting as described in Section 3.2:
d0 = d =73660,
E1 = λd01 = 22 and d1 = d0 − E1 λ1 = 2930,
 
E2 = λd12 = 58 and d2 = d1 − E2 λ2 = 30,
E3 = d2 = 30
Encoding E1 , E2 and E3 using BG1 , BG2 and B1 yields
E1 = (10110)2 =(5, 1, 0)2 ,E2 = (111010)2 = (3, 0, 0, 5, 0)2 ,E3 = (11110)2 = (3, 0, 3, 0)2 .
By encoding e using B2 and then splitting into 3 parts e2 , e3 , e4 (using radix-2
exponent splitting), we obtaine4 =(7, 0, 0, 0)2 ,e3 = (3, 0, 0, 0, 7, 0)2 ,e2 =(1, 0, 0, 0)2 .
The table below shows what happens in the interleaved multi-exponentiation toE2 E3 e2 e3 e4
1compute GE
1 G2 g1 g2 g3 g4 :
j A
5 g33
4 (g33 )2 G32 = G32 g36
3 (G32 g36 )2 g13 g2 g47 = G62 g13 g2 g312 g47
6 2 24 14
2 (G62 g13 g2 g312 g47 )2 G51 = G51 G12
2 g1 g2 g3 g4
5 12 6 2 24 14 25 3 7
29 15 4 55 28
1 (G1 G2 g1 g2 g3 g4 ) G1 G2 g1 g3 = G11
1 G2 g1 g2 g3 g4
29 15 4 55 28 2
22 58 30 8 110 56
0 (G11
G
g
g
g
g
)
=
G
G
g
g
g
1
2 1 2 3 41
2 1 2 3 g4

B

Implementation Aspects

On-The-Fly Signed-Digit Conversions. In our descriptions of multiexponentiation algorithms, we have employed radix-2 representations of exponents by referring to their individual digits. However, this by no means is meant
to imply that these digits need to be explicitly obtained and stored in advance,
which would be quite inconvenient if memory is scarce. Left-to-right signed fractional window representations [11, 23, 16] are very convenient for our purposessince (for any given maximum digit value m) there is a finite-state machine thattransforms the binary representation into the corresponding signed-digit representation. As the name suggests, this conversion machine starts at the most significant digit (“left”) and continues towards the least significant digit (“right”).
Since interleaved multi-exponentiation is a left-to-right technique as well, thisoften means that the signed digits can be obtained on the fly.
To make this work with radix-2 exponent splitting, we need to add an additional first left-to-right pass through the binary representation. This is essentially16

a dry run of the signed fractional window conversion, used to determine the firstbinary digits that will affect each of the segments of the signed-digit representation. For s-fold radix-2 exponent splitting, such a dry run can be used to initialize
each of s finite-state machines, which afterwards can be used to obtain the digitsof the individual segments (exactly as in the case of the on-the-fly conversion
using just a single such machine that we would use in the case without splitting).
A simpler alternative would be to first split the binary representation, andthen generate the signed-digit representations individually. This could be done
truly on the fly, i.e., without the additional left-to-right pass. However, thisstrategy often will increase the total weight of the resulting representations [15],so the two-pass technique usually should lead to better performance.
Variants of the Signed Fractional Window Representation. In our performance estimates in Section 4, we optimistically assumed that besides ROM
and fast read/write memory, there is another kind of memory that we can use
for the cache. This is an assumption that we made for simplicity, but which is
not necessary. In fact we may use some of the fast read/write memory for a small
cache without completely losing this memory for precomputed powers of g1 .
This can be achieved by observing that we may modify the parameter m forthe left-to-right signed fractional window representation while performing theconversion. Thus, in the algorithm from Section 3.1, provided that m ≥ 2s − 1,
we may initially use some maximum-size digit set B ± (m) = {±1, ±3, . . ., ±m, 0}
for signed digits b1,` down to b1,L1 +···+Ls−1 , then cache the current group el(b1,` ,...,b1,L +···+L

)2

1
s−1
ement g1in the memory space that so far held g1m , andthen use the smaller digit set B ± (m − 2) for subsequent digits b1,L1 +···+Ls−1 −1
down to b1,L1 +···+Ls−2 . Continuing in this fashion, we eventually give up digits±m, ±(m − 2), . . ., ± m − 2(s − 1) .

C

Performance Comparison

This appendix demonstrates the merits of our new technique for multiexponentiation with caching in one particular situation where very little memory
is available for use as a cache. We show that our method is of advantage evenunder this severe restriction. We make the following assumptions:– We look at two-fold multi-exponentiation, g1e1 g2e2 . Base element g2 is fixed;base element g1 is variable such that the current value will repeat in the
directly following multi-exponentiation with probability Pold = 12 .
– The exponents e1 and e2 are uniformly random integers up to ` = 256 bits.
– Storage is available for 128 fixed precomputed elements in read-only memory(derived from the fixed base g2 ), and for only 2 precomputed elements inread/write memory. The latter includes input value g1 . In addition to this,we have space for variable A in the algorithm from Section 2.1, and thememory holding the exponents. (Note that typically the memory needed forthe exponents is less than the memory needed for a single group element: for17

elliptic curve cryptography using projective coordinates over a 256-bit field,
one group element takes 768 bits.)– Different from the assumptions as used in Section 4, we have no additional
cache memory. That is, a group element to be cached has to be kept in oneof the two read/write storage units for precomputed elements.
– We use rough estimates S = 0.7 and M = 1 for the amount of time spent oneach group squaring (e.g., elliptic curve point doubling) and on each group
multiplication (e.g., elliptic curve point addition). (For example, when using
Jacobian projective coordinates for elliptic curves over prime fields, a point
doubling takes 10 or 8 field multiplications depending on the curve, anda general point addition requires 16 field multiplications [10], or 11 field
multiplications in the case of “mixed coordinates” [7]. Mixed coordinates
require a one-time conversion step to one of the inputs to convert it into
affine coordinates, which is reasonable for precomputed values. Accordingly,
8S
11 ≈ 0.73 is one way to justify our estimate M ≈ 0.7, although in thefollowing we neglect the cost of the conversion.)If (instead of applying our new caching strategy) we directly use interleaved
multi-exponentiation in this situation, employing signed-digit representation as
explained in Section 2.1, we can keep precomputed values g2 , g23 , g25 , . . ., g 255 inread-only memory, and use read/write memory for g1 and g13 , thus achieving an
exponentiation cost of approximately 256 256 +
M + 255S ≈ 268.1
4
10(or 89.5M + 254S ≈ 267.3 according to experimental simulation results) plus
1M +1S = 1.7 to precompute g13 from g1 when g1 has changed from the previous
computation. By assumption, this happens with probability 21 , resulting in a
total estimate of 268.1 + 1.7
2 ≈ 269.0 (for the simulation: 268.2).
Our method initially performs worse than this, namely, in the case with a newbase (Section 3.1). Here, the read-only memory will contain g2 , g23 , g25 , . . ., g 127 ,128plus similar powers of g22 . The read/write memory initially is filled with precomputed elements g1 and g13 . To perform the multi-exponentiation as describedin Section 3.1, we use radix-2 exponent splitting for exponent e2 to obtain partial
exponent representations no longer than 129 digits. For exponent e1 , we use asigned fractional window representation variant as sketched in Appendix B, i.e.,
where digit set parameter m is modified within the conversion: the more significant digits can use digits set {±1, ±3, 0}, whereas the less significant digits(digits b1,127 , . . .b1,0 ) are restricted to digit set {±1, 0}. This is because we nolonger keep g13 in memory when the method from Section 3.1 has determineda group element to be cached, thus freeing a memory location for use as cachespace. The performance estimate for this multi-exponentiation is 128 128 256 ++
M + 255S ≈ 281.6
4
3
9(simulation: 102.7M + 253.8S ≈ 280.4) plus 1M + 1S ≈ 1.7 to precompute g13
from g1 . We benefit from the extra effort put into this computation whenever18

the same g1 reappears in the following multi-exponentiation. In this case, themulti-exponentiation will only take approximate effort
 128
3

+

128 256 
M + 127S ≈ 202.7+
3
9(simulation: 113.9M + 128.2S ≈ 203.6). The average cost given Pold = 12 comesto 242.1 (simulation: 242.0). Thus, our method provides an average 10 percent
performance improvement in this scenario.

19