<<

. 5
( 19)



>>

Example 1: Large value for H
With when and then



So here the value of H is about double than average with only

Remark: has always such large H with small if
is even), we say that is not homogeneous”: see [12]. However, when
the probability that such inputs/outputs exist is generally negligible if we study
only one single specific permutation.

Example 2: Small value for H
Here our example cannot be with since we know that we always
have


(the proof is the same for and
However, we will show that when H can be much smaller than
average (i.e. is not necessary, is enough). In this example 2,
we will assume:
TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 121

1.
2.
3. (in example 3 below we will
not need this condition 3).

To get condition 3, we may assume, for example, that
and where is well chosen. So
From 1 we have:
From 2 we have:
H is the number of such that:




So H is times the number of such that:




Since all the are pairwise distinct, all the must be pairwise distinct.
So for we have exactly: solutions.
Now when are fixed, and are fixed on exactly
pairwise distinct points. So
Let be the average value of H (when the are pairwise distinct).




So here:




So when is not negligible compared with H will be significatively
smaller than , as claimed.

Remark 1. Here is not random (since is constant), and
is not random (in example 3 below we will remove this condition on
These hypothesis are generally unrealistic in a cryptographic attack, where
or and or cannot be chosen.
TEAM LinG
122 Jacques Patarin

Remark 2. If we start, as here, from values with constant, then the
values are pairwise distinct, so the values are perfectly random (if we
define only from the relation However, the values are
not perfectly random (since the probability to have is the
probability to have so is about double than average). Similarly,
the values are not perfectly random since the probability to have
and is in relation with the probability to have
so is about double than average. We will use again this idea in example 3 below.

Remark 3. Here when we can have circles in Y, S, (and circles in
R, Y) and this is a way to explain why in this example H can be much smaller
than .

Example 3: Small value for H, with random and
In this example 3, we will assume:

1.
2.
3. Let Then is random. More precisely it will
be enough to assume that the number N of collisions is
to show that H is small compared with the average value . For
random values we have so it is the case

As in example 2, H is times the number of such that:




Since all the are pairwise distinct, and all the are
pairwise distinct, and are fixed on exactly points when
is fixed.
So H is times the number of such that:

Let be a sequence of values of We want to evaluate the
number of such that: Let be the average
value for (average on all sequences We have For random values
and random functions will have about 2 times more collisions
than average sequences
So for random values is and for values with 2 times more
collisions than average is This shows that if in this example 3 is
random, then




TEAM LinG
Signed Binary Representations Revisited

Katsuyuki Okeya1, Katja Schmidt-Samoa2,
Christian Spahn2, and Tsuyoshi Takagi2
1
Hitachi, Ltd., Systems Development Laboratory,
292, Yoshida-cho, Totsuka-ku, Yokohama, 244-0817, Japan
ka-okeya@sdl.hitachi.co.jp
2
Technische Universit¤t Darmstadt, Fachbereich Informatik,
Hochschulstr. 10, D-64289 Darmstadt, Germany
{samoa,takagi}@ informatik.tu-darmstadt.de



Abstract. The most common method for computing exponentiation of
random elements in Abelian groups are sliding window schemes, which
enhance the efficiency of the binary method at the expense of some
precomputation. In groups where inversion is easy (e.g. elliptic curves),
signed representations of the exponent are meaningful because they de-
crease the amount of required precomputation. The asymptotic best
signed method is wNAF, because it minimizes the precomputation effort
whilst the non-zero density is nearly optimal. Unfortunately, wNAF can
be computed only from the least significant bit, i.e. right-to-left. How-
ever, in connection with memory constraint devices left-to-right recoding
schemes are by far more valuable.
In this paper we define the MOF (Mutual Opposite Form), a new canon-
ical representation of signed binary strings, which can be computed in
any order. Therefore we obtain the first left-to-right signed exponent-
recoding scheme for general width by applying the width sliding
window conversion on MOF left-to-right. Moreover, the analogue right-
to-left conversion on MOF yields wNAF, which indicates that the new
class is the natural left-to-right analogue to the useful wNAF. Indeed,
the new class inherits the outstanding properties of wNAF, namely the
required precomputation and the achieved non-zero density are exactly
the same.
Keywords: addition-subtraction chains, exponentiation, scalar multipli-
cation, signed binary, elliptic curve cryptosystem, efficient computation,
non-adjacent form (NAF), mutual opposite form (MOF), left-to-right


1 Introduction
In modern cryptosystems one of the most important basic operations is expo-
nentiation where is an element of an Abelian group G and is an integer.
A non-zero positive integer is uniquely represented by a binary string:


where denotes the concatenation of bits and for


M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 123“139, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
124 Katsuyuki Okeya et al.

The most common method for performing an exponentiation is the square-
and-multiply algorithm, which computes according to the bits (therefore it
is often called binary method). The efficiency of this procedure may be enhanced
if precomputation is allowed. In this case, we consider more general represen-
tations of the exponent, where each non-zero bit is not restricted to be 1,
but is an element of a suitable digit set of integers. We call a
if holds for each In general,
loose the property of uniqueness. The left-to-right square-and-multiply algorithm
is easily adjusted to work with a of the exponent, namely multi-
plication by the base is replaced with multiplication by precomputed elements
where is the appropriate digit of Therefore, the important fea-
tures of a are the number of non-zero digits and the cardinality
of because they determine the required time and memory consumption for
computing respectively. The research problem here is to find optimized rep-
resentation classes in the sense of trade-off between high non-zero density and
low memory consumption.

1.1 New Motivation for Exponentiation Algorithms
As the ubiquitous computing devices are penetrating our daily life, the impor-
tance of memory constraint devices (e.g. smart cards) in cryptography is increas-
ing. Smart cards are equipped with several Kbytes RAM only and most of them
are reserved for OS and stack. Thus, cryptographic algorithms should be opti-
mized in terms of memory. For this reason we are reluctant to consume memory
except the necessary precomputation related to for computing exponentia-
tion. Note that in connection with memory constraint devices, the most popular
cryptosystems are based on elliptic curves [Kob87,Mil86], because elliptic curve
cryptosystems (ECC) provide high security with moderate key-lengths. As ellip-
tic curve groups are written additively, exponentiation has to be understood as
scalar multiplication in this context.
Exponent recoding, i.e. the rewriting of the binary exponent to a
may be performed from the least significant bit (we say “right-to-left”)
and from the most significant bit (“left-to-right”), respectively. For the pur-
pose of ECC on memory constraint devices we prefer left-to-right to right-to-left
recoding methods. The reason is as follows: In the case of elliptic curve scalar
multiplication, the left-to-right evaluation stage is the natural choice (see Section
5 for details). If the exponent recoding is done right-to-left, it is necessary to fin-
ish the recoding and to store the recoded string before starting the left-to-right
evaluation stage. In other words, we require additional (i.e. exponential
size RAM for the right-to-left exponent recoding, where is the bit size
of the scalar.
On the contrary, if a left-to-right recoding technique is available, the recoding
and evaluation stage may be merged to obtain an efficient exponentiation on the
fly, without storing the recoded exponent at all. Therefore it is an important
task to construct a left-to-right recoding scheme, even if the size of and the
non-zero density are not improved.
TEAM LinG
Signed Binary Representations Revisited 125

1.2 Known Solutions

The most established techniques for generating representations are window
methods (see, e.g., the textbooks [Knu81,MOV96] and the survey paper [Gor98]).
Loosely speaking, in the window method with width successively consecutive
bits of the binary exponent are scanned and, if necessary, replaced by a table-
entry according to We distinguish fixed window methods like the
method, where the window segmentation of the binary string is predetermined
and the more advanced sliding window methods, where zero runs are skipped.
As an example, let us consider the sliding window method with width In
this case, equals {1,3,5,7}. During the recoding stage, the binary exponent
is rewritten by performing the following replacements:
and Note that the sliding window conversion can be performed
left-to-right and right-to-left as well. The results may differ syntactically, but
the asymptotic non-zero density of both representations is the same, namely
In the unsigned case (i.e. consists only of positive integers), sliding
window techniques are the method of choice.
However, a nice property of elliptic curves is that inversion is computed vir-
tually for free. In this case, it is meaningful to consider digit sets containing
negative integers, too. This reduces precomputation effort, because may be
computed from on the fly, such that only the elements for have
to be precomputed. However, the question arises how to construct a signed
representation. In general, there are two strategies. The first one is to construct a
{“1, +1} representation of (also called a signed binary representation) and to
apply window methods afterwards. Here, the most common signed binary rep-
resentation is NAF (non-adjacent-form) [Rei60,IEEE], which can be obtained
from the binary representation by applying the conversion
repeatedly, where denotes “1 and stands for any binary digit. However, the
carry-over +1 occurring in the first digit forces the recoding to be performed
from the least significant bit, i.e. right-to-left. The second strategy is to gen-
eralize the NAF recoding for in order to obtain wNAF [Sol00,BSS99]
(here, the non-adjacent property states that among any adjacent bits, at
most one is non-zero). According to [BSS99], this strategy is the optimal one
for But unfortunately, this strategy suffers from the same drawback as
the first one, namely as carry-overs are required, the recoding is restricted to be
done right-to-left. Consequently, all exponentiation strategies based on signed
require bits of RAM additional memory to store the
recoded exponent. Solely in the case of Joye and Yen proposed a left-
to-right binary recoding algorithm [JY00]. But it has been an unsolved problem
to generate a left-to-right recoding algorithm for a general width Note
that the asymptotic non-zero density of wNAF is the same as for the unsigned
sliding window method on binary, namely Therefore, wNAF can be
seen as its natural signed analogue, and we guess that there could be a carry-
free generation method for wNAF. In this paper, the term carry-free refers to
an algorithm that transforms the input string in situ, i.e. in each step only the
knowledge of a fixed number of consecutive input bits is necessary.
TEAM LinG
126 Katsuyuki Okeya et al.

1.3 Our Contributions

The aim of this paper is to solve both problems as follows: (1) we define a new
canonical representation class of signed binary. We call it MOF (Mutual Opposite
Form) and prove that each integer can be uniquely represented as a MOF. But
the outstanding property of MOF is that it can be efficiently developed from a
binary string right-to-left or left-to-right, likewise. Consequently, analogue to the
unsigned case, sliding window methods may be applied to receive left-to-right
and right-to-left recoding schemes for general width Surprisingly, applying the
right-to-left width sliding window method on MOF yields wNAF. However,
the observation that in the unsigned case right-to-left sliding window yields
an unsigned string with non-adjacent property stresses the analogy between
unsigned Binary and signed MOF. Therefore we achieve a carry-free wNAF
generation, a benefit of its own.
(2) Our major aim is to develop a left-to-right recoding algorithm, and this
is achieved straightforwardly by applying the width sliding window method
left-to-right on MOF. We call the so-defined class wMOF and prove that each
integer can be uniquely represented as a wMOF and that the asymptotic non-
zero density of wMOF equals which is the same as for wNAF. Therefore
the classes wNAF and wMOF may be seen as dual to each other. In general our
proposed algorithm asymptotically requires additional bits of RAM, which
is independent from the bit size and dramatically reduces the required space
comparing with previous methods. Consequently, due to its left-to-right nature,
the new scheme is by far more convenient with respect to memory consumption
than previous schemes. Interestingly, a straight-forward proof shows that for
the proposed method produces the same output as the Joye-Yen recoding,
but 2MOF is more efficient in terms of counting the number of basic operations.
We finish this work with some explicit algorithms, proving that the proposed
schemes are indeed useful for practical purposes. For example, we develop gen-
erating algorithms for wMOF based on efficient table-lookups, and we show how
to exploit wMOF for implementing on-the-fly elliptic curve scalar multiplication.


2 Signed Representations

In this section we review some signed representations, which are important in
connection with elliptic curve scalar multiplication. For the sake of simplicity,
we only deal with non-negative integers in the following. We call
a if is a set of integers and holds for each
If contains negative integers, we speak of signed representations, and if
equals {±1}, of signed binary representations. In general, signed binary repre-
sentations are redundant. The most established one is NAF (non-adjacent form),
introduced by Reitwiesner 1960 [Rei60]. A generalization of Reitwiesner™s NAF
recoding idea can be found in [Pro00,Avi61]. NAF can be easily defined by the
property that at most one out of two consecutive digits is non-zero. Reitwiesner
was able to show that ignoring leading zeros each integer has a unique NAF
TEAM LinG
Signed Binary Representations Revisited 127

representation. For this reason, some authors call NAF a canonical signed bi-
nary representation [EK94]. In addition, as shown among others by Jedwab and
Mitchell [JM89], NAF representation provides the minimal Hamming weight.
Consequently, the NAF representation of the exponent is the optimal choice if
signed methods are meaningful and no precomputation is considered. It was first
pointed out by Morain and Olivos that NAF can be used to speed up elliptic
curve scalar multiplication [MO90].
However, the situation is less clear if extra memory is available and precom-
putation is admitted. In this case, signed representations using larger digit sets
should be taken into account. One strategy to construct a signed representa-
tion is to apply sliding window methods on signed binary representations. But as
signed binary representation is redundant, the question arises which representa-
tion is the best for this purpose. Indeed, this is assumed to be an open problem
by De Win et al. [WMPW98]. There are several methods to construct signed
binary representations as a base for sliding window schemes [KT92,WMPW98],
but none of these can be performed left-to-right. In this paper, we will develop a
left-to-right recoding scheme, which is of high value in connection with memory
constraint devices.
A different approach is wNAF. Instead of applying window techniques to
signed binary representations, wNAF is computed directly from binary strings
using a generalization of NAF recoding. First we review the definition of wNAF
as stated in [Sol00].

Definition 1 (wNAF). A sequence of signed digits is called wNAF iff the fol-
lowing three properties hold:

1. The most significant non-zero bit is positive.
2. Among any consecutive digits, at most one is non-zero.
3. Each non-zero digit is odd and less than in absolute value.

Note that 2NAF and NAF are the same. Algorithm 1 describes the generation
of wNAF as proposed by Solinas [Sol00].




TEAM LinG
128 Katsuyuki Okeya et al.

Here “mods” means the signed modulo, namely mods is defined as mod
and The algorithm generates wNAF from the least signif-
icant bit, that is right-to-left generation again. The average density of non-
zero bits is asymptotically for and the digit set equals
which seems to be minimal. Thus wNAF and
its variants like modified window NAF [Möl02] are optimal in the sense of the
trade-off between speed and memory for [BSS99,BHLM01]. There are
several other algorithms for generating wNAF, for example see [BSS99,MOC97]
but each method needs carry-overs. Note that in the worst case all remaining
bits are affected by the carry, therefore the previously known wNAF algorithms
can not be considered as local methods. By inspecting Algorithm 1 closely, we
observe that this generation can be seen as the natural signed analogue to the
right-to-left sliding window method on (unsigned) Binary (here, mod instead of
mods is computed). Indeed, the latter method produces a representation that
fulfills the nonadjacent requirement (see Definition 1, property 3). Consequently,
we conjecture that there might be a signed binary representation that produces
wNAF when handled with sliding window conversions. The signed binary rep-
resentation introduced in the next section will also serve for this purpose.

3 MOF: New Canonical Representation
for Signed Binary Strings
In this section we present a new signed representation of integers. The proofs of
the propositions in this section are in the full version of this paper [OSST04].
In order to achieve a unique representation, we introduce the following special
class of signed binary strings, called the mutual opposite form (MOF).
Definition 2 (MOF).The mutual opposite form (MOF) is an signed
binary string that satisfies the following properties:
1. The signs of adjacent non-zero bits (without considering zero bits) are oppo-
site.
2. The most non-zero bit and the least non-zero bit are 1 and respectively,
unless all bits are zero.
Some zero bits are inserted between non-zero bits that have a mutual opposite
sign. An example of MOF is An important observation is that
each positive integer can be uniquely represented by MOF. Indeed, we have the
following theorem.
Theorem 1. Let be a positive integer. MOF has pair-wise
different representations. There is the bijective map between elements of
MOF and binary strings.
From this theorem, any binary string can be uniquely represented by
MOF. We obviously have the following corollary about the non-zero
density of MOF.
Corollary 1. The average non-zero density of MOF is 1/2 for

TEAM LinG
Signed Binary Representations Revisited 129

3.1 Converting Binary String to MOF
We show a simple and flexible conversion from binary string to
MOF.
The crucial point is the following observation. The binary string can
be converted to a signed binary string by computing where
stands for a bitwise subtraction. Indeed, we convert as follows:




Here the signed bit of is denoted by namely for
and We can prove that the signed representation
is MOF.
Proposition 1. The operation converts binary string to its MOF
Algorithm 2 provides an explicit conversion from Binary to MOF.




In order to generate the bit Algorithm 2 stores just two consecutive
bits and This algorithm converts a binary string to MOF from the most
significant bit in an efficient way. Note that it is also possible to convert a binary
string to MOF right-to-left. Thus MOF representation is highly flexible.
Remark 1. Interestingly, the MOF representation of an integer equals the re-
coding performed by the classical Booth algorithm for binary multiplication
[Boo51]. The classical Booth algorithm successively scans two consecutive bits
of the multiplier A (right-to-left). Depending on these bits, one of the following
operations is performed:
No operation, if
Subtract multiplicand B from the partial product, if
Add multiplicand B to the partial product, if
where is defined as 0. Of course, the design goal of this algorithm was to
speed up multiplication when there are consecutive ones in the multiplier A, and
to provide a multiplication method that works for signed and unsigned numbers
as well. To our knowledge, this representation never served as a fundament of
theoretical treatment of signed binary strings.

TEAM LinG
130 Katsuyuki Okeya et al.

4 Window Methods on MOF
In this section we show how to decrease the non-zero density of MOF by ap-
plying window methods on it. First we consider the right-to-left width sliding
window method which surprisingly yields the familiar wNAF. In contrast to pre-
viously known generation methods, the new one is carry-free, i.e. in each step
the knowledge of at most consecutive input bits is sufficient.
Then we define the dual new class wMOF as the result of the analogue left-
to-right width sliding window method on MOF. This conversion leads to the
first left-to-right signed recoding scheme for general width

4.1 Right-to-Left Case: wNAF
In order to describe the proposed scheme, we need the conversion table for width
First, we define the conversions for MOF windows of length such that the
first and the last bit is non-zero:




In addition, we have analogue conversions with all signs changed. To generate
the complete table for width we have to consider all conversions of length
If holds, the window is filled with leading zeros.
Example: In the case of we use the following table for the right-to-left
sliding window method:



In an analogue way is defined for general Based on this table,
Algorithm 3 provides a simple carry-free wNAF generation.




TEAM LinG
Signed Binary Representations Revisited 131

Obviously, the output of Algorithm 3 meets the notations of Definition 1,
therefore it is wNAF. If we knew that Definition 1 provides a unique represen-
tation, we could deduce that Algorithm 3 outputs the same as Algorithm 1.
This is true, although we could not find a proof in literature. For the sake of
completeness, we prove the following theorem in the full version of this paper
[OSST04] via exploiting the uniqueness of MOF representation.
Theorem 2. Every non-negative integer has a representation as wNAF , which
is unique except for the number of leading zeros.

4.2 Left-to-Right Case: wMOF
In this section we introduce our new proposed scheme. The crucial observation
is that as the generation Binary MOF can be performed left-to-right, the
combination of this generation and left-to-right sliding window method leads to
a complete signed left-to-right recoding scheme dual to wNAF.
In order to describe the proposed scheme, we need the conversion table for
width The conversions for MOF windows of length such that the first and
the last bit is non-zero, are defined in exactly the same way as in the right-to-
left case (see the table in section (4.1) and reflect the assignments). To generate
the complete table for width we have to consider all conversions of length
as before. The only difference is that if holds, the window
is filled with closing zeros instead of leading ones. As an example, we construct
the conversion table for width 4:




The table is complete due to the properties of MOF. Note that because of the
equalities usually two different MOF-strings are converted
to the same pattern. In an analogue way, is defined for general width
In this case the digit set equals which is
the same as for wNAF. Therefore, the scheme requires only precomputed
elements. Algorithm 4 makes use of this table to generate wMOF left-to-right.
In order to deepen the duality between wNAF and wMOF, we give a formal
definition of wMOF and prove that it leads to a unique representation of non-
negative integers.
Definition 3. A sequence of signed digits is called wMOF iff the following three
properties hold:
1. The most significant non-zero bit is positive.
2. All but the least significant non-zero digit are adjoint by zeros as
follows:
in case of for an integer the pattern
equals

TEAM LinG
132 Katsuyuki Okeya et al.

in case of either the pattern equals and the next lower

non-zero digit has opposite sign from or the pattern equals

and the next lower non-zero digit has the same sign as
If is the least significant non-zero digit, it is possible that the number of
right-hand adjacent zeros is smaller than stated above. In addition it is not
possible that the last non-zero digit is a 1 following any non-zero digit.
3. Each non-zero digit is odd and less than in absolute value.
This definition is directly related to the generation of wMOF. Note that the
exceptional case corresponding to the least significant bit takes in account that
the last window may be shorter than




Regarding the uniqueness and the non-zero density of wMOF, we have the
following two theorems, proven in the full version of this paper [OSST04].
Theorem 3. Every non-negative integer has a representation as wMOF, which
is unique except for the number of leading zeros.
Theorem 4. The average non-zero density of wMOF is asymptotically
for
We finish this section with a detailed example of the conversion from Binary
to MOF and the effects of several sliding window methods.




TEAM LinG
Signed Binary Representations Revisited 133

Left-to-Right Generation of
4.3
Although in the preceding section we have presented left-to-right generated
signed representations that are at least as useful as from a theoretical
point of view it is still an interesting question how to generate the from
the most significant bit. The reason for the difficulty is a carry caused by the
statement of Algorithm 1. To illustrate the problem, note that the bi-
nary strings 101010 and 101011 that only differ in the last digit are converted to
the NAFs 101010 and respectively, which differ completely. Intuitively,
it is not possible to generate NAF left-to-right without scanning any higher bits.
In this section we exploit the MOF representation to discuss how many bits have
to be scanned and how many additional storage is required.
Note that we obtain NAF if we apply the conversions and
right-to-left on MOF. However, performing the same conversions left-to-right
may yield a different result. The critical sequence is of the shape




Note that this sequence corresponds to the binary string 1010 . . . 011. If the
length of the sequence of alternating bits is even, then both of left-to-right and
right-to-left conversions uniquely generate the same string, namely
for But if the length is odd, left-to-right we obtain
whereas right-to-left generates Consequently,
if this sequence appears, we have to scan it completely in order to compute the
corresponding NAF. However, the first bit and the length of the critical sequence
can uniquely determine the corresponding NAF, hence it is not necessary to store
the sequence. Thus, the additional required storage in RAM is at most a few bits,
namely the bit length of the critical sequence. Therefore, we obtain Algorithm 5.




TEAM LinG
134 Katsuyuki Okeya et al.

It is also possible to construct a left-to-right generation algorithm of wNAF,
In this case, the critical sequence is of the following shape




where the most and least bits are zero and no zero run of length
appears in If it is possible to convert the critical sequence (1)
left-to-right to wNAF, then we can generate wNAF from any MOF. In order
to find the corresponding wNAF of (1), we scan the whole sequence right-to-
left and obtain the segmentations that are produced by the right-to-left sliding
window conversion MOF wNAF. Note that there is no need to store the width
windows, but we must detect and store the length of the zero runs between
any two windows. In addition, the content of the left-most window, which may
be smaller than has to be transfered. Afterwards, the sequence (1) can be
rewritten as follows:




where consists of at most consecutive bits of MOF (and may be the
empty word and each is a length pattern of

MOF, corresponding to an entry of Here we have to store and the
Based on these informations, the corresponding wNAF is completely determined
left-to-right. Thus we need to store at most bits.

4.4 Comparison with Previous Methods
In this section we clarify the difference to previous schemes for generating signed
representations.
In 1992, Koyama and Tsuruoka developed a new recoding technique to con-
vert a binary string to a signed binary string [KT92]. Following this step, a
left-to-right sliding window method is applied. The new signed binary represen-
tation has the benefit that it reduces the asymptotic non-zero density, but it
requires the sub-optimal digit set If the sliding
window method is directly applied to NAF, due to the NAF property fewer pos-
sible window contents have to be taken into account, resulting in a smaller digit
set An easy calculation shows that the largest odd NAF consisting of at most
digits equals for odd (cf. 1010...01) and for
even (cf. 1010 . . . 1001). For this reason, De Win et al. prefer the latter method
for elliptic curve scalar multiplication [WMPW98]. Although there are slightly
more point operations needed to evaluate the scalar multiplication if the expo-
nent is represented as wNAF compared to the [WMPW98] representation, the
required precomputation is less in the wNAF case because of the smaller digit
set. Indeed, Blake et al. proved that wNAF is asymptotically better than sliding
window on NAF schemes if [BSS99]. In the context of memory constraint
TEAM LinG
Signed Binary Representations Revisited 135

devices, a small digit set is even more valuable, because fewer precomputed el-
ements have to be stored. But as none of the preceding methods is a left-to-right
scheme, each one requires additional memory to store the recoded string
before starting the left-to-right evaluation of the scalar product. Note that in
the context of sliding window on signed binary schemes like [KT92,WMPW98]
the sliding window conversion may be performed left-to-right, but to obtain the
signed binary representation we have to proceed right-to-left in either case.
In contrast, wMOF turns out as a complete left-to-right scheme. Conse-
quently, there is no additional memory required for performing the scalar mul-
tiplication. In addition, due to the properties of MOF, the digit set of wMOF is
the same as for wNAF and therefore minimal.
In order to compare the proposed algorithms with previous ones, we summa-
rize the memory requirements of the new left-to-right schemes in the following
theorem.
Theorem 5. Algorithm 4 requires only bits memory for generating wMOF.
Algorithm 5 requires at most bits memory for generating NAF left-to-
right. For general width there is a left-to-right algorithm that generates wNAF
with at most bit memory.
Next, we compare the characterizing properties for the proposed schemes and
some previous ones. In the second column, the value equals the number
of elements, that have to be precomputed and stored. In the last column, we
describe the amount of memory (in bits) that is required additionally to this
storage, e.g. to construct the signed representation or to store the converted
string in right-to-left schemes. As usual, equals the bit-length of the scalar,
and SW is an abbreviation for sliding window.




5 Applications to Elliptic Curve Scalar Multiplication
Let be a finite field, where is a prime. Let E be an elliptic
curve over K. The elliptic curve E has an Abelian group structure with identity
element called the point of infinity. A point is represented as
The inverse of point is equal to hence it can be
computed virtually for free. The elliptic curve additions and 2P are
denoted by ECADD and ECDBL, respectively, where
TEAM LinG
136 Katsuyuki Okeya et al.

As elliptic curves are written additively, exponentiation has to be under-
stood as scalar multiplication. The familiar binary algorithms are adopted by
computing ECADD instead of multiplying and ECDBL instead of squaring.
In general, we distinguish two main concepts of performing scalar multiplica-
tion: left-to-right and right-to-left. Here, is represented as




Though in general both methods provide the same efficiency, the left-to-right
method is preferable due to the following reasons:
1. The left-to-right method can be adjusted for general of
like wNAF or wMOF in a more efficient way than the right-to-left method.
2. The ECADD step in the left-to-right method has the fixed input tP,
Therefore it is possible to speed up these steps if tP is expressed in affine
coordinates for each since some operations are negligible in this case.
The improvement for a 160-bit scalar multiplication is about 15% with NAF
over right-to-left scheme in the Jacobian coordinates [CMO98].
3. The right-to-left method needs an auxiliary register for storing


5.1 Explicit Implementation for
In the following we show how the ideas of Section 4.2 lead to an efficient left-to-
right scalar multiplication algorithm. For the sake of simplicity, we begin with
the special case The treatment for general width can be found in the
full version of this paper [OSST04].
Let be a binary string. The MOF and 2MOF representation of are
denoted by and respectively. The proposed scheme scans the two bits
of from the most significant bit, and if the sequences or appear, we
perform the following conversions: and Two consecutive
bits of determine the corresponding bit of MOF Thus, three consecutive
bits of can generate the corresponding bit of the 2MOF In order to find
an efficient implementation, we discuss the relationship of bit representation
among and The bits of are denoted by respec-
tively. Because of the relation we know if and only
if The other 3-bit binary strings where
are only corresponding to
Thus, there is a one-to-one map be-
tween and leading to the explicit Algorithm 6.
TEAM LinG
Signed Binary Representations Revisited 137




Finally, Algorithm 7 merges the recoding stage and evaluation stage of scalar
multiplication.




The advantage of the previous algorithm is that it reduces the memory re-
quirement since it does not store the converted representation of
TEAM LinG
Katsuyuki Okeya et al.
138

6 Conclusion
It was an unsolved problem to generate a signed representation left-to-right for
a general width In this paper we presented a solution of this problem. The
proposed scheme inherits the outstanding properties of wNAF, namely the set
of pre-computed elements and the non-zero density are same as those of wNAF.
In order to achieve a left-to-right exponent recoding, we defined a new canonical
representation of signed binary strings, called the mutual opposite form (MOF).
An integer can be uniquely represented by MOF, and this repre-
sentation can be constructed efficiently left-to-right. Then the proposed exponent
recoding is obtained by applying the width (left-to-right) sliding window con-
version to MOF. The proposed scheme is conceptually easy to understand and
it is quite simple to implement. Moreover, if we apply the width (right-to-left)
sliding window conversion to MOF, we surprisingly obtain the classical wNAF.
This is the first carry-free algorithm for generating wNAF. Therefore the pro-
posed scheme has a lot of advantages and it promises to be a good alternative to
wNAF. We believe that there will be many new applications of this algorithms
for cryptography.

References
[Avi61] Aviziensis, A., Signed digit number representations for fast parallel arith-
metic, IRE Trans. Electron. Comput., 10:389-400, (1961).
[BSS99] Blake, I., Seroussi, G., and Smart, N., Elliptic Curves in Cryptography,
Cambridge University Press, 1999.
Brown, M., Hankerson, D., Lopez, J., and Menezes, A., Software Im-
[BHLM01]
plementation of the NIST Elliptic Curves Over Prime Fields, Topics in
Cryptology - CT-RSA 2001, LNCS 2020, (2001), 250-265.
[Boo51] Booth, A., A signed binary multiplication technique, Journ. Mech. and
Applied Math., 4(2), (1951), 236-240.
[CMO98] Cohen, H., Miyaji, A., and Ono, T., Efficient Elliptic Curve Exponenti-
ation Using Mixed Coordinates, Advances in Cryptology - ASIACRYPT
™98, LNCS1514, (1998), 51-65.
[EK94] Egecioglu, –, and Koc, C, Exponentiation using Canonical Recoding, The-
oretical Computer Science, 129(2), (1994), 407-417.
[Gor98] Gordon, D., A survey of fast exponentiation methods, Journal of Algo-
rithms, vol.27, (1998), 129-146.
[IEEE] IEEE P1363, Standard Specifications for Public-Key Cryptography.
http://groupe.ieee.org/groups/1363/
[JM89] Jedwab, J., and Mitchell, C.J., Minimum Weight Modified Signed-digit
Representations and Fast Exponentiation, Electronics Letters 25, (1989),
1171-1172.
Joye, M., and Yen, S.-M., Optimal Left-to-Right Binary Signed-digit Expo-
[JY00]
nent Recoding, IEEE Transactions on Computers 49(7), (2000), 740-748.
Knuth, D. E., The art of computer programmming, vol. 2, Seminumerical
[Knu81]
Algorithms, 2nd ed., Addison-Wesley, Reading, Mass. (1981).
[Kob87] Koblitz, N., Elliptic Curve Cryptosystems, Math. Comp. 48, (1987), 203-
209.

TEAM LinG
Signed Binary Representations Revisited 139

[KT92] Koyama, K. and Tsuruoka, Y., Speeding Up Elliptic Curve Cryptosys-
tems using a Signed Binary Windows Method, Advances in Cryptology -
CRYPTO ™92, LNCS740, (1992), 345-357.
[Mil86] Miller, V.S., Use of Elliptic Curves in Cryptography, Advances in Cryp-
tology - CRYPTO ™85, LNCS218, (1986), 417-426.
[MO90] Morain, F., Olivos, J., Speeding Up the Computations on an Elliptic Curve
using Addition-Subtraction Chains, Informa. Theor. Appl., 24, (1990),
pp.531-543.
[MOC97] Miyaji, A., Ono, T., and Cohen, H., Efficient Elliptic Curve Exponentia-
tion, Information and Communication Security, ICICS 1997, LNCS 1334,
(1997), 282-291.
[MOV96] Menezes, A., van Oorschot, P. and Vanstone, S., Handbook of Applied
Cryptography, CRC Press, 1996.
[Möl02] Möller, B., Improved Techniques for Fast Exponentiation, The 5th In-
ternational Conference on Information Security and Cryptology (ICISC
2002), LNCS 2587, (2003), 298-312.
[OCo99] O™Connor, L., An Analysis of Exponentiation Based on Formal Lan-
guages, Advances in Cryptology - EUROCRYPT ™99, LNCS1592, (1999),
375-388.
[OSST04] Okeya, K., Schmidt-Samoa, K., Spahn, C., Takagi, T., Signed Binary
Representations Revisited, Cryptology ePrint Archive (2004).
http://eprint.iacr.org/
[Pro00] Prodinger, H., On Binary Representations of Integers with Digits {-1,0-
1}, Integers: Electronic Journal of Combinatorial Number Theory 0,
(2000)
[Rei60] Reitwiesner, G. W., Binary arithmetic, Advances in Computers, vol.1,
(1960), 231-308.
[Sol00] Solinas, J.A., Efficient Arithmetic on Koblitz Curves, Designs, Codes and
Cryptography, 19, (2000), 195-249.
[WMPW98] Win, E., Mister, S., Preneel, B., and Wiener, M., On the Performance of
Signature Schemes Based on Elliptic Curves, Algorithmic Number The-
ory, ANTS-III, LNCS 1423, (1998), 252-266.




TEAM LinG
Compressed Pairings

Michael Scott1,* and Paulo S.L.M. Barreto2
1
School of Computing, Dublin City University
Ballymun, Dublin 9, Ireland
mike@computing.dcu.ie
2
Escola Polit©cnica, Universidade de São Paulo
Av. Prof. Luciano Gualberto, tr. 3, 158
BR 05508-900, São Paulo(SP), Brazil
pbarreto@larc.usp.br




Abstract. Pairing-based cryptosystems rely on bilinear non-degenerate
maps called pairings, such as the Tate and Weil pairings defined over
certain elliptic curve groups. In this paper we show how to compress
pairing values, how to couple this technique with that of point compres-
sion, and how to benefit from the compressed representation to speed
up exponentiations involving pairing values, as required in many pairing
based protocols.
Keywords: pairing-based cryptosystem, efficient implementation.


1 Introduction
With the discovery of a viable identity-based encryption scheme based on the
Weil pairing [5], pairing-based cryptography has become of great interest to
cryptographers. Since then, pairing-based protocols “ many with novel properties
“ have been proposed for key exchange [30], digital signature [6], encryption [5],
and signcryption [28]. Although the Weil pairing was initially proposed as a
suitable construct for the realisation of such protocols, it is now usually accepted
that the Tate pairing is preferable for its greater efficiency. Supersingular elliptic
curves were originally proposed as a suitable setting for pairing-based schemes;
recent work has shown that certain ordinary curves are equally suitable, and
offer greater flexibility in the choice of security parameters [3, 26]. Fast computer
algorithms for the computation of the Tate pairing on both supersingular and
ordinary curves have been suggested in [1, 3, 12].
The Tate pairing calculation involves an application of Miller™s algorithm [24]
coupled to a final exponentiation to get a unique value. A typical protocol step
requires the calculation of a pairing value followed by a further exponentiation
of the result.
In this paper we explore the concept of compressed pairings, their efficient
computation, and the subsequent processing (typically exponentiation) of pairing
values. Our main contribution is to show that one can effectively reduce the
Supported in part by Enterprise Ireland RIF grant IF/2002/0312/N
*


M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 140“156, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
Compressed Pairings 141

bandwidth occupied by pairing values without impairing security nor processing
time; in some cases, one even obtains a 30%“40% speed enhancement. Our work
gives further motivation for the approach of Galbraith et al. [14], who investigate
the bit security of pairing values and show that taking the trace causes no loss
of security.
This paper is organized as follows. Section 2 introduces basic mathemati-
cal concepts. Section 3 discusses laddering exponentiation of pairing values, and
introduces a laddering variant of the BKLS [1] algorithm to compute pairings.
Section 4 describes how to compress pairing values to half length, and establishes
a connection with the techniques of point compression and point reduction. Sec-
tion 5 defines a ternary exponentiation ladder for finite fields in characteristic 3.
Section 6 describes how to compress pairing values to one third of their length,
presents a more efficient and slightly simpler version of the Duursma-Lee algo-
rithm [11] that enables pairing computation in compressed form, and discusses
improved variants of point compression and point reduction in characteristic 3.
We summarise our work in section 7.


2 Mathematical Preliminaries

The theory behind elliptic curve cryptography is well documented in standard
texts. The reader is referred to [23] for more background.
Let be a prime number, a positive integer and the finite field with
elements; is said to be the characteristic of and is its extension
degree. Unless otherwise stated, we assume throughout this paper.
Let An elliptic curve is the set of solutions over to
an equation of form where
together with an additional point at infinity, denoted O. The same equation
defines curves over for (although note that the remain in The
number of points on an elliptic curve denoted is called the
order of the curve over the field
An (additive) Abelian group structure is defined on E by the well known
secant-and-tangent method [29]. Let The order of a point
is the least nonzero integer such that rP = O, where rP is the sum of terms
equal to P. The order of a point divides the curve order. For a given integer
the set of all points such that rP = O is denoted We say that
has embedding degree if and for any In this
paper we assume It is in fact not difficult to find suitable curves with
this property for relatively small values of as described in [2, 7, 10]. We are
interested here in curves where is even, as this case facilitates fast calculation
of the Tate pairing [3].
For our purposes, a divisor is a formal sum of points on
the curve An Abelian group structure is defined on the set of divisors
by the addition of corresponding coefficients in their formal sums; in particular,
The degree of a divisor is the sum
Let be a function on the curve and let We define
TEAM LinG
142 Michael Scott and Paulo S.L.M. Barreto

The divisor of a function is A
divisor is called principal if for some function A divisor is
principal if and only if and [23, theorem 2.25]. Two
divisors and are equivalent, if their difference is a principal
divisor. Let where is coprime to and let be a divisor
equivalent to (P) “ (O); under these circumstances the divisor is principal,
and hence there is a function such that The
(reduced) Tate pairing of order is the map given
by for some divisor The Tate pairing
is bilinear and non-degenerate; assuming one gets if Q is
chosen from a coset containing a point of order which is linearly independent
from P. The computation of is achieved by an application of Miller™s
algorithm [24], whose output is only defined up to an power in The final
exponentiation to the power of is needed to produce a unique result,
and it also makes it possible to compute rather than [1]. Sometimes
we will drop the subscript of the Tate pairing, writing simply


2.1 Lucas Sequences

Lucas sequences provide a relatively cheap way of implementing exponen-
tiation in a subgroup whose order divides They have been extensively
studied in the literature, and a fast “laddering” algorithm for their computa-
tion has been developed [18,19,32], using ideas originally developed by Lehmer
and Montgomery [20,27]. Lucas sequences have been suggested as a suitable
vehicle for certain public-key schemes (see [4]). The laddering algorithm can in
fact be used as an alternative to the standard square-and-multiply approach to
exponentiation in any Abelian group, but it is particularly well-suited for Lu-
cas sequences and certain parameterisations of elliptic curves [19]. The authors
of [19] go on to emphasise that the laddering algorithm requires very little mem-
ory, facilitates parallel computing, and has a natural resistance to side-channel
attacks when used in a cryptographic context.
The Lucas sequence consists of a pair of functions
Commonly one is interested in computing and for some field
element P, in which case we write simply and or omit the arguments
altogether. For this distinguished case the sequences are defined as




Only the sequence needs to be explicitly evaluated, as we also have the
relationship


The fast laddering algorithm is described in Appendix A. Lucas sequences
are useful in the exponentiation of certain field elements, as we will see next.
TEAM LinG
Compressed Pairings 143

3 Exponentiating Pairing Values
We consider first the case of embedding degree (although the following
discussion also covers the case with the substitution Recall that
we assume the characteristic to be odd.
We represent an element of the field as where and
for some quadratic non-residue Assume in what follows that all
arithmetic is in the field
The final exponentiation in this case consists of a raising to the power of
This can be considered in two parts “ exponentiation to the
power of followed by exponentiation to the power of Now if the
output of Miller™s algorithm is then



which is obviously much quicker than the standard square-and-multiply algo-
rithm. The element calculated in this fashion has the
property:

where is called the norm of this property, easily verified by simple
substitution, is maintained under any subsequent exponentiation. An element of
this form in is called unitary [16]. Also observe that
for a unitary element. In fact, any element of whose order divides will
have this property.
A unitary element can obviously be determined up to the sign of from
alone, using equation 1. And this is our first observation - the output of the Tate
algorithm contains some considerable redundancy. It could be represented by a
single element of and a single bit to represent the sign of rather than as a
full element of
One can efficiently raise a unitary element of to a power by means of
Lucas sequences. This is a consequence of the observation that



as one can verify by induction. As pointed out above, only needs to be
explicitly calculated.
If M is a multiplication and S a squaring in then the computational cost
of this method to compute is therefore 1M + 1S per step, where a
step involves the processing associated with a single bit of (see appendix A).
The conventional binary exponentiation algorithm in takes 1 squaring and
about 1/2 multiplication in for an overall cost of roughly 2S + 5M/2 per
then this can be reduced to 2S + 3M/2 per step1. Thus the
step. If
improved algorithm costs about 60% as much as the basic binary square-and-
multiply method. When memory is not an issue the binary algorithm can be
1
If is unitary and one can compute as
and as where

TEAM LinG
144 Michael Scott and Paulo S.L.M. Barreto

implemented by using windowing techniques, as described in [15]. However the
laddering algorithm proposed here for unitary elements will always be faster
than a conventional binary algorithm for a general element in
Note that this improvement is relevant not only for the second part of the
final exponentiation of the Tate pairing, but for any exponentiation directly
involving pairing values, as happens in many pairing-based protocols [5,17,28].


3.1 A Laddering Pairing Algorithm

For U, define to be the line through U and V. For all
the line function satisfies
Let and for let be a function with divisor
One can show that
up to a constant nonzero factor. This is called Miller™s for-
mula. In the computation of the Tate pairing for even and a careful
choice of P and Q (see [1, 3]), this formula can be simplified to

Let be the binary representation of By coupling Miller's simpli-
fied formula with Montgomery's scalar multiplication ladder, we get a laddering
version of the BKLS algorithm [1] to compute

Laddering BKLS algorithm to compute




Although this algorithm has no computational advantage over the original
BKLS, it may be useful in the same context of the laddering algorithms described
in [19].


4 Compressing Pairings to Half Length

Instead of keeping the full value of the Tate pairing, it may be possible
for cryptographic purposes to discard altogether, leaving the values defined
TEAM LinG
Compressed Pairings 145

only up to conjugation, which means one of the pairing arguments will only be
defined up to a sign:



This is similar to the point reduction technique, whereby instead of keeping
one only keeps the abscissa
Definition 1. The of an element is the sum of the conjugates
of
Notice that in effect discarding the
2
imaginary part. We define the compressed Tate pairing as .

4.1 Point Reduction
Point reduction is an optimization technique introduced by Miller in 1985 [25]. It
consists of basing cryptographic protocols solely on the coordinate of the points
involved rather than using both coordinates. This setting is possible because the
coordinate of any multiple of a given point P depends only on the coordinate
of P. A related but less efficient technique is that of point compression, which
consists of keeping not only the coordinate but also a single bit from the
coordinate to choose between the two roots
Some pairing-based cryptosystems have been originally defined to take profit
from point reduction. An example is the BLS signature scheme [6], where the
signature of a message represented by a curve point M under the signing key is
the coordinate of the point S = sM. This means that, implicitly, the actual
signature is ±S rather than S alone. To verify a BLS signature, the verifier checks
whether where the verification key is V = sQ. Incidentally,
the verification key itself can be reduced to its coordinate (say, even though
this possibility does not seem to have been considered by the authors of BLS.

4.2 Coupling Point Reduction with Compressed Pairings
Verifying a BLS signature involves computing a point from
a point from and checking whether or
Using the property that any pairing value is unitary
(and hence one can simply check whether
This is especially interesting, since a compressed pairing is precisely

An important aside is that exponentiation of compressed pairings must take
into account the fact that they are actually traces of full pairings. This means
one cannot exponentiate a pairing as if it were a simple value; rather, one
must always handle it as a Lucas sequence element.
2
Rubin and Silverberg [13] use traces to compress BLS signatures, but in an entirely
different manner, and with a compression factor much closer to 1.

TEAM LinG
146 Michael Scott and Paulo S.L.M. Barreto

5 A Ternary Exponentiation Ladder
Supersingular curves in characteristic 3 are a popular choice of underlying al-
gebraic structure for pairing-based cryptosystems, since many optimisations are
possible in such a setting [1, 11, 12]. Pairing compression is possible for those
systems, and we now propose a ternary ladder for Lucas sequences in charac-
teristic 3 that keeps the exponentiation cost in within about 33% of the
exponentiation cost in
Assume the sequence element index is written in signed ternary notation,
with At step (counting downwards from
to 0), we want to compute where Thus, by definition,

For we write down the formulas to compute
and




Similarly, for we write down the formulas to compute
and




In each case, the second and third relations constitute a simple linear system.
Solving them, we get these expressions for and




If and are precomputed, computing and one of
or involves two products and two cubes, and the computation
can be carried out using only and one of or We can
therefore keep track of which value between these two actually accompanies
and compute and at the cost of only 2 products and two
TEAM LinG
Compressed Pairings 147

cubes per step. Besides, since we are working in characteristic 3, the cost of
cubing is negligible compared to the cost of multiplying.
The binary ladder computes and at the cost of one squaring
and one product, or about 1.8 product, per step. However, the step count of
the ternary ladder is only about 1/ lg(3) of its binary counterpart, and hence
its total cost is about 70% of the binary ladder. We point out that the ternary
ladder can be used for plain exponentiation in characteristic 3 as an independent
technique, even in contexts where compressed pairings are not desired or not an
option.
A detailed ternary ladder algorithm is described in Appendix A.


6 Compressing Pairings to a Third of Their Length
Definition 2. The of an element is the value


The trace is for any and
When the elliptic curve has an embedding degree the Tate pairing
algorithm outputs an element of of order where divides but not
for Now Therefore the output
of the Tate pairing is an element of order which divides
For these are precisely the type of points considered in the
XTR public key scheme [21] (which is based on the ideas of [8]), and all of the
time/space optimizations that have been developed for this scheme [21,31] apply
here as well. In particular, we note that laddering algorithms again appear to be
optimal [31], and the Tate pairing output can be represented by its and
hence compressed by a factor of 3. Observe that the compressed value, being a
trace, must be implicitly exponentiated using the Lenstra-Verheul algorithm [21,
Algorithm 2.3.7] “ the trace value per se is not even a point of order
For supersingular curves in characteristic 3 we can do better than merely take
the trace “ rather, it is possible to do nearly all computations without resorting
to arithmetic any more complex than that on

6.1 Simpler Arithmetic for Pairing Computation in Characteristic 3
Let for some let and let be
elements satisfying and The modified Tate pairing
on the supersingular curve is the mapping
where is the distortion map

Duursma and Lee showed [11, Theorem 5] that the modified Tate pairing for
points and can be written as a product of factors of form
This expression can be rewritten as
where and Specifically, the Duursma-Lee
algorithm to compute is as follows (cf. [11, Algorithm 4]):
TEAM LinG
148 Michael Scott and Paulo S.L.M. Barreto

Duursma-Lee algorithm to compute




The output is an element We now show that this algorithm can
be modified to compute instead, by maintaining a ladder of three values
Since is initialized to 1, the initial ladder can be com-
puted from alone, namely, as one readily deduces
from the definition of
Theorem 1. Let for some and let satisfy
Then and
and hence
Proof. From it follows by induction that
so that
and
Moreover,
so that


At each step of the loop, we compute according to
the following theorem:
Theorem 2.




Proof. Using the of the trace and the defining property
Similarly,
we have

Finally,


Therefore, defining and using
the matrix A defined above, the modified algorithm to compute pairing traces
reads:




TEAM LinG
Compressed Pairings 149


A laddering algorithm to compute




However, to obtain a unique pairing value suitable for pairing-based protocols
we need rather than Let The
simplest (and seemingly the most efficient) way to do it is to recover from all
three components of
We use the of the trace and fact that is a basis of
with respect to i.e. any element can be written as
where . The trick is straightforward:
1.
2.

3.


Thus we recover from the pairing ladder essentially for free. Now one must
compute and then take the trace of This can be efficiently done
using the techniques described in [1, Appendix A.2], at a cost roughly equivalent
to a few extra steps of the laddering algorithm.
Each step of this laddering algorithm takes 17 multiplications. This com-
pares well with the original Duursma-Lee algorithm where each step takes 20
multiplications, and avoids arithmetic in the main loop.

6.2 Implicit Exponentiation in Characteristic 3

It is quite commonplace that the pairing value undergoes further exponentiation
as dictated by the underlying cryptographic protocol. We are thus confronted
with the task of computing given the value of The Lenstra-Verheul
algorithm [21, Algorithm 2.3.7] performs this task for characteristic
We now describe a variant tailored for characteristic 3.
Let and let with roots
One can show [21, Lemma 2.2.1] that, if is an element
of order dividing then the roots of are the
of Defining one can further show [21,
Lemmas 2.3.2 and 2.3.4] (see also [9]) that and
The proofs of these properties are independent of the field characteristic.
TEAM LinG
150 Michael Scott and Paulo S.L.M. Barreto

From the above properties, one easily deduces the following relations that
hold in characteristic 3:




Computing takes two multiplications, takes four multiplications,
and takes six multiplications.
Define Using the above formulas,
one can compute any one of or from at the
cost of 12 multiplications:




From the definition of it is clear that if Hence,
if then The total cost of
this algorithm, about 7.6 lg multiplications, matches the complexity of the
ternary ladder introduced in section 5 for exponentiation. Appendix B
lists this algorithm in detail. We point out that this ternary ladder can also be
the basis of a characteristic 3 variant of the XTR cryptosystem.

6.3 Coupling Pairing Compression with Point Reduction
A nice feature of this algorithm is that it is compatible with a variant of the
point reduction technique.
The conventional approach to compress a point is to keep only
and a single bit of point reduction discards altogether. In characteristic 3, it
is more advantageous to discard instead, keeping and a trit of to distinguish
among the solutions of the curve equation alternatively,
one can reduce R by keeping only and modifying the cryptographic protocols
to allow for any of the three points and that share the same Thus,
we will show that the input to the laddering algorithm of section 6.1 can be only
(or the corresponding (or can be easily recovered except for a trit,
and the actual choice of this trit does not affect the compressed pairing value.
Let where for odd and assume the order of divides
The conjugates of are and or equivalently
and since and The trace
of is the sum of the conjugates, [21]. Consider the
super singular elliptic curve E : whose order is [23,
TEAM LinG
Compressed Pairings 151

section 5.2.2] where is the
trace of the Frobenius.
Let and let be a linearly independent
point. The conjugates of are and
The following property holds:

Lemma 1. If points P, and “qP share precisely the same
coordinate.

Proof. Let A simple inspection of the group law for characteristic 3 [1]
reveals that and hence Thus

for any
where we used the fact that Similarly,


We see that, for (mod 3), the coordinates of and
are the three solutions to which are exactly
Obviously, the traces of the pairings computed from the conjugates of P are all
equal, since is simply the sum of the conjugates of Thus,
the actual solution to the curve equation above used to compute is
irrelevant. Also, computing from is very efficient, since it amounts to solving
a linear system (see appendix C).


7 Conclusions
We have introduced the notion of compressed pairings, and suggested how they
can be realised as traces of ordinary Tate pairings. We also described how com-
pressed pairings can be computed and implicitly exponentiated by means of
laddering algorithms, with a compression ratio of 1/2 in characteristic
and 1/3 in characteristic 3; our algorithms thus reduce bandwidth requirements
without impairing performance. Finally, we showed how to couple compressed
pairings with the technique of point compression or point reduction. As a side
result, we proposed an efficient laddering algorithm for plain exponentitation in
characteristic 3, which can be used even in contexts where compressed pairings
are not desired.
Our work constitutes evidence that the security of pairing-based cryptosys-
tems is linked to the security of the Lucas/XTR schemes, and gives further
motivation for the approach of Galbraith et al. regarding the use of traces to
prevent security losses.
We leave it as an open problem to find a method to compute pairings directly
in compressed form when the compression ratio is 1/3 or better on ordinary
(non-supersingular) curves in characteristic




TEAM LinG
152 Michael Scott and Paulo S.L.M. Barreto

Acknowledgements
We are grateful to Steven Galbraith, Robert Granger, and Waldyr Benits Jr.
for their valuable comments during the preparation of this work, and to the
anonymous referees for their improvement suggestions.


References
1. P. S. L. M. Barreto, H. Y. Kim, B. Lynn, and M. Scott. Efficient algorithms for
pairing-based cryptosystems. In Advances in Cryptology “ Crypto™2002, volume
2442 of Lecture Notes in Computer Science, pages 354“368, Santa Barbara, USA,
2002. Springer-Verlag.
2. P. S. L. M. Barreto, B. Lynn, and M. Scott. Constructing elliptic curves with pre-
scribed embedding degrees. In Security in Communication Networks “ SCN™2002,
volume 2576 of Lecture Notes in Computer Science, pages 263“273, Amalfi, Italy,
2002. Springer-Verlag.
3. P. S. L. M. Barreto, B. Lynn, and M. Scott. On the selection of pairing-friendly
groups. In Selected Areas in Cryptography “ SAC™2003, Ottawa, Canada, 2003. to
appear.
4. D. Bleichenbacher, W. Bosma, and A. K. Lenstra. Some remarks on lucas-based
cryptosystems. In Advances in Cryptology “ Crypto ™95, volume 963 of Lecture Notes
in Computer Science, pages 386“396, Santa Barbara, USA, 1995. Springer-Verlag.
5. D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. SIAM
Journal of Computing, 32(3):586“615, 2003.
6. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In
Advances in Cryptology “ Asiacrypt™2001, volume 2248 of Lecture Notes in Com-
puter Science, pages 514“532, Gold Coast, Australia, 2002. Springer-Verlag.
7. F. Brezing and A. Weng. Elliptic curves suitable for pairing based cryptog-
raphy. Cryptology ePrint Archive, Report 2003/143, 2003. Available from
http://eprint.iacr.org/2003/143.
8. A. E. Brouwer, R. Pellikaan, and E. R. Verheul. Doing more with fewer bits. In
Advances in Cryptology “ Asiacrypt™99, volume 1716 of Lecture Notes in Computer
Science, pages 321“332, Singapore, 1999. Springer-Verlag.
9. L. Carlitz. Recurrences of the third order and related combinatorial identities.
Fibonacci Quarterly, 16(1): 11“18, 1978.
10. R. Dupont, A. Enge, and F. Morain. Building curves with arbitrary small MOV
degree over finite prime fields. Cryptology ePrint Archive, Report 2002/094, 2002.
Available from http://eprint.iacr.org/2002/094.
11. I. Duursma and H.-S. Lee. Tate pairing implementation for hyperelliptic curves
In Advances in Cryptology “ Asiacrypt™2003, volume 2894 of Lecture
Notes in Computer Science, pages 111“123, Taipei, Taiwan, 2003. Springer-Verlag.
12. S. Galbraith, K. Harrison, and D. Soldera. Implementing the Tate pairing. In
Algorithmic Number Theory Symposium “ ANTS V, volume 2369 of Lecture Notes
in Computer Science, pages 324“337, Sydney, Australia, 2002. Springer-Verlag.
13. S. Galbraith, K. Harrison, and D. Soldera. Using primitive subgroups to do more
with fewer bits. In Algorithmic Number Theory Symposium “ ANTS VI, volume
3076 of Lecture Notes in Computer Science, pages 18“41, Annapolis, USA, 2004.
Springer-Verlag.

TEAM LinG
Compressed Pairings 153

14. S. Galbraith, H. Hopkins, and I. Shparlinski. Secure bilinear diffie-hellman
bits. Cryptology ePrint Archive, Report 2002/155, 2002. Available from http:
//eprint.iacr.org/2002/155.
15. D. Gordon. A survey of fast exponentiation methods. Journal of Algorithms,
27:129“146, 2002.
16. K. Hoffman and R. Kunze. Linear Algebra. Prentice Hall, New Jersey, USA, 2nd
edition, 1971.
17. A. Joux. A one-round protocol for tripartite Diffie-Hellman. In Algorithmic Num-
ber Theory Symposium “ ANTS IV, volume 1838 of Lecture Notes in Computer
Science, pages 385“394, Leiden, The Netherlands, 2000. Springer-Verlag.
18. M. Joye and J. J. Quisquater. Efficient computation of full Lucas sequences. Elec-
tronics Letters, 32(6):537“538, 1996.
19. M. Joye and S. Yen. The montgomery powering ladder. In Cryptographic Hardware
and Embedded Systems - CHES™2002, volume 2523 of Lecture Notes in Computer
Science, pages 291“302, Berlin, Germany, 2003. Springer-Verlag.
20. D. H. Lehmer. Computer technology applied to the theory of numbers. In W. J.
LeVeque, editor, Studies in Number Theory, volume 6 of MAA Studies in Mathe-
matics, pages 117“151. Math. Assoc. Amer. (distributed by Prentice-Hall, Engle-
wood Cliffs, N.J.), 1969.
21. A. K. Lenstra and E. R. Verheul. The xtr public key system. In Advances in
Cryptology “ Crypto™2000, volume 1880 of Lecture Notes in Computer Science,
pages 1“19, Santa Barbara, USA, 2000. Springer-Verlag.
22. R. Lidl and H. Niederreiter. Finite Fields. Number 20 in Encyclopedia of Math-
ematics and its Applications. Cambridge University Press, Cambridge, UK, 2nd
edition, 1997.
23. A. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publish-
ers, 1993.
24. V. S. Miller. Short programs for functions on curves. Unpublished manuscript,
1986. Available from http://crypto.stanford.edu/miller/miller.pdf.
25. V. S. Miller. Use of elliptic curves in cryptography. In Advances in Cryptology
“ Crypto™85, volume 218 of Lecture Notes in Computer Science, pages 417“426,
Santa Barbara, USA, 1986. Springer-Verlag.
26. A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve
traces for FR-reduction. IEICE Transactions on Fundamentals, E84-A(5):1234“
1243, 2001.
27. P. L. Montgomery. Speeding the pollard and elliptic curve methods of factorization.
Mathematics of Computation, 48(177):243“264, 1987.
28. D. Nalla and K. C. Reddy. Signcryption scheme for identity-based cryptosys-
tems. Cryptology ePrint Archive, Report 2003/066, 2002. Available from http:
//eprint.iacr.org/2003/066.
29. J. H. Silverman. The Arithmetic of Elliptic Curves. Number 106 in Graduate
Texts in Mathematics. Springer-Verlag, Berlin, Germany, 1986.
30. N. P. Smart. An identity based authenticated key agreement protocol based on
the weil pairing. Electronics Letters, 38:630“632, 2002.
31. M. Stam and A. K. Lenstra. Speeding up XTR. In Advances in Cryptology “
Asiacrypt™2001, volume 2248 of Lecture Notes in Computer Science, pages 125“
143, Gold Coast, Australia, 2001. Springer-Verlag.
32. S. M. Yen and C. S. Laih. Fast algorithms for LUC digital signature computation.
IEE Proceedings on Computers and Digital Techniques, 142(2):165“169, 1995.

TEAM LinG
154 Michael Scott and Paulo S.L.M. Barreto

A Computation of Lucas Sequence Elements

The Lucas sequence for some field element P is defined by the following
recurrence relations:



Let be an integer in binary representation, with The
Lucas sequence element can be computed as:




Let be the signed ternary representation of The
Lucas sequence element in characteristic 3 (as needed for the implicit
exponentiation of of values) can be computed using the following
algorithm:



<<

. 5
( 19)



>>