# Speeding Up the Fixed-Base Comb Method for Faster Scalar Multiplication on Koblitz Curves

Christian Hanser, Christian Wagner

► To cite this version:

Christian Hanser, Christian Wagner. Speeding Up the Fixed-Base Comb Method for Faster Scalar Multiplication on Koblitz Curves. 1st Cross-Domain Conference and Workshop on Availability, Reliability, and Security in Information Systems (CD-ARES), Sep 2013, Regensburg, Germany. pp.168-179. hal-01506561

HAL Id: hal-01506561

https://inria.hal.science/hal-01506561

Submitted on 12 Apr 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Speeding Up the Fixed-Base Comb Method for Faster Scalar Multiplication on Koblitz Curves

Christian Hanser and Christian Wagner

Institute for Applied Information Processing and Communications (IAIK),
Graz University of Technology (TUG), Inffeldgasse 16a, 8010 Graz, Austria
{christian.hanser|christian.wagner@iaik.tugraz.at}

**Abstract.** Scalar multiplication is the most expensive arithmetical operation on elliptic curves. There are various methods available, which are optimized for different settings, such as high speed, side-channel resistance and small memory footprint. One of the fastest methods for fixed-base scalar multiplications is the so-called fixed-base comb scalar multiplication method, which is due to Lim and Lee. In this paper, we present a modification to this method, which exploits the possibility of exchanging doublings for much cheaper applications of the Frobenius endomorphism on binary Koblitz curves. We have implemented the findings in software and compare the performance of the implementation to the performance of the reference WTNAF implementation and the performance of the conventional comb multiplication methods. For single scalar multiplications, we are able to achieve performance improvements over the WTNAF method of up to 25% and of up to 42% over the conventional comb methods. Finally, we emphasize that the implementation of the τ-comb method is straight-forward and requires only little effort. All in all, this makes it a good alternative to other fixed-base multiplication methods.

**Keywords:** ECC, scalar multiplication, Lim-Lee method, comb method, Koblitz curves, Frobenius endomorphism, τ-adic representation

## 1 Introduction

In 1985, Neal Koblitz [8] and Victor S. Miller [14] both discovered independently that elliptic curves over finite fields can be used for public key cryptography. By now, elliptic curves have become an important concept within public key cryptography. This is mainly due to small key sizes compared to other public key cryptosystems, such as RSA, which lower the requirements for CPUs as well as the memory footprint. Elliptic curves have a group structure and their cryptographic security relies on the difficulty of solving the elliptic curve discrete logarithm problem (ECDLP).

The most expensive, yet, at the same time most important operation, on elliptic curves is the scalar multiplication. There are plenty of different techniques achieving optimizations for different settings, such as high speed through the
reduction of group operations, side-channel resistance and small memory footprint. In this paper we are focusing solely on the performance aspects of scalar multiplication. Koblitz curves allow trading the doubling operation for another operation, that is, the application of the so-called Frobenius endomorphism, which is inexpensive compared to point doubling. In the context of Koblitz curves, many multiplication methods relying on a non-adjacent form (NAF), such as windowed non-adjacent form (WNAF), interleaved simultaneous point multiplication, etc., have been adapted, so that doublings can be replaced by far more efficient applications of the Frobenius endomorphism. Yet, to the best of our knowledge, no such modification to the fixed-base comb method, which is also referred to as Lim-Lee method [10], has been proposed until now. This algorithm achieves very high speed at the cost of precomputations and increased memory usage due to lookup tables.

## 1.1 Contribution

In this paper, we are going to introduce an improvement of the fixed-base comb method on Koblitz curves. In this context, we show how point doublings can be traded for applications of the Frobenius endomorphism. To do so, we use scalar recoding to obtain an unsigned $\tau$-adic representation of scalars, which allows us to exchange the doubling steps within the comb methods for the application of the Frobenius endomorphism. We detail the scalar recoding algorithm and describe the modified fixed-base comb method. Furthermore, we have implemented this method as well as the WTNAF method in software. We give a detailed performance comparison and illustrate the performance gains we have achieved with respect to the WTNAF and the conventional fixed-base comb methods. In the former case, we achieve performance improvements of up to 25% and in the latter case improvements of up to 42%.

## 1.2 Outline

In Section 2, we are going to talk about elliptic curves in general, binary Koblitz curves and the fixed-base comb multiplication methods. Section 3 discusses the improvements we have achieved and Section 4 details the implementation, presents the benchmark results and compares the findings to the conventional comb multiplier variants. At last, Section 5 concludes the paper.

# 2 Preliminaries

An elliptic curve over a field $K$ is a plane, smooth curve described by the Weierstrass equation:

$$E: Y^2 + a_1XY + a_2Y = X^3 + a_3X^2 + a_4X + a_6, \quad (1)$$

where $a_1, a_2, a_3, a_4, a_6 \in K$. The set $E(K)$ of points $(x, y) \in K^2$ satisfying Equation (1) plus the point at infinity $O = (0:1:0)$, which is the neutral element,
forms an additive Abelian group. The addition of points on an elliptic curve is achieved using the chord-and-tangent method [17].

For cryptographic purposes, one is interested in elliptic curves over finite fields $\mathbb{F}_q$, especially in curves over fields $\mathbb{F}_{2^m}$ with $m$ being prime and $\mathbb{F}_p$ with $p$ being a large prime number. The security of elliptic curve cryptography is based on the assumption that in general there is no subexponential-time algorithm to solve the discrete logarithm problem in elliptic curve groups (ECDLP). Given $P, Q \in E(\mathbb{F}_q)$ with $P$ being a generator of a subgroup of $E(\mathbb{F}_q)$ of large prime order $n$, the ECDLP constitutes the problem of finding a scalar $k \in \mathbb{Z}_n$ such that $Q = k \cdot P$. In the following, we use $E(\mathbb{F}_q)[n]$ to denote this $n$-order subgroup of $E(\mathbb{F}_q)$.

In cryptography, we usually use non-supersingular curves, as supersingular curves turned out to be susceptible to the MOV attack [13], which reduces the ECDLP to the DLP on finite fields for which an efficient subexponential-time algorithm is known. Non-supersingular curves defined over $\mathbb{F}_{2^m}$, are described using the following short form of Equation (1):

$$Y^2 + XY = X^3 + a_2X^2 + a_6, \qquad (2)$$

where $a_2, a_6 \in \mathbb{F}_{2^m}$ and $a_6 \neq 0$.

The most important and at the same time most expensive operation on elliptic curves is the scalar multiplication, that is, computing $k \cdot P$ from some point $P \in E(\mathbb{F}_q)$ and some scalar $k \in \mathbb{Z}_n$. For this purpose, many different algorithms for different goals, such as small or even constant memory footprint, high speed or side-channel resistance, have been invented.

Basic algorithms for scalar multiplication are the double-and-add and the NAF method. In the former case, one is given an unsigned binary representation of the scalar and per bit of the scalar a doubling is performed, where for bits set to 1 an additional point addition is carried out. In the latter, the unsigned scalar representation is replaced by a signed representation, i.e., bits can now take values in $\{0, \pm 1\}$, where for negative bit values point subtractions instead of additions have to be performed. This way, the Hamming weight of the scalar can be reduced to 1/3, which gives a major speedup by reducing the number of additions. Further speed-ups can be achieved by reducing the number of additions, which is done by the windowed-NAF (WNAF) method at the expense of some precomputations (cf. [6, 4]).

Subsequently, we are dealing with so-called fixed-base comb multipliers, which are very fast methods for multiplications with some fixed-point $P$ (mostly a fixed generator of $E(\mathbb{F}_q)[n]$), and with scalar multiplications on Koblitz curves, for which enormous speed improvements exist already.

## 2.1 Fixed-Base Comb Multiplication

The fixed-base comb multiplier is due to Lim and Lee [10] and is one of the fastest scalar multiplication methods available. As it requires intense precomputations, it is only used for multiplications with a fixed point, which is in most cases a generator of an elliptic curve (sub-)group.
In the fixed-base comb method, the bit representation of a scalar k of maximum bitsize t (where t is the curve's group order in bits) is prepended with 0s, such that the length of k is a multiple of the window size w and then split into w blocks $K_i$ with $0 \le i < w$ of size $d = \lceil t/w \rceil$, so that

$$k = K_{w-1} \Vert \cdots \Vert K_1 \Vert K_0.$$

Each bitstring $K_i$ represents one row of a binary matrix with w rows and d columns:

$$\begin{bmatrix} K_0 \\ \vdots \\ K_i \\ \vdots \\ K_{w-1} \end{bmatrix} = \begin{bmatrix} K_{0,d-1} \cdots K_{0,0} \\ \vdots \\ K_{i,d-1} \cdots K_{i,0} \\ \vdots \\ K_{w-1,d-1} \cdots K_{w-1,0} \end{bmatrix} = \begin{bmatrix} k_{d-1} \cdots k_0 \\ \vdots \\ k_{(i+1)d-1} \cdots k_{id} \\ \vdots \\ k_{wd-1} \cdots k_{(w-1)d} \end{bmatrix} \quad (3)$$

Here, $K_{j,i}$ denotes the i-th bit of the bitstring $K_j$ and $k_i$ denotes the i-th bit of the unsigned binary representation of the scalar k. The columns of this matrix are then processed one at a time. By precomputing the points

$$[a_{w-1}, \dots, a_2, a_1, a_0]_2 P = a_{w-1} 2^{(w-1)d} P + \dots + a_2 2^{2d} P + a_1 2^d P + a_0 P,$$

for all possible bitstrings $(a_{w-1}, \dots, a_1, a_0)$ the actual computation can be accelerated. This method is summarized in Algorithm 1. The *Multiply* step of

**Algorithm 1 Fixed-base comb method ([10, 6])**

*Precompute:*

**Input:** Window width $w$, $d = \lceil t/w \rceil$, $P \in E(\mathbb{F}_q)$.

**Output:** Table T holding $[a_{w-1}, \dots, a_0]_2 P$ for all length $w$ bitstrings $(a_{w-1}, \dots, a_0)$.

*Multiply:*

**Input:** Window width $w$, $d = \lceil t/w \rceil$, $k = (k_{t-1}, \dots, k_1, k_0)_2$, lookup table T generated via *Precompute* with respect to $P \in E(\mathbb{F}_q)$.

**Output:** $kP$.

1: If necessary, pad $k$ on the left with 0s, interpret $k$ as $K_{w-1} \Vert \cdots \Vert K_1 \Vert K_0$, where each $K_j$ is a length $d$ bitstring, where $K_{j,i}$ denotes the i-th bit of $K_j$.

2: $Q = O$.

3: **for** $i = d-1$ **downto** 0 **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $Q = 2Q$

5: &nbsp;&nbsp;&nbsp;&nbsp; $Q = Q + [K_{w-1,i}, \dots, K_{1,i}, K_{0,i}]_2 P = Q + T_{\sum_{j=0}^{w-1} K_{j,i} 2^j}$

6: **end for**

7: **return** $Q$
Algorithm 1 has an expected running time of

$$ \left( \frac{2^w - 1}{2^w} d - 1 \right) \mathbf{A} + (d - 1)\mathbf{D}, \qquad (4) $$

where A and D stand for the costs of a (mixed) point addition and a point doubling, respectively. Inside the main loop, the fixed-base comb method has the same number of point additions and point doublings. To reduce the number of point doublings by half, the so-called fixed-base comb method with two tables has been introduced, which makes use of an additional table of the same size as the first table. This method gives a benefit over the conventional comb method whenever w is chosen such that

$$ \frac{2^{w-1}(w-2)}{2^w - w - 1} \geq \frac{\mathbf{A}}{\mathbf{D}}, \qquad (5) $$

For instance, in case of López-Dahab coordinates, $w \geq 6$ must hold for the two-table comb method to be faster than the comb method, since $A/D \approx 2$ [6].

## 2.2 Koblitz Curves

Binary Koblitz curves are defined by Equation (2), where the curve equation is defined over $\mathbb{F}_2$, that is $a_2 \in \{0, 1\}$ and $a_6 = 1$. The group of these curves is defined over $\mathbb{F}_{2^m}$ with $m$ prime. For cryptographic purposes, $E(\mathbb{F}_{2^m})$ is required to have almost prime group order, meaning that $E(\mathbb{F}_{2^m}) = hn$, where $n$ is a large prime and the cofactor $h \leq 4$.

On Koblitz curves, the map $\tau : E(\mathbb{F}_{2^m}) \to E(\mathbb{F}_{2^m})$ with:

$$ P \mapsto \begin{cases} (x^2, y^2) & \text{if } P = (x, y), \text{ and} \\ \mathcal{O} & \text{if } P = \mathcal{O}, \end{cases} $$

is an endomorphism, which is called Frobenius endomorphism. It can be used to achieve tremendous speedups for scalar multiplications on this curve type. Note that all of the remaining techniques in this section are being discussed in detail by Solinas [18].

The characteristic polynomial of $\tau$ is $\tau^2 - \mu\tau + 2$ with $\mu = (-1)^{1-a_2}$. Thus, the relation $2P = \mu\tau(P) - \tau^2(P)$ holds for all $P \in E(\mathbb{F}_{2^m})$. Since squaring is inexpensive in binary fields, the costs of applying $\tau$ are insignificant compared to other operations, such as point doubling, which suggests trading point doublings for applications of $\tau$ within multiplications by some scalar $k$. This way, one can trade 3M + 5S required for a doubling on Koblitz curves in López-Dahab coordinates ([9, 4, 7]) for 3S required for one evaluation of $\tau$, where M stands for the costs of one multiplication and S for the costs of one squaring. However, to be able to do so, $k$ needs to be converted to a value $k' = \sum_{i=0}^{l-1} u_i \tau^i \in \mathbb{Z}[\tau]$, which is said to be in $\tau$-adic representation.
**The τ-adic Representation:** Now, in order to convert scalars from base 2 to base $\tau$, we need to introduce the norm function on $\mathbb{Z}[\tau]$. The norm of an element $\alpha = a_0 + a_1\tau \in \mathbb{Z}[\tau]$ (note that every element of $\mathbb{Z}[\tau]$ can be written this way) is the integer product of $\alpha$ and its complex conjugate $\bar{\alpha} = a_0 + a_1\bar{\tau} \in \mathbb{Z}[\tau]$, i.e., $N: \mathbb{Z}[\tau] \to \mathbb{Z}$ with $N(a_0 + a_1\tau) = a_0^2 + \mu a_0 a_1 + 2a_1^2$. The ring $\mathbb{Z}[\tau]$ is Euclidean with respect to $N(\cdot)$, i.e., it is possible to perform division with remainder in $\mathbb{Z}[\tau]$ so that the norm of the remainder is smaller than the norm of the divisor. In particular, an element $\alpha = a_0 + a_1\tau \in \mathbb{Z}[\tau]$ is divisible by $\tau$ if and only if $a_0$ is even. If so, then $\alpha/\tau = (a_1 + \mu a_0/2) - (a_0/2)\tau$. Note that this also enables us to repeatedly divide $k \in \mathbb{Z}$ by $\tau$, which is necessary to derive the $\tau$-adic representation $k' = \sum_{i=0}^{l-1} u_i \tau^i$ of a scalar $k$. As $N(\tau) = 2$, the remainder in the $i$-th division $u_i$ is either an element of $\{0, \pm 1\}$ in case of signed representations or an element of $\{0, 1\}$ in case of unsigned representations.

So far, there is, however, one problem with this representation, namely, the length of the resulting $\tau$-adic representation is twice the length of the corresponding base 2 representation. In case of the NAF, this means that replacing NAF($k$) by the $\tau$-adic NAF (also known as TNAF) will eliminate one doubling for two applications of $\tau$, but will double the number of additions in the scalar multiplication method. To overcome this problem, Solinas introduced the reduced $\tau$-adic NAF in [18], leading to a $\tau$-adic NAF representation half the length of the original representation and, therefore, of roughly the size of an ordinary NAF representation. Here, an element $\rho \in \mathbb{Z}[\tau]$ of smallest possible norm so that $\rho \equiv k \pmod \delta$ with $\delta = \frac{\tau^m-1}{\tau-1}$ is computed. Then, for all points $P \in E(\mathbb{F}_{2^m})[n]$ it holds that $kP = \rho P$. From the resulting value $\rho$, the TNAF representation TNAF($\rho$) is derived, where the length of TNAF($\rho$) is bounded by $m + a_2$.

In practice, often a partial reduction (cf. [18]) is being performed in order to avoid multiprecision integer divisions. Here, one computes an element $\rho' \in \mathbb{Z}[\tau]$ that is congruent to $k$ modulo $\delta$, but does not necessarily have the smallest possible norm. After the partial reduction, the length of TNAF($\rho'$) is bounded by $m + a_2 + 3$ and is, in general, the same as the length of TNAF($\rho$).

**The Windowed τ-adic NAF Method:** The windowed $\tau$-adic NAF or WT-NAF method is the $\tau$-adic analogue of the ordinary width-$w$ NAF (WNAF). The goal of this method, is to replace doublings by evaluations of the map $\tau$ and at the same time to reduce the number of additions through windowing. We do not discuss this method in detail here, but refer the reader to [6, 18].

As with the WNAF, a representation of the scalar, having at most one nonzero coefficient among $w$ consecutive coefficients, is derived. Like before, a scalar $k \in \mathbb{Z}$ is (partially) reduced modulo $\delta = \frac{\tau^m-1}{\tau-1}$, and thereby an element $\rho \in \mathbb{Z}[\tau]$ is obtained. For $w > 1$, $\rho$ can be expressed in the form $\rho = \sum_{i=0}^{l-1} u_i \tau^i$ where $u_{l-1} \neq 0$ and $u_i \in \{0\} \cup \{\pm\alpha_u : \alpha_u \in \pi\}$ with $\pi = \{\alpha_u \equiv u \pmod{\tau^w} : u = 1, 3, \dots, 2^{w-1} - 1\}$. Thus, the number of additions in the multiplication step is reduced in favor of the precomputation of the points $\alpha_u P$ for $\alpha_u \in \pi$. As in case of the fixed-base comb methods, these points can be computed beforehand for points known a priori, such as generators. In this case, the WTNAF method
has the following expected costs:

$$ \frac{l}{w+1} \mathbf{A} + l\mathbf{T}, \qquad (6) $$

where $\mathbf{T}$ denotes the cost of one evaluation of $\tau$.

## 3 Fixed-base Comb Method on Koblitz Curves

We now show how the fixed-base comb multiplier can be modified to take advantage of the Frobenius endomorphism on Koblitz curves, i.e., how in this context doublings can be traded for evaluations of the map $\tau$. Subsequently, we refer to this method as fixed-base $\tau$-comb method. Both the precomputation and multiplication step benefit tremendously from this measure. See Section 4 for more details on the achieved performance improvements.

In order to combine the advantages of Koblitz curves with the fast fixed-based comb method, the scalar representation has to be modified. Obviously, it is necessary to obtain an unsigned $\tau$-adic representation of scalar $k$, that is $k = \sum_{i=0}^{l-1} u_i \tau^i$, with $u_i \in \{0, 1\}$. This representation can be obtained with a small modification to the TNAF algorithm specified by Solinas in [18], which is summarized in Algorithm 2, where we only allow $u_i$ to be 1 in Step 4. As with TNAF, the size of this representation is approximately twice the size of the ordinary binary representation. This is why we need to perform a reduction by $\delta = \frac{\tau^m - 1}{\tau - 1}$ beforehand, in order to reduce the size of the resulting representation. As we have obtained an unsigned $\tau$-adic scalar representation, the doublings in

<caption>**Algorithm 2 Computing the unsigned $\tau$-adic representation**</caption>

Input: $\kappa = r_0 + r_1\tau \in \mathbb{Z}[\tau]$
Output: $\kappa$ represented as bitstring $u = (u_{t-1}, \dots, u_1, u_0)_\tau$.
1: $i = 0$
2: while $(r_0 \neq 0 \lor r_1 \neq 0)$ do
3: if $r_0 \equiv 1 \mod 2$ then
4: $u_i = 1$, $r_0 = r_0 - 1$
5: else
6: $u_i = 0$
7: end if
8: $tmp = r_0$, $r_0 = \mu r_0$, $r_0 = r_1 + r_0/2$, $r_1 = -tmp/2$
9: $i = i + 1$
10: end while
11: return $(u_{i-1}, u_{i-2}, \dots, u_1, u_0)$

the precomputation need to be replaced by evaluations of $\tau$, i.e.,

$$ [a_{w-1}, \dots, a_2, a_1, a_0]_\tau P = a_{w-1}\tau^{(w-1)d}(P) + \dots + a_2\tau^{2d}(P) + a_1\tau^d(P) + a_0P. $$
Algorithm 3 shows the fixed-base $\tau$-comb multiplier, where doublings are replaced by evaluations of the Frobenius endomorphism $\tau$.

We note that due to the small costs for $\tau$, the right hand-side of Equation (5) gets large, and, thus, the two-table $\tau$-comb method does not give an advantage over Algorithm 3 for window sizes used in practice.

**Algorithm 3 Fixed-base comb method on Koblitz curves**

Precompute:

Input: Window width $w$, $d = \lceil t/w \rceil$, $P \in E(\mathbb{F}_q)$.

Output: Table $T$ holding $[a_{w-1}, \dots, a_0]_\tau P$ for all length $w$ bitstrings $(a_{w-1}, \dots, a_0)$.

Multiply:

Input: Window width $w$, $d = \lceil t/w \rceil$, $k = (k_{t-1}, \dots, k_1, k_0)_\tau$, lookup table $T$ generated via Precompute with respect to $P \in E(\mathbb{F}_q)$.

Output: $kP$.

1: If necessary, pad $k$ on the left with 0s, interpret $k$ as $K_{w-1} \Vert \cdots \Vert K_1 \Vert K_0$, where each $K_j$ is a length $d$ bitstring, where $K_{j,i}$ denotes the $i$-th bit of $K_j$.

2: $Q = O$.

3: **for** $i = d-1$ **downto** 0 **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $Q = \tau Q$

5: &nbsp;&nbsp;&nbsp;&nbsp; $Q = Q + [K_{w-1,i}, \dots, K_{1,i}, K_{0,i}]_\tau P = Q + T_{\sum_{j=0}^{w-1} K_{j,i} 2^j}$

6: **end for**

7: **return** $Q$

# 4 Implementation Results

In this section, we are detailing the implementation of the $\tau$-comb multiplication algorithm and contrast its performance to the reference implementations of the WTNAF method and the conventional comb method.

## 4.1 Implementation Details

We have implemented the NIST-recommended elliptic curves K-163, K-233, K-283, K-409 and K-571 [5] in Java. We are using fast reductions for the underlying binary fields and long-arrays for values thereof, which are in polynomial representation. We perform squarings in linear time complexity using table lookups [16] and multiplications using the windowed left-to-right comb multiplier, which works with precomputed multiplication lookup tables and is also due to Lim and Lee (cf. [12, 6]). For field multiplications, we use windows of size $w = 4$ and cache these lookup tables for recurring intermediate values in the addition/doubling formulas. Furthermore, we use partial reductions to derive the unsigned $\tau$-adic representations (see Section 2.2).

We use López-Dahab coordinates [11] with the fast formulas given by Lange and Doche in [9, 4] as well as Higuchi and Takagi in [7] and perform mixed
additions in all implementations. Using this coordinate type, mixed additions take 8M + 5S, where the multiplication lookup tables for two intermediate values can be used twice, lowering the costs to 6M + 2m + 5S. The evaluation of τ takes 3S and point doublings take 3M + 5S, which are necessary for the conventional comb methods.

Finally, we emphasize that the implementation of the τ-comb method is straight-forward and requires only little effort, which makes it a good alternative to other fixed-base multiplication methods.

## 4.2 Estimated Costs and Timings

Here, we present rough estimates for the scalar multiplication costs of the discussed scalar multiplication algorithms and the corresponding timings of our software implementations. As test platform served an Intel Core i5-2540M running Ubuntu Linux 12.10/amd64 and OpenJDK 7u15/amd64 in server mode.

Table 1 lists the costs of squarings and multiplications with already pre-computed lookup tables in relation to the costs of multiplications on the test platform. Thus, on the test platform, we get at most A = 8.2M, D = 3.5M and T = 0.3M per mixed addition, per doubling and per evaluation of τ, respectively.

<table><caption>Table 1: Costs of squarings in relation to multiplications, where S denotes the cost of one squaring, M the cost of a multiplication and m the cost of a multiplication using cached precomputation tables of window size w = 4.</caption><thead><tr><th></th><th>F<sub>2163</sub></th><th>F<sub>2233</sub></th><th>F<sub>2283</sub></th><th>F<sub>2409</sub></th><th>F<sub>2571</sub></th></tr></thead><tbody><tr><td>1S =</td><td>0.094M</td><td>0.080M</td><td>0.077M</td><td>0.061M</td><td>0.055M</td></tr><tr><td>1m =</td><td>0.643M</td><td>0.717M</td><td>0.761M</td><td>0.829M</td><td>0.939M</td></tr></tbody></table>

In the following, we give some rough estimates of point multiplication costs of the WTNAF and the τ-comb method based on the relative costs given in Table 1. So, for instance, on curve K-233 with w = 7 the WTNAF method has expected costs of 284.09M, whereas the τ-comb method has expected costs of 264.36M giving an advantage of 7.46%. For w = 8, the expected runtime of the WTNAF method on K-283 is 314.00M, whereas the τ-comb method requires only 283.72M resulting in a performance gain of 10.67%. For w = 9 and curve K-233, we have 238.45M compared to 201.45M resulting in a speed-up of 18.37% and on curve K-409 with w = 9 we get 400.53M compared to 365.85M giving a speed-up of 9.48%.

Table 2 compares the timings of one fixed-base scalar multiplication of the τ-comb method with the WTNAF method and the conventional comb method. As Table 2 shows, in the former case, we achieve performance improvements of up to 25% and in the latter case improvements of up to 42%.
<table><caption>Table 2: Comparison of the multiplication timings of the comb, the τ-comb and the WTNAF methods.</caption><thead><tr><th>Curve</th><th>Window size</th><th>Comb [µs]</th><th>τ-Comb [µs]</th><th>WTNAF [µs]</th><th>Speedup w.r.t Comb</th><th>Speedup w.r.t WTNAF</th></tr></thead><tbody><tr><td rowspan="4">K-163</td><td>w=6</td><td>276.50</td><td>209.06</td><td>241.77</td><td>1.32x</td><td>1.16x</td></tr><tr><td>w=7</td><td>237.03</td><td>196.51</td><td>208.73</td><td>1.21x</td><td>1.06x</td></tr><tr><td>w=8</td><td>211.65</td><td>168.13</td><td>194.55</td><td>1.26x</td><td>1.16x</td></tr><tr><td>w=9</td><td>192.83</td><td>152.97</td><td>187.38</td><td>1.26x</td><td>1.22x</td></tr><tr><td rowspan="4">K-233</td><td>w=6</td><td>511.96</td><td>398.87</td><td>405.49</td><td>1.28x</td><td>1.02x</td></tr><tr><td>w=7</td><td>455.76</td><td>341.16</td><td>386.22</td><td>1.34x</td><td>1.13x</td></tr><tr><td>w=8</td><td>383.59</td><td>299.29</td><td>356.87</td><td>1.28x</td><td>1.19x</td></tr><tr><td>w=9</td><td>343.87</td><td>266.21</td><td>332.61</td><td>1.29x</td><td>1.25x</td></tr><tr><td rowspan="4">K-283</td><td>w=6</td><td>738.62</td><td>544.43</td><td>583.54</td><td>1.36x</td><td>1.07x</td></tr><tr><td>w=7</td><td>653.78</td><td>489.27</td><td>527.23</td><td>1.34x</td><td>1.08x</td></tr><tr><td>w=8</td><td>582.79</td><td>430.37</td><td>509.92</td><td>1.35x</td><td>1.18x</td></tr><tr><td>w=9</td><td>508.49</td><td>393.47</td><td>448.91</td><td>1.29x</td><td>1.14x</td></tr><tr><td rowspan="4">K-409</td><td>w=6</td><td>1581.53</td><td>1113.97</td><td>1284.27</td><td>1.42x</td><td>1.15x</td></tr><tr><td>w=7</td><td>1383.75</td><td>1024.39</td><td>1110.81</td><td>1.35x</td><td>1.08x</td></tr><tr><td>w=8</td><td>1203.60</td><td>889.96</td><td>1077.14</td><td>1.35x</td><td>1.21x</td></tr><tr><td>w=9</td><td>1060.99</td><td>807.13</td><td>938.07</td><td>1.31x</td><td>1.16x</td></tr><tr><td rowspan="4">K-571</td><td>w=6</td><td>3026.80</td><td>2135.81</td><td>2280.14</td><td>1.42x</td><td>1.07x</td></tr><tr><td>w=7</td><td>2627.00</td><td>1903.24</td><td>2061.80</td><td>1.38x</td><td>1.08x</td></tr><tr><td>w=8</td><td>2336.93</td><td>1675.88</td><td>1865.80</td><td>1.39x</td><td>1.11x</td></tr><tr><td>w=9</td><td>2048.58</td><td>1581.32</td><td>1816.99</td><td>1.30x</td><td>1.15x</td></tr></tbody></table>

# 5 Conclusions

In this paper we have presented a modification to the fixed-base comb method, which allows us to benefit from speedups available on Koblitz curves, i.e., the possibility of replacing point doublings with applications of the far more efficient Frobenius endomorphism $\tau$. In order to do so, one has to perform scalar recoding from base 2 to an unsigned base $\tau$ representation, for which we presented the respective algorithm. We have implemented the findings in Java, which allowed us to draw a detailed performance comparison. The implementation timings showed a speedup of up to 42% for single scalar multiplications over the conventional comb method and of up to 25% over the WTNAF method. Finally, we emphasize that the implementation of the $\tau$-comb method is straight-forward and requires only little effort. All in all, this makes it a good alternative to other fixed-base multiplication methods.

## 5.1 Related and Future Work

The authors of [2] showed how $\tau$-adic representations can be optimized using tele-
scopic sums in combination with a single point halving operation giving a speed-
up of ≈ 12.5% over the conventional TNAF method. Later on, this approach was
refined in [3] resulting in about 25% less group operations. In [1], the authors
study how the Frobenius endomorphism $\tau$ can be efficiently combined with the
GLV-method by using powers of $\tau$. This way, they are able to decompose scalars
and apply interleaved point multiplication on the decomposed smaller scalars,
setting new speed records using a low-level implementation. Implementing the
aforementioned approaches and drawing comparisons to the method proposed
in this paper are issues for future work.

The authors of [15] proposed a new, fast fixed-base comb method, which
combines the Lim-Lee and the Tsaur-Chou method [19]. Future work includes
adapting this new fixed-base comb multiplier to work with the Frobenius endo-
morphism.

References

1. Aranha, D.F., Faz-Hernández, A., López, J., Rodríguez-Henríquez, F.: Faster im-
plementaton of scalar multiplication on Koblitz curves. In: LATINCRYPT. pp.
177–193 (2012)

2. Avanzi, R.M., Ciet, M., Sica, F.: Faster scalar multiplication on Koblitz curves combining point halving with the Frobenius endomorphism. In: Public Key Cryptography - PKC 2004, 7th International Workshop on Theory and Practice in Public Key Cryptography, Singapore, March 1-4, 2004. Lecture Notes in Computer Science, vol. 2947, pp. 28–40. Springer (2004), http://www.iacr.org/cryptodb/archive/2004/PKC/3329/3329.pdf

3. Avanzi, R.M., Heuberger, C., Prodinger, H.: Minimality of the hamming weight of the t-naf for koblitz curves and improved combination with point halving. In: Selected Areas in Cryptography. pp. 332–344 (2005)

4. Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press (2005)

5. Gallagher, P., Furlani, C.: FIPS PUB 186-3 federal information processing stan-
dards publication digital signature standard (dss) (2009)

6. Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc., Secaucus, NJ, USA (2003)

7. Higuchi, A., Takagi, N.: A fast addition algorithm for elliptic curve arithmetic in GF(2ⁿ) using projective coordinates. Inf. Process. Lett. 76(3), 101–103 (2000)

8. Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48(177), pp. 203–209 (1987)

9. Lange, T.: A note on López-Dahab coordinates. IACR Cryptology ePrint Archive 2004, 323 (2004)

10. Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: CRYPTO. pp. 95–107 (1994)

11. López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(2ⁿ). In: Selected Areas in Cryptography. pp. 201–212 (1998)

12. López, J., Dahab, R.: High-speed software multiplication in $F_{2^m}$. In: INDOCRYPT. pp. 203–212 (2000)

13. Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. In: Proceedings of the twenty-third annual ACM symposium on Theory of computing. pp. 80–89. STOC ’91, ACM, New York, NY, USA (1991)

14. Miller, V.S.: Use of elliptic curves in cryptography. In: Lecture notes in computer sciences; 218 on Advances in cryptology—CRYPTO 85. pp. 417–426. Springer-Verlag New York, Inc., New York, NY, USA (1986)

15. Mohamed, N.A.F., Hashim, M.H.A., Hutter, M.: Improved fixed-base comb method for fast scalar multiplication. In: AFRICACRYPT. pp. 342–359 (2012)
16. Schroeppel, R., Orman, H.K., O'Malley, S.W., Spatscheck, O.: Fast key exchange with elliptic curve systems. In: CRYPTO. pp. 43–56 (1995)

17. Silverman, J.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, vol. 106. Springer (1986)

18. Solinas, J.A.: Efficient arithmetic on Koblitz curves. Des. Codes Cryptography 19(2/3), 195–249 (2000)

19. Tsaur, W.J., Chou, C.H.: Efficient algorithms for speeding up the computations of elliptic curve cryptosystems. Applied Mathematics and Computation 168(2), 1045 – 1064 (2005), http://www.sciencedirect.com/science/article/pii/S0096300304006629