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: