Abstract—Compact exponentiation algorithms are required forresource constrained cryptographic devices. Historically, binary
windowing algorithms have been among the best, and only they
are possible in the most restricted cases. However, with minimallymore area, mixed base representations of the exponent give rise toalgorithms with competitive speeds. Implementations of them using thesame area are compared for both RSA and elliptic curve applications,and when processing the exponent digits in either direction. Walter’s
space-preserving duality (CT-RSA 2012, [34]) simplifies the comparison
to considering one direction plus secondary space and time issues
that distinguish the two directions. The duality led to a new, compact
left-to-right exponentiation method derived from the right-to-left division
chain method (Arith 13, [28]). Here, simulation results for this method
show it to be faster in constrained environments than the traditional
table-based algorithms for mixed base representations. Overall, theclassical binary algorithms are faster for RSA, but the new mixed basealgorithm is faster for the elliptic curves under the chosen memory
restrictions.

Keywords—Scalar multiplication, multi-base representation, mixedbase representation, exponentiation, dual addition chain, division chain.

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

2

Compact Exponentiation Schemes
Colin D. Walter, Senior Member, IEEEF

1

I NTRODUCTION

It is always useful to have machinery to generate newalgorithms and to have a wide selection of algorithms
from which to choose when there are so many different optimisations and conflicting pressures on the target computational platform. Cryptographic groups often
have some operations which are cheaper than the basic
group operation but, as well as space and time pressures,
embedded devices may have to achieve some measureof side channel resistance. Here the main implementation choices available for these are discussed in relation
to computing platforms with essentially minimal spaceresources. The simplest exponentiation method, binary
square-and-multiply, requires just two locations for storing elements of the group in which the exponentiationis performed. This investigation looks at the case of
having three locations. A new duality [34] between leftto-right and right-to-left exponentiation methods is used
to derive some novel ways of processing the recoded
exponents and hence speeding up and/or randomising
the computation.
There are few comparative treatments of exponentiation using different schemes. Joye [14] makes a comparison of left-to-right (L2R) and right-to-left (R2L) methods
but in general there is rarely more detail for an individual
algorithm than the total number of group operations,perhaps split into the number of squaring and nonsquaring operations, or a count of the underlying fieldsquarings and multiplications. However, in addition tosquaring being cheaper than a general group multiplication, many groups have other favoured cheap operations:inversion, the Frobenius endomorphism and composite
multiple-and-add operations on an elliptic curve areexamples. There is a general framework in which all ofthese operations can be used effectively with the greatest
efficiency, and which allows the use of all the usual
exponentiation algorithms, namely that of a mixed baserepresentation. These are derived from a division chain[28], for which recoding choices are made to satisfy thevarious efficiency and other requirements for the target
platform.
In most circumstances processing in one or otherdirection will have useful time, space or side channel
resistance advantages. Usually the standard left-to-righttable-based m-ary or sliding window exponentiation
Information Security Group, Royal Holloway, University of London (retired)

method is used. However, left to right processing ofrecodings with a fixed radix can be attacked throughside channel leakage because use of the table entries
may reveal the values of the corresponding digits in
the representation of the secret key [29]. This may bepossible even when the key is used only once and under
the assumption that input messages to the exponentiation are blinded and therefore unknown to the attacker.
Although a table based method may have side channel
disadvantages, the table values might be put into special
forms which make group operations significantly faster.
Among these possibilities, are the recently developed
double-and-add, triple-and-add and quintuple-and-add
composite elliptic curve operations [4], [6], [9], [12], [23],but other fast operations benefit the opposite right-to-leftdirection [27].
The original purpose here had just been to compare
the two directions in terms of speed and area over theirmost compact implementations. It was already known
that algorithms could be translated from one direction tothe other using the transposition method [2], [18] which
preserves “time”, i.e. there is the same count of squaringsand multiplications in either direction when the method
is applied carefully1 , but the method does not treat space.
However, during the research, it turned out to be possible to modify the method to treat space considerations as
well. The resulting new duality described in [34] shows
the two directions require essentially the same time andspace, with differences arising only at a secondary levelof detail. The main such differences are catalogued here,
as they have a modest effect on the most compact cases.
In particular, as well as certain operations being fasterin one direction than the other, L2R exponentiation may
suffer a greater space overhead for storing the recoded
exponent than R2L, whereas the R2L version has more
reading and writing to memory than L2R.
The new duality also gives rise to a new L2R algorithm derived from Walter’s R2L division chain recoding
technique [28]. This is investigated in more detail thanits brief mention in [34]. Classical, binary-oriented algorithms are generally better for residue rings, as in RSA,
but, where there is a cheap inverse – as in elliptic curve
cryptography – this compact mixed base L2R algorithm
is faster. The overhead is small since multi-base methods
1. Knuth’s example of 70 ([18], §4.6.3) does not even achieve thisproperty.

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

3

are straight-forward, with little extra development timeand almost no extra code. An added benefit is that arandomised recoding to a mixed base is an efficient
way of imparting some side channel resistance to the
exponentiation [30], [31]. Moreover, with its much greater
flexibility in a wider range of contexts than classicalmethods, the new algorithm has the potential of generating new record speeds for resource constrained devices.

2

N OTATION & M IXED BASES E XAMPLES

Here a fresh, i.e. unseen, exponent D of cryptographic
size is assumed for every exponentiation, or at leasta fresh, randomly different scheme is required for the
exponentiation in order to avoid side channel analysis.
If D were used repeatedly and side channel leakage were
not a problem, time could be spent searching for an
efficient addition chain, with the cost of this amortizedover all instances of its use. For the single instances here
it is not possible to do this and still retain the requirement
for time efficiency. For a multiplicative group G, wewish to compute g D for some fresh, random elementg ∈ G. Thus, it is not possible to pre-compute and store
any powers of g and spread the cost over a number of
exponentiations using different values of D. This would,
moreover, contradict the desire for space efficiency.
To construct the addition chain used to express an
exponentiation scheme for g D , it appears that one isforced to break D iteratively into two parts, the smallerof which contributes to the addition chain, and thelarger of which is fed into the next iteration. Addition
sub-chains corresponding to the smaller parts are thenconcatenated into an addition chain for D. Specifically,in all known schemes, this appears to require D to bebroken into either i) D mod r and bD/rc where r is
selected from a limited set of non-zero integers which
are close to 0, or ii) D−R and R where R is selectedfrom a limited set of integers with finitely expressible
relevant properties, at least one of which is close to D.
The former is the approach taken by Walter [28] with themixed base representation
D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0(1)

The latter is the approach pursued by Dimitrov [8] in his
multi-base representation
D=

n−1
X

di Ri .

(2)i=0

In these representations di ∈ D for some pre-defined
digit set D, ri ∈ R for some pre-defined radix set R of
non-zero positive integers, and Ri ∈ R∗ is a product ofelements from R. The case of R = {2}, D = {0, 1} yields
the normal binary representation used in the standard
square-and-multiply exponentiation schemes.
Knuth [18] and Gordon [11] provide coverage of themost important classical scalable exponentiation methods, and all relevant algorithms follow the mixed basepattern (1) above. As well as the usual binary squareand-multiply method (processing exponent bits in either direction), there are its generalisations to the leftto-right table-based m-ary method of Brauer [3] andits dual, namely the right-to-left m-ary method of Yao[36]. These arise by taking R = {m} and D any
set which contains at least a complete set of residues
modulo m, such as, typically, D = {0, 1, . . . , m−1} or
D = {d−(m−1)/2e, . . . , −1, 0, 1, . . . , d(m−1)/2e}. The
sliding window versions of both these algorithms [19]correspond to R = {2, m} where m = 2w is a 2power, and non-zero odd digits being removed from
D. There is also the non-adjacent form (NAF) recoding [16], [1] which yields two algorithms, one to process the digits in each of the two directions. It uses
an extended digit set to allow the redundancy whichenables any pair of consecutive digits to include 0.
The tableless R2L method of Walter [28] takes, interalia, R = {2, 3, 5, 17, 33, 49, 65, 97, 129, 257, 513, 1025, . . .},whereas that of Dimitrov [7] uses, inter alia, R ={2, 3, . . .} with di = 0 if ri 6= 2. Gebotys & Longa[21] deliberately select the mixed base representationsof [7] in order to make use of composite elliptic curve
operations which are cheaper than the sum of the costs of
their constituent group operations. Dimitrov et al. [9], [23]previously used such operations to provide speed-ups
for the multi-base representation (2). Such applications
are among those of greatest pertinence here.
There are specialised mixed base recodings for improving side-channel resistance. Some simply reduce datadependent variation by performing a multiplication at
every conditional step in the loop body of algorithms
such as those in Figs. 1 and 2. This may be a dummy
multiplication whose result is discarded when di = 0. It
becomes part of the exponentiation as a result of how thebase/digit pair (ri , di ) is translated into an addition subchain. Alternatively, a digit set D may be chosen which
does not contain 0. Other counter-measures include a
random input to vary the recoding unpredictably. This
may allow limited re-use of the same exponent. Most
random recodings use a fixed power of 2 as the base;some have a variable power of 2. They include thoseof Liardet & Smart [20], Oswald & Aigner [26] andItoh et al. [13], among many. Those using a radix set
containing more than powers of 2 are restricted to the
M IST algorithm [30] where the choice of bases is random,
typically with R = {2, 3} or R = {2, 3, 5}. In such cases,(1) is called a randomary representation.

3 R ECODING TO A M IXED BASE OR M ULTI BASE R EPRESENTATION
Exponentiation is a two stage process. In the first stage, a
recoding is used to convert the exponent into an addition
chain [18] which provides rules for constructing powersof the input in order to obtain the required output. In
the second, which may be executed in parallel withthe first, those addition chain rules are applied to theC. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

given group element to raise it to the required exponent.
With the space constraints here, the addition chain must
be annotated with register details which show how to
perform the computation in the space available.
Derivation of a mixed base form (1) is straight-forward
using the usual change-of-base algorithm with the (possibly variable) base ri to generate the digits di from least to
most significant. Suppose Di is the value of D remaining
after generating the digits d0 , d1 , ..., di−1 . The iterative
step starts by using a simple finite automaton to select abase ri ∈ R. It applies some suitable rule such as exact
divisibility of Di by ri . Next, digit di ∈ D is chosen fromthe residue class Di mod ri using some appropriate rule,such as that of least absolute value, that of least nonnegative value, making Di+1 a multiple of 2, or a random
selection. The step is then repeated on Di+1 = (Di −di )/ri
until eventually Dn = 0 for some n. The recoding time
is usually quadratic in log(D) as it involves a “short”√
division of the number Di −di with average size D
by the base ri which has length O(1)2 . In most of the
expected applications, a product in the group G will
also take quadratic time, so that the recoding will taketime equivalent to a very small constant number ofgroup operations whereas exponentiation in G will takeO(log(D)3 ) time. Recoding time can then be ignored
except for the smallest values of log(D) for which it is,in any case, insignificant.
The detail of the finite automaton driving the recoding(1) depends on device requirements, such as speed,
space or side channel resistance. For efficiency, a choicegiving di = 0 usually saves a multiplication in the
exponentiation, and taking ri as a power of 2 increases
the proportion of squarings, which are cheaper thanmultiplications. Choosing the appropriate value for ri
may allow a Frobenius map to be applied, i.e. raising
to a power equal to the characteristic of the underlying
finite field. The cost of inversion or division in G will
determine whether negative digits can be employed.
Cheap double-and-add, triple-and-add and quintupleand-add composite elliptic curve operations [4], [6], [9],[12], [23] could be employed when, for example, (ri , di )can be chosen to be (2, ±1), (3, ±1) or (5, ±1) respectively,
but this has slight detrimental repercussions on the code
area of the device. More precise recoding details for thisand how to optimise the choices are described in [33].
The multi-base approach (2) is difficult to put into
practice without imposing additional structure such asthat given in the mixed base representation (1) [7]. Digits
are generated from most to least significant, but the
choice of Ri is problematic. The main exception is when
every Ri is a power of the radix r in which D is presented
but, strictly speaking, that generates a single base rep2. The finite automaton chooses a digit in O(1) time, there are n =O(log D) digits and each division Di+1 = (Di −di )/ri normally takes
O(log D) time. However, if every ri divides a power of the radix usedin the initial presentation of D then this division just requires moving
a pointer to the representation of D, which takes O(1) time and makes
the recoding algorithm linear in log(D).

4resentation rather than a multi-base representation, andthis is of type (1). A left-to-right windowing algorithm
is the simplest non-trivial example of such a multi-baserecoding, whereas the right-to-left windowing algorithm
illustrates a mixed base recoding.

4

T HE E XPONENTIATIONThe second phase in an exponentiation is to apply an
addition chain corresponding to the recoding of D tog ∈ G in order to compute g D . This is performed in
one of several ways. First, an algorithm specification isrequired to show how results for individual base/digit
pairs (ri , di ) are combined to yield g D . The standard
left-to-right (L2R) and right-to-left (R2L) choices are illustrated in Figs. 1 and 2 respectively. These include
Brauer’s m-ary algorithm [3] and its dual by Yao [36] as
special cases. Secondly, a process must be described forconverting base/digit pairs into an addition chain which
is annotated with the memory locations used for each
operation. Specifically, for Figs. 1 and 2 this would meanprescribing how to raise group elements to the powers
ri and d.
It is now apparent that the recoding and exponentiation processes can often be run in parallel, as in sliding
windows [19]. Then the recoding generates the elementsof the addition chain just before use and in the sameorder as that in which they are consumed. However, therecoding process may have to generate the digits in the
opposite order from consumption, in which case the twoprocesses must run sequentially. In particular, this would
also require storing the recoding.
Large tables in Figs. 1 and 2 would be too expensive
for most embedded systems, and the speed-up they giveis negligible beyond two or three entries. If maximisingthroughput for a given area is the objective, it is normallybetter to implement several exponentiators with verysmall tables. Hence the greatest interest in exponentiation
methods falls naturally on the most compact cases. The
binary square-and-multiply algorithm (in either direction) is the only sensible choice when the minimum
number of locations, viz. 2, are available for storing
elements of G. The main interest here is therefore inalgorithms which use three such locations. So the target
device has:i) space for the recoded representation of the exponent D (if necessary);ii) two places T0 , T1 (say) for group elements, used
for temporary storage or table elements;iii) space P for the partially computed value of g D ;andiv) any additional temporary working space requiredfor performing a group operation.
The recoding space (i) is discussed in more detail in §6.9.
Only one of the three locations T0 , T1 , P might technicallybe a register and the other two somewhere in memory,with values possibly only read or stored one word at
a time. By performing a word-by-word swap between

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMESg ∈ G, D = ((dn−1 rn−2 +dn−2 )rn−3 + . . .
+d1 )r0 +d0 ∈ N, where di ∈ D, ri ∈ R.
Output: g D————————————————————————–
1
Initialise table: T [d] ← g d for all d ∈ D \ {0}.
2
P ← 1G3
for i ← n−1 downto 0 do {3b
if i 6= n−1 then P ← P ri
3a
if di 6= 0 then P ← P ×T [di ] }4
return P
Inputs:Figure 1. Left-to-Right (L2R) m-ary, Sliding Window orMixed Base Exponentiationg ∈ G, D = ((dn−1 rn−2 +dn−2 )rn−3 + . . .
+d1 )r0 +d0 ∈ N, where di ∈ D, ri ∈ R.
Output: g D————————————————————————–
1
Initialise table: T [d] ← 1G for all d ∈ D \ {0}.
2P ←g3
for i ← 0 to n−1 do {3a
if di 6= 0 then T [di ] ← T [di ]×P
3bif iQ
6= n−1 then P ← P ri }4
return d∈D\{0} T [d]dInputs:Figure 2. Right-to-Left (R2L) m-ary, Sliding Window orMixed Base Exponentiation
locations, we can survive with very little register space
and with only one location being accessible to write
results into during a group operation. This means thatthe read and write costs of different locations need to beaccounted for when assigning weights to each base/digit
choice in the recoding. It also means that copy and swap
operations are required in the set of operations available
for manipulating group elements.
The working space (iv) is necessarily rather ill-defined.
For some groups it may be possible to discard input
words once they have been used and use the released
space to store the output words as they are computed,
thereby saving space. It may also be possible to usepart of the output register as working space until it isneeded for the computed output. This level of detail isbeyond the scope of the investigation, although we flag
the differences between algorithms where this may be anissue that affects fair comparison.

5

B INARY A LGORITHMS

Suppose D were to contain only powers of 2. In this case,the step P ← P ri in Fig. 1 or 2 would not require space
to store an extra group element while another group
operation was being computed. Hence both T0 and T1
can be used to store digit-related “table” values.
Suppose m is the largest power of 2 in D and 2
itself is also in D. We might expect to need a complete
set of residues modulo m in any recoding. However,5

with a sliding window, digit di = 0 is chosen withbase ri = 2 whenever Di ≡ 0 mod 2 in the recoding
algorithm. Hence only odd non-zero digits are required.
This reduces the table size to at most m/2.
A further half of the table space may be saved
if division in the group G has essentially thesame cost as multiplication. Then the complete set{1−m/2, 3−m/2, . . . , m/1−3, m/2−1} of odd residues requires a supporting table with entries only for the positive odd residues 1, 3, . . . , m/2−1. Its size is just m/4.
The multiplication in step (3b) of Fig. 1 is then replacedby the division P ← P/T [−di ] when the digit di isnegative. Similarly the multiplication in step (3a) of Fig. 2
is replaced by T [−di ] ← T [−di ]/P when di is negative,
and the final product is, of course, only taken over thedigits represented in the table T .
This extra halving of the table size occurs for elliptic
curves since point additions and point subtractions have
similar costs, but not for RSA as modular division ismuch more expensive than modular multiplication. So
it is now apparent that the limit of 2 on the tablesize translates into a maximum base m = 8 for ECC
applications and m = 4 for RSA applications if m isa base for which all non-zero residue classes are to be
represented by digit values.
5.1 Time – Recoding Choices
With two table locations available, the usual binary
square-and-multiply algorithm does not make full useof the given resources, and is consequently slower thanwhat could be achieved: neglecting end issues, this binary method requires asymptotically one squaring andhalf a multiplication per exponent bit in either direction.
However, the table is large enough to use a base 4 sliding window with R = {2, 4} and digit set D = {0, 1, 3}.
Recoding is most easily done from the least significant
end, but can be done in the opposite direction [16], [1].
On average, half the base choices have base ri = 2 andso half the choices have base ri = 4. The digit is 0
for ri = 2 and non-zero for ri = 4. Thus one thirdof bits are consumed by loop iterations involving one
squaring and no multiplication, whereas the other two
thirds of bits are consumed by loop iterations involving
two squarings and one multiplication. So in addition tothe one squaring per bit there is on average only 13 rdof a multiplication per bit. This is faster than the binary
square-and-multiply.
When division is feasible, the recoding can use a 3bit window with R = {2, 8} and D = {−3, −1, 0, 1, 3}.
The table T again contains elements indexed by the digit
subset {1, 3}. With a similar argument to that above, basechoices 2 and 8 are equally likely, and so one quarterof bits are consumed by loop iterations involving one
squaring and no multiplication, whereas the other threequarters of bits are consumed by loop iterations involving three squarings and one multiplication or division. So
in addition to the one squaring per bit there is on average

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

only 18 th of a multiplication and 18 th of a division per bit– a total of 45 operations per bit. This is cheaper than thebase 4 sliding window with only non-negative digits if
the cost of one division is less than 53 rds the cost of amultiplication.
Finally, the w-NAF recoding has R = {2, 2w } andD = {d : |d| < 2w , d odd}, with base 2 always having digit 0, and adjacent digits not being both nonzero. The recoding chooses di = Di mod 2w or di =(Di mod 2w )−2w to make Di+1 even when Di is odd.
Pairing each non-zero digit with the following zero digit
gives a window of w+1 bits. Hence w-NAF is the same as
the base 2w+1 sliding window recoding described above
for which R = {2, 2w+1 } but taking D as for w-NAF.
Thus, it does not provide a distinct method to be added
to those already under consideration.
5.2 Time – Direction Issues
Still considering only radix choices which are powers of
2, with a bit of care, the same number of squarings and(non-squaring) multiplications should occur between
both the algorithms of Figures 1 and 2. Clearly, mostloop iterations corresponding to the same digit/base pair
will require the same number of squarings and multiplications. So, for the two algorithms, we will count how
many extra operations are required over and above those
expected for the loop iterations, assuming t tabulated
digits 1, 3, 5, . . . , 2t−1. Without loss of generality, assume
that dn−1 6= 0 since any optimisation should adjust n to
make this true.
In the L2R algorithm, initialisation should involve one
squaring to obtain g 2 (temporarily stored in P , say) andt−1 multiplications to obtain the powers 3, 5, . . . , 2t−1
of g. In the first loop iteration, one multiplication issaved by using an initialisation when P is first updated
from 1G . This totals one squaring and t−2 multiplications
more than what is naı̈vely expected from the loop.
In the finalisation step of the R2L algorithm, the return
value R is accumulated in the space used by T [2t−1]
to avoid using extra space, and an auxiliary product isconstructed in P :P ← T [2t−1]R←P ;for i ← t−1 downto 1 do{
P ← P ×T [2i−1]
if i = 1 then R ← R×R
R ← R×P}
At the end of iteration i > 1 this has created
T [2i−1]× . . . ×T [2t−1] in P and T [2i−1]1 ×T [2i+1]2 ×. . . ×T [2t−1]t+1−i in R. So it outputs the value R =T [1]1 ×T [3]3 ×T [5]5 × . . . ×T [2t−1]2t−1 , as required. The
code performs one squaring and 2t−2 multiplications.
However, there are t iterations of the main R2L loop
in which the table values are updated from 1 to a
non-trivial value. If these are replaced by initialisations

6

directly to the required values, then the number of extra
multiplications drops to t−2.
Thus both algorithms use the same number of multiplications and squarings. This becomes automatic when
the duality mechanism of [34] is applied (see §6.4)3 . Thatmechanism even changes the appropriate loop multiplications in one direction into initialisations in the other.
The equality in operation counts means that the mostsignificant time differences between the two processing
directions is in• the use of special forms for group elements andgroup operations;• reading and writing data to and from memory.
In the L2R version time could be spent putting thetable elements g d into a special form which makes themultiplications by T [d] more efficient. Similarly, in theR2L version there may be a special form that can be used
for P that is preserved under squaring and which speeds
up the squaring or the multiplication of T [d]. Both these
possibilities would normally reduce the overall time by asmall linear factor. Examples include the double-and-add
operation [10], [4].
For each operation, reading/writing is effectively linear in the size of the group elements whereas the operations themselves are typically quadratic in the element
size. Hence the overall difference in speed arising fromthis will be negligible once cryptographic lengths arereached. It is worth observing, though, that in the main
loop the L2R version writes only to P and only reads
from T whereas the R2L version reads from and writes
to both. This means potentially more data movement in
the R2L case.
5.3 Integrating Recoding with Exponentiation
The binary recoding algorithms of §5.1 are usually applied to D from least to most significant digit. Hence, for
the R2L direction, the recoding can be done in parallelwith the exponentiation and there is no need to store therecoding. This is also true for the L2R direction if D ispresented in binary. Avanzi [1] shows how to generatefrom left to right a sliding window recoding of similar
efficiency and resource characteristics to the above R2L
recodings. This is as follows.
Suppose division is expensive, so that no negative
digits are to be chosen. Then the digit set can again betaken to be D = {0, 1, 3, 5, . . . , m−3, m−1}, which consists of 0 and all the odd numbers less than m, but takeR = {2, 4, 8, . . . , m}. If D0 is the remaining unrecodedsuffix if D, then the recoding algorithm chooses baser = 2 and digit d = 0 when the leading bit of D0 is
0. Otherwise, let d0 (6= 0) be the value of the leadingw = log2 m bits of D0 and suppose 2s ||d0 where ‘||’denotes the highest power giving exact division. Then
take base r = 2−s m and digit d = 2−s d0 . So, as d is odd,
3. This explains why the total counts in Möller’s Tables 1 and 2 [24]are equal.

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMESd ∈ D. This is then repeated on the rest of D. As thenext s bits of D are 0, the next s choices would be ofbase 2 with digit 0. Once fewer than w bits remain, thesame procedure is applied with w equal to the numberof remaining bits.
On the other hand, if division is relatively cheapthen negative digits are employed and the digit set
can be taken as D = {0, ±1, ±3, . . . , ±(m/2−1)}. Again,
R = {2, 4, 8, . . . , m}. At any point in the L2R recoding,
suppose D0 is the unrecoded suffix of D and D0 the complementary recoded prefix. So D = D0 ||D0 . Suppose therecoded digits generated so far have value D0 +b0 whereb0 is the leading bit of D0 . (This is an integer addition,
not a concatenation of binary strings interpreted as aninteger.) A 0 bit is prepended to D if necessary so that
this holds initially when no digits have been generated.
Suppose D0 = b0 ||D00 and b00 is the leading bit of D00 . If
b0 = b00 then base r = 2 and digit d = 0 are chosen.
The generated digits then have value r(D0 +b0 )+d =D00 +b00 where D00 is the prefix complementary to suffix
D00 . So our required loop invariant is preserved in thiscase. Otherwise, suppose d00 is the value of the leadingw = log2 m bits of D0 , D00 is the remaining suffix of D0
with complement D00 , and D00 has leading bit b00 . Then
D0 = d00 ||D00 as strings and mD0 +d00 = D00 as values.
Define d0 = d00 −b0 m+b00 . Then 0 ≤ d0 ≤ m/2 if b0 = 0,
whereas −m/2 ≤ d0 ≤ 0 if b0 = 1. So d0 ∈ D when d0 is
odd or zero. In this case choose base r = m and digitd = d0 . Then the digits generated so far have the valuer(D0 +b0 )+d = D00 +b00 so that the required loop invariant
holds again. If d0 is even and 2s ||d0 then d0 is split up as
before into an odd digit d0 2−s with base m2−s followedby s digits 0 with base 2. After this the loop invariant
holds as before.
Thus the main binary recoding algorithms can, with
only minor differences, be performed digit by digit ineither direction.
5.4 Side Channel Leakage
Implementation weakness arises because when the tableelement is fetched, used, or written there is a danger that enough of its Hamming weight, address orother identifying information will leak through power
variation or electromagnetic waves for an adversary to
determine which exponent digits are equal, and thereby
recover the secret key D. For L2R, the table elements
and their Hamming weights are fixed throughout thecomputation, whereas for R2L, although there is more
movement of “table” data, only the addresses are fixed.
Countermeasures might blind this information leakage,
but R2L has a clear advantage without such blinding.
R2L can use random relocation of the data as a cheapand easy way of blinding the addresses, whereas data
blinding for L2R is much more expensive.
We ignore the leakage problems of executing different
code for zero digits. This is common to both directions
and can be avoided by minor, judicious recoding (such as7g ∈ G, D = ((dn−1 rn−2 +dn−2 )rn−3 + . . .
+d1 )r0 +d0 ∈ N, where di ∈ D, ri ∈ R.
Output: g D————————————————————————–
1 T ← 1G
2 P ←g3 for i ← 0 to n−1 do in parallel {3a
if di 6= 0 then T ← T ×P di
3b
P ← P ri }4 return T
Inputs:Figure 3. Compact Right-to-Left (R2L) Mixed Base Exponentiation [28]dummy multiplications) and perhaps the cost of anotherregister as well as more time if zero were excluded fromD [15]4 . Indeed, one rather weak solution is to include
T [0] initialised to the identity element 1G , and remove theconditional restriction in the main loop so that multiplications by/of T [0] are performed. However, if different
non-zero digits cannot be distinguished in a cost effective
way by the attacker, then knowing the positions of zero
digits is probably insufficient in many cases to reduce
the search space for a secret key to a computationallyfeasible size. Specifically, in our target platform there isa table of two elements, representing two or four digits.
The attacker has to distinguish correctly which one isused in each multiplication in order to discover the secretexponent. This is extremely difficult even with strong
leakage which distinguishes individual digits [32].

6M IXED BASE E XPONENTIATIONLet us now consider using a set R of bases which are
not all powers of 2. There has been recent research
to develop efficient composite double-and-add, tripleand-add, quintuple-and-add, etc. operations for elliptic
curve cryptography. These can be used in a left-toright evaluation when the exponent D has a mixedbase representation which includes the bases 2, 3 and 5
respectively, e.g. [9], [23], [21]. Usually the best strategy
is to select a radix r for which the digit is 0 since it saves
a multiplication, and otherwise take r = 2. So di = 0 if
ri 6= 2 and odd or zero digits di for ri = 2 such that|di | < 2t for the table size t = |T |. Within the restrictions
imposed by availability of digits, this re-coding was used
for the L2R and R2L results in Table 2 and it is close tothat of [21].
Figures 1 and 2 are presented in a form which shows
how to apply the recoding to perform exponentiation.
(We discuss these in more detail below.) However, there
is also a more compact tableless form given in Figure
3 in which there are only two quantities being stored
or updated: the usual cumulative product in T and a
4. Another register would be needed if a digit were to be added to
D to compensate for the loss of 0.

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

digit-independent
power gi = g Ri for the radix product
Qi−1
Ri =
j=0 rj in location P . The iterative step forms
gi+1 = giri in P , sharing as much as possible of thecalculation with that for gidi , and multiplies the latter
onto T when formed. To avoid extra multiplications it
is best if the only digits allowed are those that appear
naturally when raising to the power ri (§6.1). They
need to appear in an addition chain for ri , ideally of
minimal length. In §6.2 the dual compact L2R mixedbase algorithm is constructed. It has a table of just one
element, corresponding to T in the R2L form, and, in asimilar way to there, the underlying addition chains forri simulate having a much larger table. By using dual
addition chains, the exponentiation has the same costin terms of multiplications and squarings for the two
directions.
6.1 Digit Availability
For this section it is assumed that not all bases are
powers of 2. So extra memory has to be available forstoring intermediate powers of g ∈ G when raising to
non-2-power exponent r. The space for this is normallyequivalent to one table entry, say P 0 , and represents thefirst major hidden space difference between binary andproperly mixed base exponentiations. So let P and P 0
denote the two registers (or other memory) used forconstructing and storing the rth powers and, as before,
let T be an array, indexed by a subset of digits, forholding the digit-related table or accumulating products.
When T holds just one element then this satisfies thespace restrictions permitted in §4 for the target platform.
One is apparently therefore restricted to only the digit
values D = {0, 1} or D = {0, ±1}, the latter when
inversion is cheap. However, the table entry can be
multiplied in at any time during step (3b) of the threefigures so far rather than as a separate step (3a) before
or after. This turns out to be equivalent to having moredigits available.
Several minimal length addition chains are of particular interest: 1+1 = 2 for base 2, 1+1 = 2, 1+2 = 3 for base
3 and 1+1 = 2, 1+2 = 3, 2+3 = 5 or 1+1 = 2, 2+2 = 4,
1+4 = 5 for base 5. These show that any digit power P dcan be constructed en route to the radix power P r and at
no further extra expense when 0 ≤ d < r and r ∈ {2, 3, 5}.
Once P d is obtained in Fig. 3, it is multiplied onto T
without incurring any space penalty because it requires
no extra resources beyond what are already required forthe next multiplication in forming P r . For digit powers
created in this way, the number of group operations
required to evaluate corresponding loop iterations willbe the same for the exponentiation schemes of Figs. 1,
2 and 3. This number is just that required for step (3b),plus one when the digit is non-zero. Moreover, the cost
will still be the same even if we differentiate between
squaring and non-squaring operations.
However, for bases larger than 5 there may be digits
which are not in a shortest addition chain for the chosen

8base. In any of the exponentiation algorithms, digits
not included in the table or obtained when raising to
the power r can be assigned an extra cost, such as thenumber of extra group operations required to obtain therequisite power using a longer addition chain – perhaps∞ if there is insufficient space for its computation. For
example, in the L2R algorithm of Fig. 1, once the rth
power has been created in P , the working space P 0
becomes available for constructing any g d : the usual
binary algorithm can be used, holding the product in P 0
and multiplying in g from T when necessary. For the R2L
algorithms of Figs. 2 and 3 a similar process is possible.
Specifically, for h ∈ G initially in P , any hd can be createdin P 0 using the binary algorithm while retaining h in P .
This is then multiplied into T and subsequently hr iscreated in P . Thus, every digit is available, although notnecessarily at an acceptable price.
The need for such costly extra digits can often be
avoided without incurring any penalty simply by a better
recoding. For example, any digits d larger than the baser could be replaced by d−r and a carry of 1 generated to
the next digit up. In this way, the extra group operations
needed for creating these digit powers are used instead
to multiply their more naturally occurring constituent
components directly into T .
6.2 A Location-Specific Matrix Representation for
Addition Chains
As noted above, the addition chains for 2, 3 and 5
automatically yield the digit powers between 0 and theradix choice r. The required value is multiplied into T
when created in the compact R2L scheme of Fig. 3. Hence
there is no extra cost for allowing certain digits althoughtable entries for them may not exist. Similarly, in an L2R
scheme, if g 1 in T [1] is multiplied into P at the right time,
it gives rise to g d at the end of the loop iteration, andso is equivalent to having a pre-calculated table valueg d . For example, with base 5, digit 4 and h initially in
P , the multiplications to perform are: P ×T [1] → P 0 ,P 0 ×P 0 → P 0 , P 0 ×P 0 → P 0 , P ×P 0 → P . Although thiscreates the desired h5 g 4 in P , it is unclear what digit
powers could be obtained in this way. In fact, all that isneeded is to take the dual of an addition chain for (r, d).
There appears to be no concept of location-aware
dual addition chains prior to [34]5 . A register-specificdescription is required to determine that a dual processuses similar execution space as well as time. Suppose tregisters are available for computing powers of g ∈ G.
Then addition chain operations are defined more precisely by corresponding t×t matrices indexed by theregisters. These provide additional location informationby specifying where the group elements are read fromand written to. They act on a row or column vector
containing the exponents of the powers of g in those
5. There is a well-known transposition method which reverses edges
in the computational di-graph [18]. If done carefully, time can bepreserved, but it fails to address any space issues.

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

registers. Suppose Mn−1 , Mn−2 , . . ., M1 , M0 are matrices
representing the addition chain operations. (They may
represent more complex group operations than simple
multiplications.) For convenience, these are written in thesame order as the recoding of D so that M0 will normallydenote the start of the chain and be part of the sub-chain
for creating the least significant digit. Let the row vectorv, indexed by the registers, represent the values storedinitially in the registers. For the right-to-left (R2L) viewthe matrices are applied in right-to-left order on the left
to vector v T to evaluate Mn−1 . . .M1 M0 v T and yield thevalues in the registers at the end of the computation.
For the left-to-right (L2R) interpretation the matrices areapplied in left-to-right order to the right of v to evaluate
vMn−1 . . .M1 M0 .
For example, suppose g a and g b are initially in P and
P 0 respectively. Then, in the R2L view, the addition chain
operations corresponding to the multiplication P ×P 0 →P and the squaring P ×P → P are represented using
matrices and vectors indexed by (P, P 0 ) as, respectively,





a+b
1 1
a
=
b
0 1
b
and



2a
b




=

2
0

0
1



a
b



In Fig. 3 the contents of P and P 0 are entirely given
by applying a sequence of such matrices. At some point
during a loop iteration the required digit power hd of theinitial value h appears in P , say, with he , say, in P 0 (or viceversa). Then, at the end of the iteration, hr appears in P
and some other unwanted value h∗ in P 0 . Without loss ofgenerality, the matrices representing these addition subchains have the forms



 


d 0
r 0
i j
d 0
and
=
e 0
∗ 0
∗ ∗
e 0
respectively, where the matrix with row (i j) corresponds
to the part of the addition chain after d is generated. So
r = id+je. After applying the addition chain corresponding to the matrix with column (d e)T , the element inregister P is multiplied into T and the process continues
with the addition chain corresponding to the other matrix. We would need to move up to 3×3 matrices indexedby (P, P 0 , T ) to represent this action. For the L2R dual,
the components of the same matrix product are applied
from left to right on a row vector, say (a 0). So, once


i j
(a 0)
= (ai aj)
∗ ∗has been formed by applying the left hand factor to
the row, the element g 1 in T is multiplied into P toyield (ai+1 aj). For convenience, we skip the 3×3 matrix
view necessary to illustrate this. Then application of thesecond factor createsd 0(ai+1 aj)
= ((ai+1)d+aje 0) = (ar+d 0) .
e 0

9This is exactly how P needs to be updated by a loop
iteration in Fig. 1. In both directions this creates theillusion of having a table element for digit d.
6.3

The Dual Addition Chain

Ideally, the dual addition chain would be that specified
by applying the matrices for each addition step in left
to right order to a row vector instead of right to left
on the corresponding column vector (or vice versa). Unfortunately, not every matrix which behaves as a multiplication in one direction behaves as a multiplication in
the other direction. So some extra care is necessary.
For

0 2
example, in the R2L direction, matrix
acting
0 1
on a column vector represents the operation of squaring
the value in one register and writing the result into
the other register. However, this becomes a composite
square-and-multiply operation (or double-and-add) withan initialisation when applied in the opposite direction,i.e. to a row vector. So the permitted atomic addition
chain operations are restricted to exclude such cases; they
are replaced by compositions of simpler operations. If
the target device cannot perform every allowed atomic
operation – such as writing an output to the locationof an input – then the individual operations can be
combined into composite ones which the device can
execute.
Since the location of values is important, some extra
operations are required to move data around as wellas the usual ones for squaring and multiplication. Altogether,
Definition 1: (cf [34], Def. 2) Seven classes of atomic
operations are allowed in location-aware addition chains:• Copying one register to another;• Copying one register to another & then initialising
the source register;• Swapping the values of two registers;• Inverting the value in one register;• In-place squaring of the contents of one register;• Multiplying two different registers into one of the
input registers;• Multiplying two different registers into one of the
input registers, & then initialising the other input.
These operations do not change the values of any registers other than those mentioned. 
Any addition chain can be written using only theabove operations whatever registers are prescribed forreading and writing. For example, if an operation, suchas multiplication or squaring, needs to write to a register
P 00 which is not an input to the operation, then one of
its inputs is simply copied into P 00 first and then theoperation performed using that copy. If multiplications
or squarings can only be performed on and to certain locations, then swaps of arguments and results can be used
to provide operations of greater generality. However, forconvenience, in the following it is assumed that there

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

are no restrictions beyond those specified above. Including an inversion operation enables addition-subtraction
chains to be represented and dualised as well. No initialisation only operation is required because it is incorporated when necessary into other operations. If desired,
the squaring and inversion classes might be extended
to include other unary powering operations such as a
Frobenius map.
For a device with two locations, R2L examples of eachclass are, respectively,

 
 
 

1 0
0 0
0 1
−1 0
,
,
,
,
1 0
1 0
1 0
0 1

 



2 0
1 1
1 1
,
, and
.
0 1
0 1
0 0
This set is closed under transposition, and so the L2R
interpretations of them are also atomic operations. If
we define a location-aware addition chain as being asequence of such matrices then the transpose provides awell-defined dual chain. Alternatively, a dual is obtainedby applying the matrices in the opposite order to acolumn vector instead of a row vector of locations, orvice versa. Of course, independently of the matrix representations, the operators have transposes which enable
the dual to be defined. Removing the location details
and the copying operations leaves a classical addition
chain consisting of only squaring and multiplication
operations. So a dual for the classical addition chain is
obtained.
6.4 Counting Multiplications in the Dual Chain
Ideally we would like to have the same number ofmultiplications and squarings in an addition chain andits dual. This requires some restrictions on the allowablelocation-aware chains to make them normalised. The form
is achieved by repeatedly applying the following to achain of atomic operations until none applies (cf [34]Defn. 6):i) any operation with 1G as an input should be
replaced by a simpler one which does not requirethat argument;ii) any operation with an argument which is not usedsubsequently should be replaced by an equivalent
one that re-initialises that argument; andiii) any operation whose result is unused must be
deleted.
Note that none of these modifications changes the number or type of the multiplicative operations, nor theoverall output. One more condition is imposed, namely,iv) the number of inputs to the chain is the same as
the number of outputs from the chain.
So, if the same registers are used for output as for input,
there is a complementary set of non-I/O locations usedsolely for intermediate calculations.
Theorem 1: [34] Using the above construction forlocation-aware addition or addition-subtraction chains,10

the number of squarings and the number of multiplications is the same for a normalised chain and its dual.
This is easily proved by counting the number of operations which initialise a location to 1G and equating itto the number of operations which overwrite a location
containing 1G .
Removing the location details yields a corollary for theclassical addition chain:
Theorem 2: A normalised addition chain and its dual
have the same length. 
When the normalised chain computes only the value
g D , the matrix representing its action has a single nonzero value, namely D. So the dual also computes g D(providing the reading and writing locations are interchanged). However, if the chain computes several values– a multi-exponentiation – then its dual may computedifferent values. Clearly, if inputs and outputs are to be
via the same locations for a chain and its dual, then thetwo chains compute the same values if, and only if, thematrix representing the action of one is symmetric, i.e.
equal to its transpose.
6.5 Some Duality Examples
Suppose a device has locations R0, R1 and R2 with
R1 used for I/O. Let ←I denote assignments which
include initialisation of any input location which is not
the location being assigned to. Then the following is alocation-aware chain which outputs g 3 in R1 if g ∈ G is
initially in R1. It follows the construction rules provided
in the previous section.
R2 ← R1; R2 ← R1+R2; R0 ←I R1;R1 ←I R2; R1 ←I R0+R1;
This includes two multiplications and no squarings.
The R2L matrix equivalent acting on the column vector(R0, R1, R2)T is
!
!
!
!
0 0 0
1 0 0
0 1 0
1 0 0
1 1 0
0 0 1
0 0 0
0 1 0
0 0 1
0 0 0
0 0 1
0 1 1
!
!
1 0 0
0 0 0
0 3 0
× 0 1 0
=
.
0 1 0
0 0 0
Applying this L2R on a row vector (R0, R1, R2) gives thedual location-aware chain
R0 ← R1; R2 ←I R1; R1 ←I R0;
R1 ← R1+R2; R1 ←I R1+R2;
which also has two multiplications and no squarings.
As a second example, the classical addition chain
1+1=2, 2+2=4, 4+1=5 shows roughly how to implement
the base/digit pair (5, 4) in the R2L algorithm of Fig. 3.
Adding the location information for registers T, P, P 0

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMESgives
P 0 ← P ; P ← 2P ; P ← 2P ; T ← T +P ; P ←I P +P 0 ;This has two I/O registers, namely T and P . It acts on(g, h, ∗) to produce (gh4 , h5 , 1G ) using two squaringsand one multiplication. The dual of the chain is
P 0 ← P ; P ← T +P ; P ← 2P ; P ← 2P ; P ←I P +P 0 ;which acts on (g, h, ∗) to produce (g, h5 g 4 , 1G ), also using
two squarings and one multiplication. This is the updating required for a left-to-right algorithm.
6.6 The Montgomery Powering Ladder
Constructing a dual for the Montgomery Powering
Ladder [25], [17], [35] illustrates some of the subtleties ofnormalisation which, if ignored, may lead to a different
number of some types of operation in the dual.
A slightly modified version of the original algorithm
is given in Fig. 4. Taking the transpose yields the remarkedly similar algorithm of Fig. 5 which computes thesame value. The correctness proof for the L2R version
simply involves
checking that T [0] = g Di , T [1] = g Di +1
Pn−1
where Di = j=i dj 2j at the end of the loop iteration
using di . That for the R2L version involves checking that
Pi−1
i
0
0
T [0] = g 2 −Di , T [1] = g Di where Di 0 = j=0 dj 2j at theend of the loop iteration using di−1 .
The usual requirement for dn−1 = 1 has been dropped
and the initialisation simplified in Fig. 4 to give a more
uniform presentation. Those conditions would need tobe restored to ensure that each loop iteration consistedof a non-trivial multiplication followed by a non-trivial
squaring. However, the main problem for normalising
the usual version of the Ladder is the redundant operation on T [1] in the last loop iteration – the final value ofT [1] remains unused.
Observe that if D ≡ 0 mod 2a then the last a+1
loop iterations have non-trivial, unused multiplications
in step (2a) of Fig. 4, whereas the corresponding firsta+1 loop iterations in Fig. 5 have trivial multiplications
by 1G in step (2a). The cost of the two algorithms
is therefore different unless there are extra conditions.
Here, requiring d0 6= 0 and, dually, dn−1 6= 0 for bothalgorithms limits the trivial and superfluous operations
at each end of the algorithms so that the numbers ofsquarings and multiplications could be equated. Under
these extra conditions the initialisation and finalisation
could be easily modified to include the first and last loop
iterations and yield normalised, regular algorithms.
An interesting difference between the algorithms isthat the loop operations in the L2R version can becomputed in parallel whilst those in the dual can not.
On the other hand the dual version can use a more
efficient double-and-add operation on an elliptic curve.
The left-to-right version can also compute g D on an
elliptic curve using only the x- and z- projective coordinates using the known coordinates of T [0], T [1] andT [1]/T [0] = g to recover the y-coordinate. Unfortunately,

11

Pn−1
g ∈ G, D = i=0 di 2i
where di ∈ {0, 1} for 0 ≤ i < n − 1.
Output: g D————————————————————————–
1a T [0] ← 1G
1b T [1] ← g
2 for i ← n−1 downto 0 do {2aT [1−di ] ← T [0]×T [1]2bT [di ]← T [di ]2}
3 return T [0]Inputs:Figure 4. Left-to-Right (L2R) Montgomery Powering
Ladder [17]Pn−1g ∈ G, D = i=0 di 2i
where di ∈ {0, 1} for 0 ≤ i < n − 1.
Output: g D————————————————————————–
1a T [0] ← g
1b T [1] ← 1G
2 for i ← 0 to n−1 do {2b
T [di ] ← T [di ]22aT [di ] ← T [0]×T [1] }3 return T [1]Inputs:Figure 5. Quasi-Dual Right-to-Left (R2L) Montgomery
Powering Ladder
this is not possible in the dual version as the coordinates
n−1
of T [1]/T [0] = g 2
are unknown. This example ofduality only uses two locations, however, and so falls
outside the main scope of this study.
6.7

The New Compact L2R Mixed Base Algorithm

For any given base r it is relatively straight-forward togenerate addition chains for r and see which digit values
d are produced by each chain. When register informationis added, these enable the R2L division chain algorithmof Fig. 3 to be executed. The construction of the dual
location-aware addition chain enables the algorithm toprocess the digits in the opposite L2R order with thesame space resources and the same numbers of squaringsand multiplications. Moreover, all the digits available for
the R2L direction are also available for the L2R direction.
The resulting new compact L2R algorithm achieves thesame results at the end of each loop iteration as thealgorithm of Fig. 1, but requires a table T containing only
the initial g ∈ G, not every digit power. The algorithm,
first given in [34], is outlined in Fig. 6 and the loop
iteration detail is provided by using a dual chain for thebase/digit pair, as illustrated in §6.5.
For completeness, Table 1 provides the L2R registerlevel instructions suitable for the most common
base/digit pairs (r, d), d ≤ 5. The notation for theoperation sequences on the three registers T , P , P 0 is

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMESg ∈ G, D = ((dn−1 rn−2 +dn−2 )rn−3 + . . .
+d1 )r0 +d0 ∈ N, where di ∈ D, ri ∈ R.
Output: g D————————————————————————–
1 T ←g2 P ← 1G
3 for i ← n−1 downto 0 do
3a
P ← P ri ×T di
4 return P
Inputs:Figure 6. Compact Left-to-Right (L2R) Mixed Base Exponentiation [34]self-explanatory. All initialisations have been removed
because none has practical value except when taking thedual. The last column indicates one way of assigning theoperation types, including double-and-add (DA), tripleand-add (TA) and quintuple-and-add (QA) composite
operations. (Following the elliptic curve context in whichefficient implementations of these may be available, additive notation has been used to describe them rather
than multiplicative notation.) Since there may be time to
put the table element in a special form (such as affinerather than projective coordinates), multiplication by thetable element may be faster than multiplication by arandom element. This is denoted by A rather than A.
If the digit range includes negative digits and division
costs the same as multiplication, then more of the loop
iterations could make use of this special form with thecheaper operation A.
Operation Sequence

Operations

(2,0)
(2,1)

2P → P ;2P → P ;T+P → P ;

D
DA

(3,0)

P → P0 ;2P0 → P0 ;

(3,1)

0

(r, d)

P+P0 → P ;

T

P→P;

2P

0

→P;

P+P0 → P ;P+T → P ;

TA

(3,2)

P → P0 ;T+P0 → P0 ;2P0 → P0 ;P+P0 → P ;

A, DA

(5,0)

P → P0 ;2P0 → P0 ;2P0 → P0 ;P+P0 → P ;

Q

(5,1)

P → P0 ;2P0 → P0 ;P+P0 → P ;2P0 → P0 ;P+T → P ;

QA

(5,2)

P → P0 ;2P0 → P0 ;2P0 → P0 ;T+P0 → P0 ;P+P0 → P ;DA, DA(5,3)

P → P0 ;T+P0 → P0 ;P+P0 → P0 ;P+P0 → P ;P+P0 → P ;A, A, A, A

(5,4)

P → P0 ;T+P0 → P0 ;2P0 → P0 ;2P0 → P0 ;P+P0 → P ;A, D, DA0TABLE 1
Register Instructions for Loop Iteration in the L2R
Compact Mixed Base Exponentiation

It is, of course, always possible to include a larger table
T in the compact L2R algorithm. For example, includingg 3 in the table would allow a cheaper implementationof base 4 with digit 3. However, the space limitation to12

three registers makes this impossible on the target device.
Space permitting, the dual R2L algorithm to this would
also have a larger T used in a way similar to that inFig. 2.
6.8 Recoding Time
Some mixed base recoding algorithms are presented
in [7], [28], [30] and above. Generally, the algorithm
decides the ith base/digit pair (ri , di ) using the valueof Di mod π where π is divisible by every element in B.
This value may enable several digits, say j, to be decided
at one go if π is increased sufficiently, ideally to justless than the maximum value of a machine word. Then
determining Di mod π, base/digit pairs i to i+j−1, andDi+j uses the school book short division algorithm andwill typically require between 2ni and 4ni word×word
divisions or multiplications where Di is ni words long,plus a similar number of additive operations. It will also
make Di+j around half a word or so shorter than Di , say,the actual amount depending on how fussy the recoding
algorithm is, i.e. how large π must be to decide one
digit, and therefore how many digits can be decided withthe chosen π. On average ni is half the word length ofD, and so the total number of word operations for therecoding should be no more than that for around halfa dozen multiplications of integers the size of D – very
comparable with the cost of a single elliptic curve point
addition. This cost is the main time penalty for using amixed base representation rather than a purely base 2
sliding window which requires at most a partitioning of
the exponent bits. However, if D is already represented
in base π, then much of this cost can be saved.
This method for the recoding clearly has a word operation complexity of O(n2 ) where n = O(log D) is the key
length, i.e. the number of digits in D. A multiplicationin G is also typically O(n2 ), so that the exponentiation has a word complexity of O(n3 ). Consequently, for
cryptographic key lengths the recoding cost should be a
relatively insignificant part of the whole computation.
6.9 Recoding & Other Space Issues
Given a binary representation of D, the mixed baserepresentation can only be generated from left to right,
forcing the storage of the recoding if an L2R exponentiation method is used. The space required depends
on the recodingQfunction, but is generally under aboutn−1
3 log2 D. Since i=0 ri ≈ D, the binary representations
for the sequence r0 , r1 , . . . will take about log2 D bits,
and, if there are at most r digit choices for base r
then the sequence d0 , d1 , . . . takes another log2 D bits,
approximately. Another log2 D bits or so may be used
to mark the start of each base/digit pair.
In practice some simple compression may reduce thisconsiderably. For R = {2, 3} and digits in the range 0
to r−1, a single bit could be used for the base, one bit
for a base 2 digit, and two bits for a base 3 digit. If

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

every base choice were 2, then the space taken would be
2dlog2 De bits. If every base choice were 3, then the spacetaken would be 3dlog3 De ≈ 3 log3 2 log2 D < 2 log2 D.
Whatever the ratio of choosing base 2 against base 3, thetotal will be between these limits, and therefore boundedby 2dlog2 De bits.
Another typical choice might be R = {2, 3, 5} with thedigit set {0, ±1} for base 2 and only digit 0 for bases
3 and 5. One bit would indicate whether base 2 waschosen. In the case of base 2, two further bits would
indicate the digit choice. Otherwise, one extra bit would
be used to indicate the choice of base 3 or 5. Then
there would be an upper bound of 3dlog2 De bits for therecoding space. This could be reduced if every non-zerodigit had to be followed by a digit 0.
When the recoding is generated on-the-fly for R2L
methods, the only extra storage requirement is that for
the value of Di , which is the same as that for D. So L2R
requires more space than R2L if elements of R are not all
powers of a single number. However, in many protocols
the exponent is random, and might be generated on-thefly in mixed base form. In this case the space requiredby a recoding of D can be ignored, making L2R and R2L
space requirements identical.
Finally on space issues, unlike the binary case with
D given in binary, D is destroyed by the mixed baserecoding. Hence, for both directions, extra space may berequired in the mixed base case to store the initial valueof D. Also, unlike the L2R cases, the input “message”g∈G is destroyed by all the R2L methods, and so further
space may be required to preserve it.
6.10

Composite Elliptic Curve Operations

The duality between L2R and R2L suggests speeds
should be almost identical. However, particularly withreference to the group of points on an elliptic curve, thepre-computed L2R table entries might be manipulated
into special forms (such as affine rather than projective
coordinates [5]) which may make all the multiplications6by the digit powers in T cheaper in the L2R direction
than the R2L direction [9], [23], [21]. Here “cheaper” maymean less space (e.g. two coordinates instead of three)
and/or faster (e.g. from specialised mixed coordinate
operations). Indeed, one might save up to 5 of 16 field
operations in the point additions (Jacobian coords) [22].
On the other hand, for R2L every operation bar thatinvolving T is a powering of P and there are fastermethods also for those cases [12], [27], [14]. In general
one can expect some composite operations in the group
G to be cheaper than the sum of the costs of their constituent operations. How well these can be applied seems
to determine whether R2L or L2R will be faster sinceduality shows that the same number of multiplications
6. The reader is reminded that the group G is being represented
multiplicatively. So, on an elliptic curve, ‘’multiplication” here (and in
Table 2) means what is more usually described as ‘’point addition” and‘’squaring” means ‘’point doubling”.

13and squarings occur in either direction. A more efficient
Frobenius operation (raising to a power equal to theunderlying field characteristic) applies equally well ineither direction, and is something that may be taken
advantage of in a recoding which favours such powers
for either digit or radix.

7

S IMULATION R ESULTS

Sections 5 and 6 describe the best binary and mixedbase exponentiation algorithms when only three memory
locations are available for storing powers of the input
element g. This section compares the approaches. Since
the mixed base recoding for an L2R algorithm typicallyoccupies space equal to another element of G, the comparison also includes binary algorithms with an extra
location, i.e. four in total, so that the L2R versions canbe compared more fairly.
Mixed base recoding is a Markov process with a transition matrix determined by the residue of Di modulo
the lowest common multiple of the base choices. For
any recoding algorithm it is therefore straightforward
to determine the asymptotic relative frequencies of thevarious base/digit pairs, and hence the average numbersof squarings, multiplications or any composite operation
per exponent bit. The results are given in Table 2 forbase set B = {2, 3} and the recoding given in thefirst paragraph of §6. A better recoding is possible, but
improves the speed only marginally. The #Multns column
combines the numbers of squarings and multiplications
for several likely ratios Sq/M u of their relative costs. The
cost of table and other initialisation (such as recoding) isomitted.
The results are divided into two sets according towhether or not inversion is essentially free in the group.
This allows application of the conclusions to both the
RSA and elliptic curve cases. The speed of the left-toright compact mixed base algorithm (Compact) is compared to the normal table-based mixed base version fora table of size 1 (MB Table), as it occupies the same
space. The sliding window algorithm of equivalent space
has a table of between two and three elements (SWin2
and SWin3 resp.), depending on whether or not space isneeded for the mixed base recoding of D.
The table shows that sliding windows gives the best
speed for slightly less space when there is no cheap
inversion. However, the compact mixed base algorithm
is fastest when inversion is free. Being new7 , it should
enable new records to be set for elliptic curve point
multiplication on the smallest devices by using combined
double-and-add or triple-and-add formulae as describedby Longa and Gebotys [21] who only used the traditional
table-based version for their record.
7. At the time of writing, the more detailed account in [34] had notappeared.

C. D. WALTER (2011)

COMPACT EXPONENTIATION SCHEMES

log2 D = 160, with inversion
Sq/Mu
Method#Mults14log2 D = 1024, without inversion
Sq/Mu
Method#Mults

1.0
1.0
1.0
1.0

MB Table
Compact
SWin2
SWin3

203.9
190.5
200.0
195.6

1.0
1.0
1.0
1.0

MB Table
Compact
SWin2
SWin3

1415.21388.71365.31316.6

0.8
0.8
0.8
0.8

MB Table
Compact
SWin2
SWin3

173.4
159.6
168.0
163.6

0.8
0.8
0.8
0.8

MB Table
Compact
SWin2
SWin3

1220.61196.01160.51111.8

0.5
0.5
0.5
0.5

MB Table
Compact
SWin2
SWin3

126.7
113.2
120.0
115.6

0.5
0.5
0.5
0.5

MB Table
Compact
SWin2
SWin3

936.7
907.2
853.3
804.6

TABLE 2Comparative Speeds for Sliding Window and Mixed BaseExponentiation

8

R EFERENCES

[2]
[3]

M. Ciet, M. Joye, K. Lauter & P. L. Montgomery, Trading Inversions
for Multiplications in Elliptic Curve Cryptography, Designs, Codes
and Cryptography 39(2), 2006, pp. 189–206.

[5]

H. Cohen, A. Miyaji & T. Ono, Efficient Elliptic Curve Exponentiation using Mixed Coordinates, Asiacrypt 1998, LNCS 1514,
Springer-Verlag 1998, pp. 51–65.

[6]

R. Dahab & J. Lopez, An Improvement of the Guajardo-Paar Method
for Multiplication on non-Supersingular Elliptic Curves, Proc. SCCC
1998, IEEE Computer Society 1998, pp. 91–95.

[7]

V. S. Dimitrov & T. V. Cooklev, Two Algorithms for Modular
Exponentiation using Nonstandard Arithmetics, IEICE Transactions
on Fundamentals of Electronics, Communications and Computer
Science, E78-A, no. 1, 1995, pp. 82–87.

[8]

V. S. Dimitrov, G. A. Jullien & W. C. Miller, Theory and Applications
for a Double-Base Number System, Proc. ARITH 13, IEEE Computer
Society, 1997, pp. 44–51.

[9]

V. Dimitrov, L. Imbert & P. K. Mishra, Efficient and Secure Elliptic
Curve Point Multiplication using Double Base Chain, Asiacrypt 2005,
LNCS 3788, Springer-Verlag 2005, pp. 59–79.

[10]K. Eisenträger, K. Lauter & P. L. Montgomery, Fast Elliptic Curve
Arithmetic and Improved Weil Pairing Evaluation, CT-RSA 2003,
LNCS 2612, Sringer-Verlag 2003, pp. 343–354.

[11]

D. M. Gordon, A Survey of Fast Exponentiation Algorithms, Journalof Algorithms, 27, 1998, pp. 129–146.

[12]

J. Guajardo & C. Paar, Efficient Algorithms for Elliptic Curve
Cryptosystems, CRYPTO ’97, LNCS 1294, Springer-Verlag, 1997,
pp. 342–356.

[13]

K. Itoh, J. Yajima, M. Takenaka & N. Torii, DPA Countermeasures by
Improving the Window Method, CHES 2002, LNCS 2523, SpringerVerlag 2002, pp. 303–317.

[14]

M. Joye, Fast Point Multiplication on Elliptic Curves Without Precomputation, WAIFI 2008, LNCS 5130, Springer-Verlag, 2008, pp. 36–
46.

[15]

M. Joye, Highly Regular m-ary Powering Ladders Selected Areas
in Cryptography (SAC 2009), LNCS 5867, Springer-Verlag, 2009,
pp. 350–363.

[16]

M. Joye & S.-M. Yen, Optimal Left-to-Right Binary Signed Digit
Recoding, IEEE Trans. Comp. 49(7), 2000, pp. 740–748.

[17]

M. Joye & S.-M. Yen, The Montgomery Powering Ladder,
Proc. CHES 2002, B.S. Kaliski Jr., Ç. Koç & C. Paar, (editors),
LNCS 2523, Springer-Verlag, 2003, pp. 291–302.

[18]

D. E. Knuth, The Art of Computer Programming, vol. 2, “Seminumerical Algorithms”, 3rd Edition, Addison-Wesley, 1997. ISBN
0-201-89684-2.

[19]Ç. K. Koç, Analysis of Sliding Window Techniques for Exponentiation, Computers & Mathematics with Applications 30 (10), 1995,
pp. 17–24.

[20]

P.-Y. Liardet & N. P. Smart, Preventing SPA/DPA in ECC Systems
using the Jacobi Form, Proc. CHES 2001, Ç. Koç, D. Naccache &C. Paar (editors), LNCS 2162, Springer-Verlag, 2001, pp. 391–401.

[21]

P. Longa & C. Gebotys, Fast Multibase Methods and Other Several
Optimizations for Elliptic Curve Scalar Multiplication, PKC 2009,
LNCS 5443, Springer-Verlag, 2009, pp. 443–462.

[22]

N. Meloni, New Point Addition Formulae for ECC Applications,
WAIFI 2007, LNCS 4547, Springer-Verlag, 2007, pp. 189–201.

[23]

P. K. Mishra & V. Dimitrov, Efficient Quintuple Formulas for
Elliptic Curves and Efficient Scalar Multiplication using Multibase
Number Representation, Information Security – ISC 2007, LNCS
4779, Springer-Verlag, 2007, pp. 390–406.

[24]

B. Möller, Improved Techniques for Fast Exponentiation, Information
Security and Cryptology – ICISC 2002, LNCS 2587, SpringerVerlag, 2003, pp. 298–312.

[25]

Peter L. Montgomery, Speeding the Pollard and elliptic curve methods

C ONCLUSION

The most compact versions of mixed base exponentiation
have been studied and compared to binary algorithms
which use the same space. The comparison was simplified by applying a recent space-preserving duality
between left-to-right and right-to-left algorithms whichshows that, to a first order, the two directions havethe same speed when given the same area. The maindifferences were identified, namely the space for therecoded exponent and preserving copies of the original
exponent and input message, the time reading from andwriting to memory, and differential costs for composite
group operations in the two directions. Even taking into
account the cost of recoding, the mixed base algorithms
were shown to be faster where inversion is essentially
free, such as in elliptic curve applications. So, in thepresence of side channel leakage, the arguably moresecure right-to-left direction of exponentiation may be
used with little or no speed or area penalty, and perhaps
even with some performance gain from not having tostore the recoding. The duality gives rise to a compact,
left-to-right mixed base algorithm which makes use of
efficient composite curve operations and is a few percent faster than that used recently by Longa and Gebotys[21] to obtain record speeds for scalar multiplication on
elliptic curves. The ability to tune the recoding algorithm
to make maximal use of cheap composite operations such
the Frobenius map means that mixed base algorithms canprovide better results in much wider contexts than theclassical binary-based exponentiation algorithms.

[1]

[4]

R. M. Avanzi, A Note on the Signed Sliding Window Integer Recoding
and a Left-to-Right Analogue, SAC 2004, LNCS 3357, SpringerVerlag 2005, pp. 130–143.
D. J. Bernstein, Pippenger’s Exponentiation Algorithm,
http://cr.yp.to/papers/pippenger.pdf, 2002.
A. Brauer, On Addition Chains, Bull. Amer. Math. Soc., 45 (10),1939, pp. 736–739.

C. D. WALTER (2011)

[26]

[27]

[28]

[29]
[30]

[31]

[32]
[33]

[34]

[35]
[36]

COMPACT EXPONENTIATION SCHEMES

of factorization, Mathematics of Computation 48(177), pp. 243–264,
Jan. 1987.
E. Oswald & M. Aigner, Randomized Addition-Subtraction Chainsas a Countermeasure against Power Attacks, Proc. CHES 2001, LNCS
2162, Springer-Verlag, 2001, pp. 39–50.
Y. Sakai & K. Sakurai, On the Power of Multidoubling in Speeding
Up Elliptic Curve Multiplication, SAC 2001, LNCS 2259, SpringerVerlag, 2001, pp. 268–283.
C. D. Walter, Exponentiation using Division Chains, Proc. 13th IEEE
Symposium on Computer Arithmetic (ARITH 13), IEEE, 1997,
pp. 92–98.
C. D. Walter, Sliding Windows succumbs to Big Mac Attack, CHES
2001, LNCS 2162, Springer-Verlag, 2001, pp. 286–299.
C. D. Walter, MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis, CT-RSA 2002, LNCS 2271,
Springer 2002, pp. 53–66.
C. D. Walter, Some Security Aspects of the MIST Randomized Exponentiation Algorithm, Proc. CHES 2002, LNCS 2523, SpringerVerlag, 2003, pp. 276–290.
C. D. Walter, Longer Keys May Facilitate Side Channel Attacks, SAC
2003, LNCS 3006, Springer-Verlag, 2004, pp. 42–57.
C. D. Walter, Fast Scalar Multiplication for ECC over GF(p) using
Division Chains, Proc. WISA 2010, LNCS 6513, Springer-Verlag,
2010, pp. 61–75.
C. D. Walter, A Duality in Space Usage between Left-to-Right
and Right-to-Left Exponentiation, Proc. CT-RSA 2012, LNCS 7178,
Springer-Verlag, 2012, pp. 84–97.
C. D. Walter, The Montgomery and Joye Powering Ladders are Dual,
IACR ePrint Archive 2017, No. 1081, 2017.
A. C.-C. Yao, On the Evaluation of Powers, SIAM J. Comput. 5(1),1976, pp. 100–103.

15