a slight increase of weight for the sake of length reduction if saved squarings

[due to length reduction] outweigh the additional multiplications [due to weight

increase]. 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 a

2

“double digit” of weight 2. Details are out of the scope of the present paper; we

just 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 e¬-

ciency since it determines the number of squarings needed for interleaved multi-

exponentiation. For an exponent e, this length is around log2 e with any of the

representations 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 e¬ec-

tive idea (underlying [5] and made explicit in [8]) to get better performance if

all bases are ¬xed.

For exponentiations g e with exponent representations e = (b , . . . , b0 )2 of

maximum length + 1, we can decide to split each such representation into

some number s of shorter exponent representations. To wit, let + 1 = L1 +

· · · + Ls with positive integers Li ≈ +1 , and then let e1 = (bL1 ’1 , . . ., b0 )2 ,

s

e2 = (bL1 +L2 ’1 , . . ., bL1 )2 , and so on:

Faster Multi-exponentiation through Caching 45

e = (b , . . . , b0 )2 = (bL1 +···+Ls ’1 , . . ., bL1 +···+Ls’1 ,

es

bL1 +···+Ls’1 ’1 , . . ., bL1 +···+Ls’2 , . . ., bL1 ’1 , . . ., b0 )2

e1

es’1

· 2L1 +···+Li’1 it follows that

Then from e = 1¤i¤s ei

L1 +···+Ls’2 L1 +···+Ls’1

L1 e2 es’1 es

g e = g e1 · g 2 · · · · · g2 · g2 ,

È1¤I<i LI

2

and thus by de¬ning gi = g we have transformed the task of com-

e

e

puting g into the s-fold multi-exponentiation 1¤i¤s gi i . There is no need to

actually evaluate the ei as integers here since we already have appropriate rep-

resentations of them”namely, portions of the original representation as shown.

Thanks to exponent splitting, the maximum length of exponent representa-

tions can go down from + 1 to +1 if the Li are chosen accordingly. If g is

s

¬xed (and the parameters Li are constant), then so are the gi as de¬ned here.

b

Thus, the powers gi needed by the interleaved multi-exponentiation algorithm

in Section 2.1 can be precomputed in advance. So using additional memory for

precomputed data (possibly ROM) allows us to save time in each exponentiation.

So far, we have looked at radix-2 exponent splitting applied to exponentia-

tion, 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 ¬xed base in multi-exponentiation tasks, converting a k-fold multi-

exponentiation into some k -fold multi-exponentiation, k > k. However, since

È1¤I<i LI

the exponent splitting technique needs additional precomputed data (the powers

gi = g 2 of base g), it cannot be used to advantage for bases that are

not ¬xed. Thus, if there is any base that is not ¬xed (as in the case of DSA

and ECDSA signature veri¬cation), 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

Results

This section describes a novel technique for computing power products

ei

1¤i¤k gi assuming that g2 , . . ., gk are ¬xed base elements, while g1 is a vari-

able base element whose values may recur. The technique is based on interleaved

multi-exponentiation and on exponent splitting, but adds new features. It con-

sists of two di¬erent multi-exponentiation algorithms. The ¬rst algorithm, de-

scribed below in Section 3.1, is employed whenever a “new” g1 value appears.

This algorithm not only computes the multi-exponentiation result, but also out-

puts 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

46 B. M¨ller and A. Rupp

o

value appears, namely one for which a cache entry already exists. This algorithm

then exploits the cache entry created by the ¬rst algorithm to compute the new

multi-exponentiation result faster.

For both algorithms, we assume that parameters for radix-2 exponent splitting

have been ¬xed, 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 sets for exponent

representations have been ¬xed (see Section 2.1), and that there is a ¬xed 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 using the given

digit sets and exponent splitting parameters are precomputed in advance. These

are constant elements, so they may be stored in ROM. Due to our 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 lead to

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 preferred

depends very much on the statistical properties of the application scenario.

Multi-exponentiation for a New Base g1

3.1

e

If no cache entry based on g1 is available, 1¤i¤k gi i should be computed as

follows. As in Section 2.1, we assume that the exponents are given in represen-

tations ei = 0¤j¤ bi,j · 2j , bi,j ∈ Bi .

First, apply radix-2 exponent splitting (Section 2.2) to the representations

of exponents e2 through ek such that all of the resulting exponent represen-

tations observe maximum length L = max1¤i¤s Li (≈ +1 ). This transforms

s

the k-fold multi-exponentiation task into a multi-exponentiation task with more

bases, where the exponent to g1 appears unchanged but all other exponent rep-

resentations have been split into parts no longer than L digits. The list of bases

has expanded from (g1 , g2 , . . ., gk ) into

L1 +···+Ls’1 L1 +···+Ls’1

L1 L1

2 2 2 2

g1 , g2 , g2 , . . ., g2 , . . . , gk , gk , . . ., gk ;

we will assume that g1 keeps its index (i = 1). Now apply the interleaved multi-

exponentiation algorithm from Section 2.1 to this new 1 + (k ’ 1)s -fold power

Faster Multi-exponentiation through Caching 47

product. (Remember that appropriate precomputed powers of the bases except g1

are assumed to be available e.g. from ROM.) This will generate the desired result,

ei

1¤i¤k gi . 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,