Technical Report TI-8/01 (27th April 2001)
TU Darmstadt, Fachbereich Informatik

Algorithms for multi-exponentiation
Bodo Möller
Technische Universität Darmstadt, Fachbereich Informatik
moeller@cdc.informatik.tu-darmstadt.de

Abstract. ThisQpaper compares different approaches for computing
power products 1≤i≤k giei in finite groups. We look at the conventional
simultaneous exponentiation approach and present an alternative strategy, interleaving exponentiation. Our comparison shows that in generalgroups, sometimes the conventional method and sometimes interleaving
exponentiation is more efficient. In groups where inverting elements iseasy (e.g. elliptic curves), interleaving exponentiation with signed exponent recoding usually wins over the conventional method.

1

Introduction

A common task in implementations of many public-key cryptosystems is multiexponentiation in some commutative group G, i.e. evaluating a product
Y
giei
1≤i≤k

where k ≥ 2 is a small integer, each gi is an element of G, and each ei is an
integer (typically a few hundred up to a few thousand bits long). We require thatthe ei be non-negative (otherwise, invert gi ). Example groups include (Z/nZ)∗
for some integer n (e.g., for verification of ElGamal [9] or DSA [15] signatures),groups of rational points on elliptic curves over finite fields (e.g., for verification of
ECDSA [1] signatures), or class groups of imaginary-quadratic orders (e.g., forverification of RDSA [2][6] signatures). We have k = 2 for DSA and ECDSA
verification and k = 3 for ElGamal and RDSA verification. Larger values of k
appear in protocols of Brands [4]. In the present paper, we allow k = 1 as well
for algorithms; efficiency considerations may ignore this case. It is well known
that for k > 1 it is unnecessarily inefficient to compute the powers giei separately
and then multiply them. Instead, specific algorithms for multi-exponentiation
are usually applied.
We assume that the ei consist of independent random bits up to a respective
maximum bit-length bi ; i.e., ei is a uniformly distributed random integer in theinterval [0, 2bi − 1]. (In practice the actual distribution may differ, but for typicalcases this simplified assumption is reasonably close.) In this setting, we consider
general algorithms for arbitrary exponents; we do not examine algorithms basedon tailor-made addition chains in Zk for given e1 , . . ., ek (cf. [3]). (Note that even
if an exponent is fixed in a cryptographic protocol, it is sometimes desirable to1

perform computations using varying exponents in order to thwart side-channel
attacks that try to use timings [10] or power consumption measurements [11]or other extra data to gain knowledge on secret exponents.
Q ei To avoid constanten·ord(g)+e
exponents,gcanberewritten
as
g
,
and
gi can be rewritten as
QQ( gi )n giei −n for arbitrary integers n.)
Like window-based algorithms for single exponentiations, the algorithms that
we analyze work in two stages: First, in the precomputation stage, an auxiliary
table of group elements is computed from the elements gi ; then, in the evaluation
stage, the final result is computed using these auxiliary values.
The usual approach for multi-exponentiation combines all input group elements gi with each other in the precomputation stage ([9], [17], [18]); then theevaluation stage looks at all exponents simultaneously. In the present paper, we
discuss an alternative approach where the gi are treated separately in the precomputation stage. In this approach, the evaluation stage uses an interleavingof the generators and exponents for the various i rather than handling multiple
i simultaneously.
We collectively refer to the multi-exponentiation methods described in [9],[17] and [18] as “simultaneous exponentiation”. Section 2 describes these methods. Section 3 presents two variants of our alternative approach, which we dub“interleaving exponentiation”: a basic method and an alternative method thatcan be used in groups where inverting elements is easy. In section 4, we compare
the efficiency of simultaneous exponentiation methods and interleaving exponentiation methods. Section 5 discusses a variant of interleaving exponentiationthat is sometimes advantegeous when all bases gi are fixed.
In specific groups, additional useful efficiently computable endomorphisms
are available besides squaring and possibly inversion (see e.g. [16]); this maylead to better multi-exponentiation algorithms for these groups. Such specialgroups are out of the scope of the present paper.
1.1

Notation

We write e[j] for bit j of a non-negative integer e (j ≥ 0). For negative j,
we define that e[j] = 0. We write e[j . . . j 0 ] for the integer consisting of theconcatenation of bits j down to j 0 of e; e.g., if e = 101112 = 39, then e[3 . . . 1] =0112 = 3 and e[1 . . . −2] = 11002 = 12.

2

Simultaneous exponentiation methods

We look at two multi-exponentiation methods using simultaneous exponentiation(as opposed to interleaving exponentiation, which is introduced in section 3):
Straus’s 2w -ary method (section 2.1) and the sliding window method of Yen,
Laih, and Lenstra (section 2.2). (The method known as “Shamir’s trick” appears
as a special case of both of these.)
As noted in the introduction, all algorithms that we consider are related andwork in two stages: a first precomputation stage yielding an auxiliary table of2

group elements and a second evaluation stage that computes the final result
using this table. For comparing different methods, we examine the two stages
separately.
When examining simultaneous exponentiation algorithms, we assume that bi
is the same for all i. Let at least one ei be non-zero, and let b be the bit-lengthof the longest of the ei . Parameter w is always a positive integer, the “windowsize”; larger window sizes make the precomputation stage less efficient, but speed
up the evaluation stage. It is not possible to give a general rule for selecting an
optimal w (cf. section 4).
Relevant features of the precomputation stage are the number of group operations required for computing the auxiliary table, and the number of table
entries. For group operations, we differentiate between squarings and generalmultiplications, since the former often can be computed more efficiently. The
precomputed tables will always contain the values g1 , . . ., gn , all of which aretrivially available and hence can be neglected. It will be visible that computing
each additional table entry requires one multiplication or, for some of the table
entries in the simultaneous 2w -ary method, one squaring. In addition to this, ksquarings are necessary if w > 1.
The evaluation stage requires both squarings and multiplications. For each
multi-exponentiation method, we look at number of squarings and the expected
number of general multiplications for given k, b, and w. w is assumed to besmall in comparison to b (otherwise the precomputation stage would become
unreasonably expensive).
It should be noted that a slight optimisation for the precomputation stage ispossible in all methods by first looking which table entries are actually needed(either during the evaluation stage, or because other precomputed table entries
that are needed in the evaluation stage depend on them) and limiting precomputation to these. As this optimisation will usually only have a small effect inpractice, we neglect it in our comparisons.
For the number of squarings in the evaluation stage, we assume that thefollowing optimisation is used: As initially variable A is 1G (the neutral elementof G) in all algorithms, squarings can easily be avoided until a different value
has been assigned to A.
Formulas for the expected number of multiplications during the evaluation
stage given in the following are actually asymptotics for large b/w rather than
precise values (we do not take into account the special probability distributions
encountered at both ends of the exponents). As b/w is small in practice, theerror is negligible for our purposes.
Just as squarings can be optimised away in the evaluation stage while A is
1G , the first multiplication of A by a table entry can be replaced by an assignment. This minor optimisation is not used in our figures below; note that it
applies similarly to all algorithms discussed in this paper (and does not affectasymptotics), so comparisons between different methods remain just as valid.
3

2.1

Simultaneous 2w -ary method

The simultaneous 2w -ary exponentiation method [17] (see also [13]) looks at
w bits of each of the exponents for each evaluation stage group multiplication(where w is a small positive integer), i.e. kw bits in total. The special case wherew = 1 is also known as “Shamir’s trick” since it was described in [9] with areference to Shamir.
Q
Precomputation stage Precompute 1≤i≤k giEi for all non-zero k-tuples (E1 ,. . ., Ek ) ∈ {0, . . ., 2w − 1}k .
Number of non-trivial table entries: 2kw − 1 − k. Of these, 2k(w−1) − 1 can becomputed by squaring other table entries (all the Ei are even). The remaining
2kw − 2k(w−1) − k entries require one general multiplication each.
No additional squarings are required.
Evaluation stage
A ← 1G
for j = b(b − 1)/wcw down to 0 step w dofor n = 1 to w do
A ← A2

if e1 [j + w − 1 . . . j], . . ., ek [j + w − 1 . . . j] 6= (0, . . ., 0) thenQ e [j+w−1 ... j]A ← A · i gi i{multiply A by table entry}
return A
kj
1 w.
Number of squarings: b −w
1
1 − 2kw
Expected number of multiplications: b ·w .
2.2

Simultaneous sliding window method

The simultaneous sliding window exponentiation method of Yen, Laih, andA. Lenstra [18] is an improvement of the 2w -ary method described in section 2.1.
Due to the use of a sliding window, table entries are required only for those tuples (E1 , . . . , Ek ) where at least one of the Ek is odd; also the expected numberof multiplications required in the evaluation stage is reduced. Like the 2w -arymethod, this method looks at w bits of each of the exponents for each evaluation
stage group multiplication (kw bits in total). For w = 1, this again is “Shamir’s
trick”.
Q
Precomputation stage Precompute 1≤i≤k giEi for all k-tuples (E1 , . . ., Ek ) ∈{0, . . ., 2w − 1}k where at least one of the Ek is odd.
Number of non-trivial table entries (multiplications): 2kw − 2k(w−1) − k.
Number of squarings: k if w > 1; none otherwise.
4

Evaluation stage
A ← 1Gj ←b−1
while j ≥ 0 do
if ∀i ∈ {1, . . ., k} : ei [j] = 0 thenA ← A2 ; j ← j − 1else
jnew ← max(j − w, −1)
J ← jnew + 1
while ∀i ∈ {1, . . ., k} : ei [J] = 0 do
J ←J +1{now j ≥ J > jnew }for i = 1 to k do
Ei ← ei [j . . . J]
while j ≥ J do
2
A ← AQ; j ←j−1
A ← A · i giEi {multiply A by table entry}
while j > jnew do
A ← A2 ; j ← j − 1
return A
Number of squarings: b − w up to b − 1.
1
P1.
Expected number of multiplications: b ·1 =b·
w + n≥1 2kn
w + 2k1−1

3Interleaving exponentiation methods

Here, we look at two interleaving exponentiation algorithms: A basic algorithm
suitable for arbitrary groups (section 3.1) and a special variant using signed
exponent recoding that can be applied if inverting elements is easy (section 3.2).
The comments in the introduction to section 2 apply similarly, with the
exception that we no longer assume all the bi to be identical. Instead of a single
window size w, in this section we have k possibly different window sizes wi(1 ≤ i ≤ k) used for the respective parts of the multi-exponentiation; each wi isa small positive integer.
Note that for the algorithms described in this section, the precomputed table has disjoint parts for different exponents gi . If multiple multi-exponentiations
have to be performed and some of the bases gi appear again, then the corresponding parts of earlier precomputed tables can be reused.
3.1

Basic interleaving exponentiation method

The basic interleaving exponentiation method is a generalization of the sliding
window method for a single exponentiation (see e.g. [13]), to which it corresponds
in case k = 1.
5

Precomputation stage For i = 1, . . ., k, precompute giE for all odd E suchthat 1 ≤ E ≤ 2wi − 1.

P
wi −1
Number of non-trivial table entries (multiplications):− k.
1≤i≤k 2

Number of squarings: # i ∈ {1, . . ., k} | wi > 1 .
Evaluation stage
A ← 1G
for i = 1 to k dowindow handle i ← nil
for j = b − 1 down to 0 do
A ← A2for i = 1 to k do
if window handle i = nil and ei [j] = 1 thenJ ← j − wi + 1
while ei [J] = 0 do
J ←J +1{now j ≥ J > j − w and J ≥ 0}
window handle i ← J
Ei ← ei [j . . . J]
if window handle i = j thenA ← A · giEi {multiply A by table entry}
window handle i ← nil
return A
Number of squarings: b − maxi wi up to b − 1.
P
P
1 .
P1
Expected number of multiplications: b·
1 = b·
w
+1
i
w
+
n
i
1≤i≤k
1≤i≤k
n≥1 2
3.2

wNAF-based interleaving exponentiation method

In some groups, elements can be inverted very efficiently so that division is not
significantly more expensive than multiplication. (Inversion is cheap in case of
elliptic curves or class groups of imaginary quadratic number fields, but notin (Z/nZ)∗ .) This can be exploited for making exponentiation algorithms more
efficient by recoding the exponents into a signed representation. We use thetechnique introduced for single exponentiations in [14] and apply it to the taskof multi-exponentiation.
Given an exponent ei and a window size wi , we need a width-(wi + 1) nonadjacent form (width-(wi + 1) NAF or wNAF ) of ei , which is an array Ni [bi ], . . .,Ni [0] of integers such that– each P
Ni [j] is either 0 or odd with an absolute value less than 2wi ;– ei = 0≤j≤bi Ni [j] · 2j ;– at most one of any wi + 1 consecutive components of the array is non-zero.
A width-(wi + 1) NAFs always exists and is uniquely determined; it can becomputed by the following algorithm [16]:6c ← eij←0while c > 0 do
if c[0] = 1 thenu ← c[wi . . . 0]
if u[wi ] = 1 thenu ← u − 2wi +1
c←c−u
else
u←0
Ni [j] ← u; j ← j + 1c ← c/2
while j ≤ bi do
Ni [j] ← 0; j ← j + 1
return Ni [bi ], . . ., Ni [0]The maximum possible index for a non-zero component of the wNAF of a
B-bit integer is B; i.e., the length of the wNAF without leading zeros may exceed
the length of the binary expansion by one. The average density (proportion of
non-zero components) in width-(wi + 1) NAFs is 1/(wi + 2) for B → ∞ [16].
Precomputation stage For i = 1, . . ., k, precompute giE for all odd E suchthat 1 ≤ E ≤ 2wi − 1. (As inversion in G is assumed to be easy, this makes gi−E
available as well.)

P
wi −1
Number of non-trivial table entries (multiplications):− k.
1≤i≤k 2

Number of squarings: # i ∈ {1, . . ., k} | wi > 1 .
Evaluation stage
A ← 1G
for i = 1 to k do
Ni [b], . . ., Ni [bi + 1] ← 0, . . ., 0Ni [bi ], . . ., Ni [0] ← width-(wi + 1) NAF of ei
for j = b down to 0 do
A ← A2for i = 1 to k do
if Ni [j] 6= 0 thenN [j]A ← A · gi i {multiply A by [inverse of] table entry}
return A
Number of squarings: b − maxi wi up to b.
P
Expected number of multiplications: b · 1≤i≤k w 1+ 2 .
i
We can compare wNAFs with the sliding window technique of the basic interleaving exponentiation algorithm. Windows can be represented by components
of an array as in the wNAF approach: In the algorithm description of section 3.1,
7

Ei provides component values; array indexes are given by window handle i . With
the array filled in accordingly, we can use the same evaluation stage algorithm
as in the wNAF-based method. The average density is 1/(wi + 1) (each window
covers wi bits, and the number of additional zero bits between neighbouring windows is 1 on average). With wNAFs, the average density goes down to 1/(wi +2)
for exactly the same precomputation. Thus using wNAFs effectively increases
the window size by one.

4

Comparison of simultaneous and interleaving
exponentiation methods

There is no general rule for selecting window sizes for the multi-exponentiation
algorithms that we have looked at. Various factors have to be considered: Firstof all, absolute memory constraints can impose limits on possible window sizes.
Second, even if a particular window size appears to minimize the total amountof computation for a multi-exponentiation, sometimes slightly smaller windows
may improve the actual performance; this is because larger window sizes mean
larger precomputed tables, i.e. possibly additional memory allocation overhead
and less effective memory caching. Last but not least, implementations can use
different representations for group elements during different stages of the multiexponentiation: For instance, extra effort may be spent during the precomputation stage in order to obtain representations of precomputed elements that speed
up multiplication with them in the evaluation stage. (Concrete examples for thecase of single exponentiations in elliptic curves over finite prime fields can befound in [7]: Various kinds of coordinates are available for representing points.)
These effects, however, do not mean that we cannot compare algorithms without looking at concrete cases: We can compare different aspects separately (tablesize, precomputation stage efficiency, evaluation stage efficiency) and check if analgorithm wins on all counts.
For the following comparisons, we assume that all maximum exponent lengths
bi are the same (an assumption that we made in section 2 on simultaneous
exponentiation methods, but not in section 3 on interleaving exponentiation
methods). As before, let b be the length of the largest of the exponents ei .
In section 4.1, we compare the simultaneous 2w -ary method with the basic
interleaving method and show that the latter is usually more efficient for k = 2 if
squarings are about as costly as multiplications. In section 4.2, we compare thesimultaneous sliding window method with the wNAF-based interleaving method
and show that the latter is more efficient for k = 2 and k = 3, assuming thatcomputing and storing the wNAFs is not too costly. Section 4.3 shortly discusses
the alternative multi-exponentiation method from [8] and shows that is obviatedby our interleaving exponentiation methods. Finally, in section 4.4, we look atsome concrete figures for the number of multiplications required by different
methods for example values of k and b.
8

4.1

Comparison between the simultaneous 2w -ary method and thebasic interleaving method

While the simultaneous sliding window method is more efficient than the simultaneous 2w -ary method, this section focusses on the latter. The reasons isthat the 2w -ary method is often used in practice (e.g. [5]), possibly because itis perceived to be simpler to implement. The basic interleaving exponentiation
method is not too complicated, and as we will see, it is often more efficient than
the simultaneous 2w -ary exponentiation method. So when the intention is to
avoid the simultaneous sliding window method, the basic interleaving method
appears preferable for many applications.
Assume that, given k and b, a certain w turns out to provide optimal efficiency
for the simultaneous 2w -ary exponentiation method (section 2.1) when performed
in a specific environment. Then the precomputation table requires 2kw − 1 − knon-trivial entries, 2k(w−1) − 1 of which can be computed with one squaring each
(while each of the remaining entries requires one general multiplication).
For the basic interleaving exponentiation method (section 3.1), we can use
uniform window sizes w1 = . . . = wk = kw. Then the precomputation table has
k2kw−1 − k non-trivial entries, each of which requires one general multiplication;
also k additional squarings are needed (unless k = w = 1).
Thus in case k = 2, the table grows from 22w −3 to 22w −2 non-trivial entries,
and instead of 22w − 3 group operations of which 22(w−1) − 1 are squarings,
we need 22w group operations of which only 2 are squarings. If squarings areabout as expensive as general multiplications, then for k = 2 the overall cost of
precomputation is comparable for these two multi-exponentiation methods.
The number of squarings in the evaluation stage is always nearly b for bothmethods. The expected number of general multiplications in the evaluation stage
is smaller for the interleaving method (except if k = w = 1, in which case bothalgorithms do exactly the same): Dividing the value for the basic interleaving
exponentiation method by the value for the simultaneous 2w -ary exponentiation
method yields
2kw
k
kw
w
=
·
,
·
1
kw + 1 2kw − 1
kw + 1 1 − 2kw
and this is less than 1 for kw > 1 (the minimum is 64/75 at kw = 4).
Note that using w1 = . . . = wk = kw is not necessarily an optimal choice of
window sizes for the basic interleaving exponentiation method; using smaller orlarger windows might lead to better performance. (Indeed, if we look just at the
number of operations and ignore memory usage, then there is no reason why thewindow size should depend on k.) While the above proof only covers the casek = 2, there are actually many other cases where the basic interleaving method
is more efficient than the simultaneous 2w -ary method, even if general multiplications are much more expensive than squaring; see table 1 in section 4.4. Also
note that the precomputation effort grows exponentially in k in simultaneous
methods, but not in interleaving methods.
94.2

Comparison between the simultaneous sliding window method
and the wNAF-based interleaving method

Similarly to section 4.1, assume that a certain w provides optimal efficiency forthe simultaneous sliding window exponentiation method (section 2.2) for given
k and b. In the following analysis, we require k > 1. The precomputation tablehas 2kw − 2k(w−1) − k non-trivial entries, each of which requires one generalmultiplication to compute. In addition to this, k squarings are required for precomputation unless w = 1.
For the wNAF-based interleaving exponentiation method (section 3.2), we
can use window sizes w1 = . . . = wk = kw − 1. This leads to a precomputationtable with k2kw−2 − k non-trivial entries, requiring one general multiplication
each. In addition to this, we need k squarings unless kw = 2.
The difference between the number of non-trivial tables entries (and generalmultiplications) for these two methods isk(2kw − 2k(w−1) − k) − (k2kw−2 − k) = 2kw 1 − 2−k −.
4This is positive for k ≤ 3 and negative for k ≥ 4. Thus, with the wi chosen like
this, the precomputation stage of the wNAF-based interleaving exponentiation
method is more efficient if k = 2 or k = 3 (except for the case k = 3, w = 1,
where the wNAF-based interleaving exponentiation method saves one generalmultiplication, but requires three additional squarings).
The evaluation stage requires close to b squarings for both methods. The
expected number of general multiplications is smaller for the wNAF-based interleaving method: b/(w + 1/k) instead of b/(w + 2k1−1 ).
The wNAF-based interleaving method will often provide better performance
than the simultaneous sliding window method for k ≥ 4 as well: If additional
memory allocation is not a problem, then the efficiency gain of the evaluation
stage usually compensates for the growth of the precomputed table.
Similar to the situation in the preceding section, w1 = . . . = wk = kw − 1 is
not necessarily an optimal choice, and smaller or larger window sizes might bebetter (see section 4.4).
4.3

Comparison between the Dimitrov-Jullien-Miller
multi-exponentiation method and interleaving exponentiation

A multi-exponentiation method for the case k = 2 requiring two precomputed
values (in addition to g1 and g2 ) if inverting is easy, or six precomputed values
if inversions have to be done during the precomputation stage, was describedby Dimitrov, Jullien, and Miller in [8]. This algorithm is related to the simultaneous sliding window exponentiation method of Yen, Laih, and Lenstra [18](section 2.2 in the present paper), but uses signed recoding of exponents in order to reduce the size of the precomputed table. While the Yen-Laih-Lenstra
method with a window size of 1 requires an expected number of b · 0.75 generalmultiplications during the evaluation stage, the new method requires only about10b · 0.534 multiplications according to [8] (the number of squarings stays about
the same). Yen-Laih-Lenstra with a window size of 2 needs only b · 3/7 ≈ b · 0.429
multiplications (table 3 of [8] erroneously assumes a value of b·0.625), but has the
disadvantage of requiring more precomputed elements, which may be a problem
in some constrained environments.
We do not examine the algorithm of [8] in detail; note that it is outperformedby the wNAF-based interleaving method of section 3.2 with w1 = w2 = 2 if inversion is cheap (two precomputed values, b·0.5 multiplications) and by the basic
interleaving method of section 3.1 with w1 = w2 = 3 otherwise (six precomputed
values, b · 0.5 multiplications).
4.4

ExamplesAs noted before, endless variations are possible for defining optimisation goals.
In this section, we ignore memory usage and squarings and the issue of different element representations; we make comparisons based just on the expected
number of general multiplications required by the various methods. Note thatthe number of squarings is approximately the same for the simultaneous sliding
window method, the basic interleaving method, and the wNAF-based interleaving method: No more than k squarings are needed in the precomputation stage,
and close to b squarings are needed in the evaluation stage. The simultaneous
2w -ary method requires the above plus 2k(w−1) − 1 squarings; so ignoring thecost of squaring tends to favour this method.
Table 1 compares the number of general multiplications needed by these four
methods for various k and b values. The entries for the most efficient methods ina particular configuration are printed in bold: For groups where inversion is easyso that the wNAF-based method can be used, it wins in all of these examples; forgeneral groups, sometimes the simultaneous sliding window method and sometimes the basic interleaving method requires the least number of multiplications.
(Remember that for w = 1 there is no difference between the simultaneous 2w ary method and the simultaneous sliding window method; for w > 1, the former
is always less efficient.)

5

Multi-exponentiation with fixed bases

When many multi-exponentiations use the same bases g1 , . . ., gk , is is sufficient
to execute the precomputation stage just once, and we can try to make theevaluation stage more efficient by investing more work in precomputation. We
cannot easily reduce the number of general multiplications in the evaluation
stage, but we can reduce the number of squarings by using the Lim-Lee “comb”
method [12]: For an arbitrary positive integer m, m − 1 squarings suffice if forevery i we choose wi such that bi ≤ wi m and precomputeP
2j
Gi (S) := gi j∈S
11Table 1. Expected number of general multiplications for a multi-exponentiation (c1 : simultaneous 2w -ary method, c2 : simultaneous sliding window method, c3 : basic interleaving method, c4 : wNAF-based interleaving method)kb = 160b = 256b = 512b = 1024
b = 2048c1
85.0 (w = 2) 130.0 (w = 2) 214.0 (w = 3) 382.0 (w = 3) 700.0 (w = 4)c2
78.6 (w = 2) 119.7 (w = 2) 199.6 (w = 3) 353.2 (w = 3) 660.4 (w = 3)2
c3
78.0 (w1 = 4) 115.3 (w1 = 5) 200.7 (w1 = 5) 354.6 (w1 = 6) 638.0 (w1 = 7)c4
67.3 (w1 = 4) 99.3 (w1 = 4) 176.3 (w1 = 5) 318.0 (w1 = 6) 574.0 (w1 = 6)
c1 131.8 (w = 2) 179.0 (w = 2) 305.0 (w = 2) 557.0 (w = 2) 1061.0 (w = 2)c2 127.7 (w = 2) 172.5 (w = 2) 291.9 (w = 2) 530.9 (w = 2) 1008.7 (w = 2)3
c3 117.0 (w1 = 4) 173.0 (w1 = 5) 301.0 (w1 = 5) 531.9 (w1 = 6) 957.0 (w1 = 7)
c4 101.0 (w1 = 4) 149.0 (w1 = 4) 264.4 (w1 = 5) 477.0 (w1 = 6) 861.0 (w1 = 6)
c1 161.0 (w = 1) 251.0 (w = 1) 491.0 (w = 1) 746.0 (w = 2) 1256.0 (w = 2)c2 161.0 (w = 1) 251.0 (w = 1) 483.7 (w = 2) 731.5 (w = 2) 1227.0 (w = 2)4
c3 156.0 (w1 = 4) 230.7 (w1 = 5) 401.3 (w1 = 5) 709.1 (w1 = 6) 1276.0 (w1 = 7)
c4 134.7 (w1 = 4) 198.7 (w1 = 4) 352.6 (w1 = 5) 636.0 (w1 = 6) 1148.0 (w1 = 6)
c1 181.0 (w = 1) 274.0 (w = 1) 522.0 (w = 1) 1018.0 (w = 1) 2010.0 (w = 1)c2 181.0 (w = 1) 274.0 (w = 1) 522.0 (w = 1) 1018.0 (w = 1) 1994.7 (w = 2)5
c3 195.0 (w1 = 4) 288.3 (w1 = 5) 501.7 (w1 = 5) 886.4 (w1 = 6) 1595.0 (w1 = 7)
c4 168.3 (w1 = 4) 248.3 (w1 = 4) 440.7 (w1 = 5) 795.0 (w1 = 6) 1435.0 (w1 = 6)
c1 214.5 (w = 1) 309.0 (w = 1) 561.0 (w = 1) 1065.0 (w = 1) 2073.0 (w = 1)c2 214.5 (w = 1) 309.0 (w = 1) 561.0 (w = 1) 1065.0 (w = 1) 2073.0 (w = 1)6
c3 234.0 (w1 = 4) 346.0 (w1 = 5) 602.0 (w1 = 5) 1063.7 (w1 = 6) 1914.0 (w1 = 7)
c4 202.0 (w1 = 4) 298.0 (w1 = 4) 528.9 (w1 = 5) 954.0 (w1 = 6) 1722.0 (w1 = 6)
c1 278.8 (w = 1) 374.0 (w = 1) 628.0 (w = 1) 1136.0 (w = 1) 2152.0 (w = 1)c2 278.8 (w = 1) 374.0 (w = 1) 628.0 (w = 1) 1136.0 (w = 1) 2152.0 (w = 1)7
c3 273.0 (w1 = 4) 403.7 (w1 = 5) 702.3 (w1 = 5) 1241.0 (w1 = 6) 2233.0 (w1 = 7)
c4 235.7 (w1 = 4) 347.7 (w1 = 4) 617.0 (w1 = 5) 1113.0 (w1 = 6) 2009.0 (w1 = 6)
c1 406.4 (w = 1) 502.0 (w = 1) 757.0 (w = 1) 1267.0 (w = 1) 2287.0 (w = 1)c2 406.4 (w = 1) 502.0 (w = 1) 757.0 (w = 1) 1267.0 (w = 1) 2287.0 (w = 1)8
c3 312.0 (w1 = 4) 461.3 (w1 = 5) 802.7 (w1 = 5) 1418.3 (w1 = 6) 2552.0 (w1 = 7)
c4 269.3 (w1 = 4) 397.3 (w1 = 4) 705.1 (w1 = 5) 1272.0 (w1 = 6) 2296.0 (w1 = 6)
c1 661.7 (w = 1) 757.5 (w = 1) 1013.0 (w = 1) 1524.0 (w = 1) 2546.0 (w = 1)c2 661.7 (w = 1) 757.5 (w = 1) 1013.0 (w = 1) 1524.0 (w = 1) 2546.0 (w = 1)9c3 351.0 (w1 = 4) 519.0 (w1 = 5) 903.0 (w1 = 5) 1595.6 (w1 = 6) 2871.0 (w1 = 7)
c4 303.0 (w1 = 4) 447.0 (w1 = 4) 793.3 (w1 = 5) 1431.0 (w1 = 6) 2583.0 (w1 = 6)
c1 1172.8 (w = 1) 1268.8 (w = 1) 1524.5 (w = 1) 2036.0 (w = 1) 3059.0 (w = 1)c2 1172.8 (w = 1) 1268.8 (w = 1) 1524.5 (w = 1) 2036.0 (w = 1) 3059.0 (w = 1)10
c3 390.0 (w1 = 4) 576.7 (w1 = 5) 1003.3 (w1 = 5) 1772.9 (w1 = 6) 3190.0 (w1 = 7)
c4 336.7 (w1 = 4) 496.7 (w1 = 4) 881.4 (w1 = 5) 1590.0 (w1 = 6) 2870.0 (w1 = 6)

12

for all subsets S ⊆ {0, m, 2m, . . ., (wi − 1)m}. Note that then every exponent up
to bi bits of length can be written asXei =Ni [j] · 2j0≤j<mP
where each Ni [j] is an integer of the form j∈S 2j with S as above. Thus we
can use interleaving exponentiation with an evaluation stage algorithm similar
to section 3.2, but with a reduced number of iterations. The Ni [j] values for each
iteration need not be stored in advance, they can be extracted from the ei bytapping their bits in comb-shaped patterns; hence the nickname of this method.
A refinement of this (also from [12]) is based on the observation that theprecomputed table can be reduced in size in exchange for additional evaluation stage multiplications: Partition {0, m, 2m, . . ., (wi − 1)m}Sinto vi subsets
Ti,1 , . . ., Ti,vi ; now each of the above sets S can
Q be written as 1≤n≤vi Sn with
Sn = S ∩ Ti,n , and then we have Gi (S) = 1≤n≤vi Gi (Sn ). Thus it suffices
to precompute Gi (Sn ) for all non-zero subsets Sn ⊆ Ti,n for all n; from thisprecomputed data, Gi (S) can be computed in at most vi − 1 multiplications.
While Lim-Lee precomputation reduces the number of squarings, the expected number of general multiplications is larger than for the basic interleaving
exponentiation method with a similarly sized precomputed table. (In the basic
interleaving method, 2w1 −1 − 1 non-trivial precomputed values suffice to makesure that each evaluation stage multiplication covers wi exponent bits, and we
can skip many additional zero bits thanks to the sliding window. With Lim-Lee
precomputation, we need at least 2W − 2 non-trivial precomputed values to beable to cover W exponent bits with one evaluation stage multiplication, and
we lose the advantage of a sliding window.) Thus if k is large, using Lim-Lee
precomputation is a disadvantage.
Note that it is possible to use Lim-Lee precomputation for some of the bases
and standard precomputation (as in section 3) for others. This does not help for
multi-exponentiation in these mixed cases, but precomputed data can then bereused for pure Lim-Lee cases.

6

Conclusion

In many cases, the basic interleaving exponentiation method compares favourably
to the simultaneous 2w -ary method, in particular if k = 2 and squarings areabout as costly as general multiplications. In groups where inverting elements
is easy, the wNAF-based interleaving exponentiation method is available; its
efficiency is superior even to the sliding window variant of simultaneous exponentiation both in the precomputation stage and the evaluation stage if k = 2
or k = 3, and it is usually more efficient for larger k as well. In all cases, interleaving exponentiation provides the following advantages over simultaneous
exponentiation:– Improved efficiency if the bit-lengths of the exponents ei differ significantly.
13

– More flexibility in choice of the size of the auxiliary table (and, hence, thetime spent on precomputation), particularly if k is large.
– Better handling of situations where one or more of the gi are fixed whileothers are variable between multiple multi-exponentiation: A corresponding
part of the precomputation has to be done only once. (This is the case in
DSA, ECDSA, and RDSA signature verification if multiple signatures areverified that are based on the same underlying parameters.)
Thus, depending on circumstances, either the simultaneous sliding window
method or one of the interleaving exponentiation methods may be advantageous.
The special case k = 1 of the basic and wNAF-based interleaving exponentiation methods yields the usual sliding windows exponentiation method and
wNAF-based exponentiation method, respectively; so there is no need to implement these separatly if interleaving exponentiation is implemented for variable k.

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] Biehl, I., Buchmann, J., Hamdy, S., and Meyer, A. A signature scheme
based on the intractability of extracting roots. Designs, Codes and Cryptography.
To appear.
[3] Bos, J., and Coster, M. Addition chain heuristics. In Advances in Cryptology– CRYPTO ’89 (1989), G. Brassard, Ed., vol. 435 of Lecture Notes in Computer
Science, pp. 400–407.
[4] Brands, S. Rethinking Public Key Infrastructures and Digital Certificates –Building in Privacy. MIT Press, 2000.
[5] Brown, M., Hankerson, D., López, J., and Menezes, A. Software implementation of the NIST elliptic curves over prime fields. In Progress in Cryptology –CT-RSA 2001 (2001), D. Naccache, Ed., vol. 2020 of Lecture Notes in Computer
Science, pp. 250–265.
[6] Buchmann, J., and Hamdy, S.
A survey on IQ cryptography.
In
Proceedings of Public Key Cryptography and Computational Number Theory, 2000.
To appear. Preprint available at http://www.informatik.tudarmstadt.de/TI/Veroeffentlichung/TR/.
[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] Dimitrov, V. S., Jullien, G. A., and Miller, W. C. Complexity and fastalgorithms for multiexponentiation. IEEE Transactions on Computers 49 (2000),
141–147.
[9] ElGamal, T. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31 (1985), 469–472.
[10] Kocher, P. C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS,
and other systems. In Advances in Cryptology – CRYPTO ’96 (1996), N. Koblitz,
Ed., vol. 1109 of Lecture Notes in Computer Science, pp. 104–113.

14

[11] Kocher, P. C., Jaffe, J., and Jun, B. Differential power analysis. In Advancesin Cryptology – CRYPTO ’99 (1999), M. Wiener, Ed., vol. 1666 of Lecture Notes
in Computer Science, pp. 388–397.
[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] Menezes, A. J., van Oorschot, P. C., and Vanstone, S. A. Handbook ofApplied Cryptography. CRC Press, 1997.
[14] 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.
[15] National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS). FIPS PUB 186-2, 2000.
[16] Solinas, J. A. Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography 19 (2000), 195–249.
[17] Straus, E. Problems and solutions: Addition chains of vectors. American Mathematical Monthly 71 (1964), 806–808.
[18] Yen, S.-M., Laih, C.-S., and Lenstra, A. Multi-exponentiation. IEE Proceedings – Computers and Digital Techiques 141 (1994), 325–326.

15