S. Vaudenay, A. M. Youssef (Eds.): Selected Areas in Cryptography – SAC 2001,
Springer-Verlag LNCS 2259, pp. 165–180, ISBN 3-540-43066-0.

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 commutative groups. We look at the conventional simultaneous exponentiation approach and present an alternative strategy, interleaving exponentiation. Our comparison shows thatin general groups, sometimes the conventional method and sometimes
interleaving exponentiation is more efficient. In groups where inverting
elements is easy (e.g. elliptic curves), interleaving exponentiation withsigned 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 [11] or DSA [17] signatures;groups of rational points on elliptic curves over finite fields, e.g. for verification of
ECDSA [1] signatures; and class groups of imaginary-quadratic orders, e.g. forverification of RDSA [2][7] 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 foralgorithms; efficiency considerations may ignore this case. It is well known thatin general 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 [12] or power consumption measurements [13]or other extra data to gain knowledge on secret exponents.
To avoid constantQ eien·ord(g)+e
exponents,gcanberewritten
as
g
and
g
can
be rewritten asi
QQ( gi )n giei −n for arbitrary integers n.)
Like window-based algorithms for single exponentiations, the algorithms that
we analyse 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 ([11], [20], [21]); 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 [11],[20] and [21] 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 variants that can be advantageous when allbases gi are fixed.
In specific groups, additional useful efficiently computable endomorphisms
are available besides squaring and possibly inversion (see e.g. [19]); 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. For negative j, we define thate[j] = 0. We write e[j . . . j 0 ] for the integer consisting of the concatenation ofbits j down to j 0 of e; e.g., if e = 101112 = 23, then e[3 . . . 1] = 0112 = 3 ande[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: First, the precomputation stage prepares an auxiliary table2

of group elements; then, the evaluation stage computes the final result using thistable. 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 , . . ., gk , 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 needed by the simultaneous sliding window method if w > 1.
The evaluation stage requires both squarings and multiplications. For each
multi-exponentiation method, we look at the number of squarings and the expected number of general multiplications for given k, b, and w. w is assumed tobe small 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 in practice w will be muchsmaller than b, the error is negligible for our purposes.
Just as squarings can be eliminated in the evaluation stage while A is 1G , thefirst 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 affect asymptotics), so
comparisons between different methods remain just as valid.
3

2.1

Simultaneous 2w -Ary Method

The simultaneous 2w -ary exponentiation method [20] (see also [15]) looks at w
bits of each of the exponents for each evaluation stage group multiplication,i.e. kw bits in total. The special case where w = 1 is also known as “Shamir’s
trick” since it was described in [11] with a reference 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 Ajk
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 [21] 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 Ei is odd. (Note that while values gi2
no longer appear in the precomputed table, the precomputation stage now needs
them as intermediate values unless w = 1.) Also the expected number of multiplications required in the evaluation stage is reduced. Like the 2w -ary method,
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”.
For k = 1, this is the usual sliding window method for a single exponentiation(see e.g. [15]).
Q
Precomputation Stage. Precompute 1≤i≤k giEi for all k-tuples (E1 , . . ., Ek )∈ {0, . . ., 2w − 1}k where at least one of the Ei 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. Again we assume that initial squarings are eliminatedwhile A is 1G .
Note that for the algorithms described in this section, the precomputed tablehas disjoint parts for different bases gi . If multiple multi-exponentiations haveto be performed and some of the bases gi appear again, then the correspondingparts 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. [15]), 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 − wi 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.
Expected number of multiplications:
X

1≤i≤k

3.2

bi ·

wi +

1
P

1
n≥1 2n

=

X

1≤i≤k

bi ·

1
.
wi + 1

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 not in(Z/nZ)∗ .) This can be exploited for making exponentiation algorithms more efficient by recoding the exponents into a signed representation. We use a techniqueintroduced for single exponentiations independently in [18] and in [16] and apply
it to the task of 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.
6

A width-(wi + 1) NAFs always exists and is uniquely determined; it can becomputed by the following algorithm [19]: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 → ∞ [19].
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: 1≤i≤k bi · w 1+ 2 .
i7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,
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 minimise 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 thatspeed up multiplication with them in the evaluation stage (e.g. affine rather
than projective representations of points on elliptic curves [8]).
These effects, however, do not mean that we cannot compare algorithms
without looking at concrete cases: We can compare different aspects separately(table size, precomputation stage efficiency, evaluation stage efficiency) and look
if an algorithm 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 briefly discusses
the alternative multi-exponentiation method from [10] 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 the
Basic Interleaving Method

While the simultaneous sliding window method is more efficient than the simultaneous 2w -ary method, this section focuses on the latter. The reasons is that the
2w -ary method is often used in practice (e.g. [6]), possibly because it is perceived
to be simpler to implement. The basic interleaving exponentiation method is not
too complicated (in particular, indexes into the precomputed table are easy handle), 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
=
· kw
,
·
1
kw + 1 2 − 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 choiceof window sizes for the basic interleaving exponentiation method; using smalleror larger 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
window sizes 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 with this choice of window sizes willoften provide better performance than the simultaneous sliding window method
for k ≥ 4 as well: If additional memory allocation is not a problem, then theefficiency gain of the evaluation stage usually compensates for the growth of theprecomputed 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 [10]. This algorithm is related to the simultaneous sliding window exponentiation method of Yen, Laih, and Lenstra [21](section 2.2 in the present paper), but uses signed recoding of exponents in orderto reduce the size of the precomputed table. While the Yen-Laih-Lenstra method10with a window size of 1 requires an expected number of b · 0.75 general multiplications during the evaluation stage, the new method requires only about b · 0.534
multiplications according to [10] (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 [10] 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 [10] 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, precomputation and evaluation stage combined. (Window sizes are chosen such that thiscost measure is minimised.) Note that the 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 neededin the evaluation stage. The simultaneous 2w -ary method requires 2k(w−1) − 1
squarings for precomputation and again close to b evaluation stage squarings; so
ignoring the cost 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 , it is sufficient to execute the precomputation stage just once, and we can try to makethe evaluation 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 exponent splitting(cf. [5] and [9]) or the Lim-Lee “comb” method [14]. (Which approach is the11Table
1. Expected number of general multiplications for a multi-exponentiation
Qg ei with exponents up to b bits (c1 : simultaneous 2w -ary method, c2 : simultane1≤i≤k i
ous sliding window method, c3 : basic interleaving method, c4 : wNAF-based interleaving
method)kb = 160b = 256b = 512b = 1024
b = 2048c1
44.5 (w=4)
64.6 (w=5) 114.2 (w=5) 199.0 (w=6) 353.3 (w=7)
c2
39.0 (w=4)
57.7 (w=5) 100.3 (w=5) 177.3 (w=6) 319.0 (w=7)
1c3
39.0 (wi =4) 57.7 (wi =5) 100.3 (wi =5) 177.3 (wi =6) 319.0 (wi =7)c4
33.7 (wi =4) 49.7 (wi =4) 88.1 (wi =5) 159.0 (wi =6) 287.0 (wi =6)c1
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 (wi =4) 115.3 (wi =5) 200.7 (wi =5) 354.6 (wi =6) 638.0 (wi =7)c4
67.3 (wi =4) 99.3 (wi =4) 176.3 (wi =5) 318.0 (wi =6) 574.0 (wi =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)
3c3 117.0 (wi =4) 173.0 (wi =5) 301.0 (wi =5) 531.9 (wi =6) 957.0 (wi =7)
c4 101.0 (wi =4) 149.0 (wi =4) 264.4 (wi =5) 477.0 (wi =6) 861.0 (wi =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 (wi =4) 230.7 (wi =5) 401.3 (wi =5) 709.1 (wi =6) 1276.0 (wi =7)
c4 134.7 (wi =4) 198.7 (wi =4) 352.6 (wi =5) 636.0 (wi =6) 1148.0 (wi =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)
5c3 195.0 (wi =4) 288.3 (wi =5) 501.7 (wi =5) 886.4 (wi =6) 1595.0 (wi =7)
c4 168.3 (wi =4) 248.3 (wi =4) 440.7 (wi =5) 795.0 (wi =6) 1435.0 (wi =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)
6c3 234.0 (wi =4) 346.0 (wi =5) 602.0 (wi =5) 1063.7 (wi =6) 1914.0 (wi =7)
c4 202.0 (wi =4) 298.0 (wi =4) 528.9 (wi =5) 954.0 (wi =6) 1722.0 (wi =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 (wi =4) 403.7 (wi =5) 702.3 (wi =5) 1241.0 (wi =6) 2233.0 (wi =7)
c4 235.7 (wi =4) 347.7 (wi =4) 617.0 (wi =5) 1113.0 (wi =6) 2009.0 (wi =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)
8c3 312.0 (wi =4) 461.3 (wi =5) 802.7 (wi =5) 1418.3 (wi =6) 2552.0 (wi =7)
c4 269.3 (wi =4) 397.3 (wi =4) 705.1 (wi =5) 1272.0 (wi =6) 2296.0 (wi =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 (wi =4) 519.0 (wi =5) 903.0 (wi =5) 1595.6 (wi =6) 2871.0 (wi =7)c4 303.0 (wi =4) 447.0 (wi =4) 793.3 (wi =5) 1431.0 (wi =6) 2583.0 (wi =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 (wi =4) 576.7 (wi =5) 1003.3 (wi =5) 1772.9 (wi =6) 3190.0 (wi =7)
c4 336.7 (wi =4) 496.7 (wi =4) 881.4 (wi =5) 1590.0 (wi =6) 2870.0 (wi =6)12most efficient depends on details of the situation such as exponent lengths, thepermissible size of the precomputed table, the relative cost of squarings versus
general multiplications, and whether the wNAF-based interleaving exponentiation method is applicable.)
Let m be an arbitrary positive integer. Assuming that fixed Q
exponent length
bounds bi are known, we show how to evaluate power products 1≤i≤k giei in at
most m − 1 evaluation stage squarings, using a precomputed table independentof the specific exponents ei .
5.1

Exponent Splitting

Exponent splitting constructs a new power product representation by rewriting
each factor as follows:Yjmgiei =(gi2 )ei [jm+m−1 ... jm]
0≤j<dbi /mePThis leads to power products consisting of 1≤i≤k dbi /me factors. Any multiexponentiation method can be used for evaluating these power products.
It is evident that for the multi-exponentiation methods described in thispaper, exponent splitting does not help if k is already large and there are manylarge exponents. (In this case, instead of using precomputation table entries for
additional bases, window sizes should be increased; then the evaluation stage will
require more squarings, but fewer general multiplications than with exponent
splitting.)
5.2

Lim-Lee Precomputation

To apply the Lim-Lee “comb” method, for every i we choose wi such that bi ≤wi m and precomputeP
Gi (S) := gi

j∈S

2j

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 [14]) 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} into vi subsets
13

S
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, 2wi −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 each 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 thenprofitably be reused for pure Lim-Lee cases.
Without going into details, we remark that the Lim-Lee method can be considered an application of exponent splitting using specific multi-exponentiation
algorithms suited for small exponents. For example, if k = 1, the simple Lim-Lee
method uses “Shamir’s trick”, i.e. simultaneous exponentiation with a window
size of 1. Further algorithmic variations are possible.

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.
– 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.
14

It is easy to implement interleaving exponentiation for variable k. As thethe 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, this makes it unnecessary to
implement these separately.

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. Brickell, Gordon, McCurley, and Wilson. 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. 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.
7. 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.tu-darmstadt.de/TI/Veroeffentlichung/TR/.
8. 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.
9. 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.
10. Dimitrov, V. S., Jullien, G. A., and Miller, W. C. Complexity and fastalgorithms for multiexponentiation. IEEE Transactions on Computers 49 (2000),
141–147.
11. ElGamal, T. A public-key cryptosystem and a signature scheme based on discrete
logarithms. IEEE Transactions on Information Theory 31 (1985), 469–472.
12. 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.
13. 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.
14. 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.

1515. Menezes, A. J., van Oorschot, P. C., and Vanstone, S. A. Handbook ofApplied Cryptography. CRC Press, 1997.
16. 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.
17. National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS). FIPS PUB 186-2, 2000.
18. Solinas, J. A. An improved algorithm for arithmetic on a family of elliptic curves.
In Advances in Cryptology – CRYPTO ’97 (1997), B. S. Kaliski, Jr., Ed., vol. 1294
of Lecture Notes in Computer Science, pp. 357–371.
19. Solinas, J. A. Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography 19 (2000), 195–249.
20. Straus, E. G. Problems and solutions: Addition chains of vectors. American
Mathematical Monthly 71 (1964), 806–808.
21. Yen, S.-M., Laih, C.-S., and Lenstra, A. K. Multi-exponentiation. IEE Proceedings – Computers and Digital Techiques 141 (1994), 325–326.

16