# Improving the Efficiency of Elliptic Curve Scalar Multiplication Using Binary Huff Curves

Gerwin Gsenger, Christian Hanser

► To cite this version:

Gerwin Gsenger, Christian Hanser. Improving the Efficiency of Elliptic Curve Scalar Multiplication Using Binary Huff Curves. 1st Cross-Domain Conference and Workshop on Availability, Reliability, and Security in Information Systems (CD-ARES), Sep 2013, Regensburg, Germany. pp.155-167. hal-01506564

HAL Id: hal-01506564

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

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
# Improving the Efficiency of Elliptic Curve Scalar Multiplication using Binary Huff Curves

Gerwin Gsenger and Christian Hanser

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

**Abstract.** In 2010, Joye et. al brought the so-called Huff curve model, which was originally proposed in 1948 for the studies of diophantine equations, into the context of elliptic curve cryptography. Their initial work describes Huff curves over fields of large prime characteristic and details unified addition laws. Devigne and Joye subsequently extended the model to elliptic curves over binary fields and proposed fast differential addition formulas that are well-suited for use with the Montgomery ladder, which is a side-channel attack resistant scalar multiplication algorithm. Moreover, they showed that, in contrast to Huff curves over prime fields, it is possible to convert (almost) all binary Weierstrass curves into Huff form.

We have implemented generalized binary Huff curves in software using a differential Montgomery ladder and detail the implementation as well as the optimizations to it. We provide timings, which show speed-ups of up to 7.4% for binary NIST curves in Huff form compared to the reference implementation on Weierstrass curves. Furthermore, we present fast formulas for mapping between binary Weierstrass and generalized binary Huff curves and vice versa, where in the back conversion step an implicit $y$-coordinate recovery is performed. With these formulas, the implementation of the differential Montgomery ladder on Huff curves does not require more effort than its counterpart on Weierstrass curves. Thus, given the performance gains discussed in this paper, such an implementation is an interesting alternative to conventional implementations. Finally, we give a list of Huff curve parameters corresponding to the binary NIST curves specified in FIPS 186-3.

## 1 Introduction

In 1985, Neal Koblitz [10] 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). Traditionally, Weierstrass equations have been
used to describe elliptic curves. Nevertheless, over time, especially in the last
couple of decades, new models to describe elliptic curves have been found, such
as the Montgomery form, the Edwards form [2] and the like.

In 1948, Huff was studying a diophantine problem, for which he introduced
a new elliptic curve model [8]. In 2010, Joye et. al [9], studied Huff's model over
fields of odd characteristic and introduced formulas for fast point arithmetics.
Each Huff curve defined over $\mathbb{F}_p$ contains a subgroup isomorphic to $\mathbb{Z}_4 \times \mathbb{Z}_2$
which, unfortunately, implies that there are no standardized prime curves that
can be expressed in Huff form, as all these curves have cofactors equal to one.
The Huff model has subsequently been extended by Devigne and Joye [5] to cover
elliptic curves defined over binary fields $\mathbb{F}_{2^m}$. Furthermore, in [5], they present a
unified addition law and give very fast differential addition formulas for binary
Huff curves, which are well-suited for use with the Montgomery ladder, which is
a side-channel attack resistant scalar multiplication algorithm.

For $m \ge 4$, every Weierstrass curve over $\mathbb{F}_{2^m}$ is birationally equivalent to a
generalized Huff curve. Therefore, we are free to convert all standardized binary
curves into corresponding (generalized) binary Huff curves. The authors of [5],
give formulas for mapping points between binary Weierstrass curves and binary
Huff curves, using an intermediate Weierstrass curve isomorphic to the original
curve in short Weierstrass form.

## 1.1 Contribution

We have implemented generalized binary Huff curves in software, where for scalar
multiplication we use a differential Montgomery ladder, which is a good choice
for software implementations running in server environments, as it is resistant to
remote timing attacks [4, 3, 18]. The differential Montgomery ladder is based on
the differential addition formulas given by Devigne and Joye in [5]. The timings
show that for the binary NIST curves, this implementation is up to 7.4% faster
than the reference implementation of the differential Montgomery ladder on the
original Weierstrass curves, to which we have applied the same optimizations.

The conversion between binary Weierstrass and generalized binary Huff curves
requires two steps. As generalized binary Huff curves are birationally equivalent
to a class of Weierstrass curves, which are themselves isomorphic to curves in
short Weierstrass form, it is necessary to apply a birational equivalence as well as
an isomorphism for the conversion. Additionally, after applying the differential
Montgomery ladder on binary Huff curves and mapping the result back to the
corresponding Weierstrass curve, a y-coordinate recovery is necessary. We address this issue by providing fast all-in-one, back-and-forth conversion formulas.
These back-and-forth conversions turn out to be almost as efficient as the y-
coordinate recovery on Weierstrass curves, which is required anyway after using
the differential Montgomery ladder on Weierstrass curves, which preserves most
of the savings obtained through the faster differential addition formulas. When
using the formulas presented in this paper, the implementation of the differential
Montgomery ladder on Huff curves does not require more effort than its counterpart on Weierstrass curves. Thus, given the performance gains discussed in
this paper such an implementation is an interesting alternative to conventional implementations.

Finally, we present curve parameters for Huff curves, which are birationally equivalent to the NIST-recommended binary Weierstrass curves specified in FIPS 186-3 [6].

## 1.2 Outline

In Section 2 and 3 we are going to talk about elliptic curves in general and the Huff curve model in particular. Section 4 gives the Huff curve parameters we have derived for the NIST-recommended curves. It details the implementation, the improvements we have achieved, shows the benchmark results and draws a comparison to the reference implementation. At last, Section 5 concludes the paper.

# 2 Preliminaries

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

$$E: Y^2 + a_1 XY + a_2 Y = X^3 + a_3 X^2 + a_4 X + 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 $\mathcal{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 [16].

For cryptographic purposes, we are interested in elliptic curves over finite fields $\mathbb{F}_q$, especially in curves over fields $\mathbb{F}_{2^m}$ 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 $Q, P \in E(\mathbb{F}_q)$ the ECDLP constitutes the problem of finding a scalar $k \in \mathbb{Z}$ such that $Q = k \cdot P$.

In cryptography, usually non-supersingular curves are being used, 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_2 X^2 + a_6, \quad (2)$$

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

For binary field multiplications we are using the windowed left-to-right comb multiplier as detailed in [7]. This algorithm uses lookup-tables, which can be cached and reused to speed up multiplications with frequently used values, such as curve parameters. In the following, let $\mathbf{M}$ and $\mathbf{S}$ denote the costs of one field multiplication and one field squaring, respectively. Moreover, let $\mathbf{m}_w$ stand for the cost of the multiplication with some value, for which the lookup table of window size $w$ has already been calculated.
## 2.1 Differential Addition and the Montgomery Ladder

Scalar multiplication is the most crucial and at the same time the most costly operation on elliptic curves and there are many ways to perform elliptic curve scalar multiplications. One way to do so is the so-called Montgomery ladder, which is both side-channel resistant and reasonably fast. Its side-channel resistance is due to the fact that at each ladder step, regardless of the currently processed bit of the scalar $k$, one point doubling operation as well as one point addition operation are performed and only the order of execution is changed. Thus, in order to mitigate side-channel attacks, the Montgomery ladder is widely used, especially in hardware implementations. In the context of software implementations, side-channel resistance is less important. Still, there are scenarios, such as cryptographic implementations running on servers, where remote timing attacks can be performed (cf. [4, 3, 18]) and, therefore, timing-attack proof implementations are required. This issue can again be addressed with the use of the Montgomery ladder, as its execution time is constant for fixed scalar lengths.

For the fast application of the Montgomery ladder, differential addition and doubling formulas are necessary. Luckily, these two operations can be performed very efficiently on Huff curves. By *differential point addition*, we mean the computation of $w(P+Q)$ from $w(P)$, $w(Q)$, and $w(P-Q)$, where $w(\cdot)$ is a coordinate function for which typically $w(P) = w(-P)$ is demanded. Note that the difference $w(P-Q)$ required for the differential addition steps within the Montgomery ladder is fixed, i.e., the difference of the resulting points stays invariant throughout the whole process. For differential addition on Weierstrass curves, the knowledge of $y$-coordinates is irrelevant, as the computation of $x$-coordinates does not involve them, which is reflected in the definition of $w(\cdot)$. Clearly, this saves computational effort, as the $y$-coordinate of intermediate results is not computed. Analogously, we mean by differential doubling the computation of $w(2P)$ from $w(P)$.

On Weierstrass curves, the fastest differential addition formulas are due to Bernstein and Lange (see [1]). From the results of Stam [17], they derive a representation, called *XZ-coordinates*, featuring fast differential addition and doubling formulas. Per bit of scalar $k$, these formulas require $5M + 1m_8 + 4S$ for $P$ known a priori and $6M + 2m_8 + 5S$ otherwise.

The Montgomery ladder for projective differential addition formulas is shown in Algorithm 1. Here, the addition and the doubling steps are carried out using differential addition and differential doubling formulas, where in the former case the input is $W(2P)$, $W(P)$ and the invariant, consequently, is $W(P)$. Note that $W(\cdot)$ stands for the projective version of the coordinate function $w(\cdot)$.

After application of the Montgomery ladder, the $y$-coordinate of the product $k \cdot P = (x_1, y_1)$ can be restored efficiently and, hence, there is no need to compute it in the intermediate steps. Restoring the $y$-coordinate for affine coordinates, also means simultaneously scaling the $x$-coordinate, in order to avoid multiple
**Algorithm 1 Differential Montgomery Ladder**

**Require:** A point $P$ on $E$ and a scalar $k = (k_{l-1}, \dots, k_0)_{2 \in \mathbb{Z}}$

**Ensure:** $W(k \cdot P) = (X_1 : Z_1)$
$(X_1 : Z_1) = W(P)$ and $(X_2 : Z_2) = W(2P)$

for $i = l - 2$ downto 0 do

if $k_i = 0$ then

$(X_1 : Z_1) = 2(X_1 : Z_1)$, and

$(X_2 : Z_2) = (X_1 : Z_1) + (X_2 : Z_2)$

else

$(X_1 : Z_1) = (X_1 : Z_1) + (X_2 : Z_2)$, and

$(X_2 : Z_2) = 2(X_2 : Z_2)$

end if

end for

inversions. It works in the following way, as detailed in [11] and in [17]:

$$x_1 = \frac{\bar{Z}\bar{X}Z_2X_1}{\bar{Z}\bar{X}Z_2Z_1} \quad \text{and} \quad y_1 = \bar{Y} + \frac{\gamma((X_1\bar{Z} + \bar{X}Z_1)\gamma + Z_1Z_2\bar{X}^2 + Z_1Z_2\bar{Z}\bar{Y})}{\bar{Z}\bar{X}Z_2Z_1},$$

where $\gamma = X_2\bar{Z} + \bar{X}Z_2$ and $P = (\bar{X} : \bar{Y} : \bar{Z}) \neq \emptyset$. There are two special cases to check, see [11] for more details on that. Using these formulas requires $\mathbf{1I} + \mathbf{10M}$, when assuming $\bar{Z} = 1$, i.e., $P$ to be scaled.

## 3 The Binary Huff Curve Model

This section is mainly a recapitulation of the research done by Joye et. al in [5] and [9], since we need these facts in Section 4 in order to derive compact formulas for mapping between binary Weierstrass and binary Huff curves.

As defined in [5], binary Huff curves are a new class of elliptic curves. For every Weierstrass curve defined over $\mathbb{F}_{2^m}$ with $m \ge 4$, there is a birationally equivalent generalized binary Huff curve. A generalized binary Huff curve is given by the set of projective points $(X : Y : Z)$ over $\mathbb{F}_{2^m}$ satisfying the subsequent equation:

$$E_H : aX(Y^2 + fYZ + Z^2) = bY(X^2 + fXZ + Z^2) \quad (3)$$

with $a, b, f \in \mathbb{F}_{2^m}^*$ and $a \neq b$. Three points at infinity, i.e., $(1 : 0 : 0), (0 : 1 : 0)$, and $(a : b : 0)$, satisfy Equation (3). The affine version of Equation (3) is birationally equivalent to the subsequent binary Weierstrass curve:

$$E_{W'} : v(v + (a+b)fu) = u(u + a^2)(u + b^2), \quad (4)$$

which itself is isomorphic to the short Weierstrass form through the following isomorphism:

$$\Theta : E_W(\mathbb{F}_{2^m}) \to E_{W'}(\mathbb{F}_{2^m}) \\ (u, v) \mapsto (\mu^2 u, \mu^3 (v + su + \sqrt{a_6})),$$
and its inverse:

$$ \begin{gathered} \Omega : E_{W'}(\mathbb{F}_{2^m}) \to E_W(\mathbb{F}_{2^m}) \\ (u', v') \mapsto (\nu^2 u', \nu^3 v' + s\nu^2 u' + \sqrt{a_6}) \end{gathered} $$

with $\mu = (a+b)f$, $\nu = \mu^{-1}$, and $s \in \mathbb{F}_{2^m}$ satisfying $s^2 + s = a_2 + f^{-2}$. The birational equivalence

$$ \begin{gathered} \Phi : E_{W'}(\mathbb{F}_{2^m}) \to E_H(\mathbb{F}_{2^m}), \\ (u, v) \mapsto \left( \frac{b(u+a^2)}{v}, \frac{a(u+b^2)}{v+(a+b)fu} \right), \end{gathered} $$

maps from the Weierstrass curve $E_{W'}$ onto the Huff curve $E_H$. Its inverse looks as follows:

$$ \begin{gathered} \Psi : E_H(\mathbb{F}_{2^m}) \to E_{W'}(\mathbb{F}_{2^m}), \\ (x, y) \mapsto \left( \frac{ab}{xy}, \frac{ab(axy+b)}{x^2y} \right) \end{gathered} $$

The neutral element is $(0, 0)$ and the group law is based on the chord-and-tangent rule. Note, however, that the birational equivalences are not line-preserving. The inverse of some affine point $P = (x_1, y_1) \in E_H$ is

$$ -P = \left( y_1 \frac{(\alpha x_1 + 1)}{(\beta y_1 + 1)}, x_1 \frac{(\beta x_1 + 1)}{(\alpha x_1 + 1)} \right), \qquad (5) $$

with $\alpha = \frac{a+b}{b \cdot f}$ and $\beta = \frac{a+b}{a \cdot f}$. The projective homogenization of Equation (5) can be evaluated using $4M + 4m_8$. Furthermore, there are four exceptional cases, which have to be dealt with separately. We refer the reader to [5] for more details on that. Compared to binary Weierstrass curves, where point inversion costs at most one field addition and, hence, is negligible, this operation is very expensive on binary Huff curves.

Projective point doubling, and point addition take $6M + 2m_8 + 6S$ and $15M + 3S$, respectively. The affine doubling formula looks as follows:

$$ 2P = \begin{cases} (1:0:0) & \text{if } x_1 = 1, \\ (0:1:0) & \text{if } y_1 = 1, \\ (a:b:0) & \text{if } x_1 y_1 = 1, \text{ and} \\ \left( \frac{f(a+b)x_1^2(1+y_1)^2}{b(1+x_1)^2(1+x_1y_1)^2}, \frac{f(a+b)y_1^2(1+x_1)^2}{a(1+y_1)^2(1+x_1y_1)^2} \right) & \text{otherwise.} \end{cases} \qquad (6) $$

where $P = (x_1, y_1) \in E_H$. Also note that for subgroups not including the points at infinity a complete addition law exists, i.e., it can also be used for point doublings.
## 3.1 Differential Addition

For Huff curves, the authors of [5] give differential addition formulas for use with the Montgomery ladder. To do so, they introduce the coordinate function $w(x, y) = xy$, which fulfills the condition $w(P) = w(-P)$. From Formula (6), they derive the following differential doubling formula:

$$w(2P) = \begin{cases} \gamma \cdot \frac{w_1^2}{(1+w_1)^4} & \text{if } w_1 \neq 1, \text{ and} \\ (1:0) & \text{otherwise.} \end{cases} \qquad (7)$$

where $\gamma = \frac{(a+b)^2}{ab}$ and $w_1 = w(P)$. Using the birational equivalence $\Phi$ and the multiplicative differential addition formula from [17], the authors of [5] obtain the subsequent addition formula:

$$w(P+Q) = \begin{cases} \frac{(w_1+w_2)^2}{\bar{w}(1+w_1w_2)^2} & \text{if } w_1w_2 \neq 1, \text{ and} \\ (1:0) & \text{otherwise.} \end{cases} \qquad (8)$$

where $P \neq Q$, $w_1 = w(P)$, $w_2 = w(Q)$, and $\bar{w} = w(P - Q)$.

Working with affine coordinates is less satisfying due to the costly inversion required in each step. Hence, Devigne and Joye introduce projective WZ-coordinates. A point $P = (\frac{X_1}{Z_1}, \frac{Y_1}{Z_1}) \in E_H$ in WZ-coordinates, is represented by the tuple

$$(W:Z) = \begin{cases} (\theta w(P):\theta) = (\theta X_1 Y_1 : \theta Z_1^2) & \text{if } P \neq (a:b:0), \text{ and} \\ (\theta:0) & \text{otherwise.} \end{cases}$$

for some $\theta \in \mathbb{F}_{2^m}^*$. Now, when given $P = (W_1:Z_1)$ and $Q = (W_2:Z_2)$, the projective differential addition formulas look as follows:

$$\begin{cases} W(2P) = \gamma \cdot (W_1 Z_1)^2 \\ Z(2P) = (W_1 + Z_1)^4 \end{cases} \quad \text{and} \quad \begin{cases} W(P+Q) = \bar{Z} (W_1 Z_2 + W_2 Z_1)^2 \\ Z(P+Q) = \bar{W} (W_1 W_2 + Z_1 Z_2)^2, \end{cases}$$

where $W(P - Q) = (\bar{W}, \bar{Z})$ are the WZ-coordinates of $P - Q$. Obviously, the first requires $1M + 1m_8 + 3S$, whereas the latter requires $6M + 2S$, which can be improved to $4M + 2S$ by computing $W_1Z_2 + W_2Z_1$ as $(W_1 + Z_1)(W_2 + Z_2) + (W_1W_2 + Z_1Z_2)$ and scaling the coordinate $(\bar{W} : \bar{Z})$, since it remains constant throughout the whole Montgomery ladder process.

## 4 Contribution

In this section we are going to describe a Huff curve implementation and the optimizations we have applied to it. Furthermore, we contrast its performance with a reference implementation that is based on Weierstrass curves, to which we have applied the same set of optimizations. Then, we present timings of both
implementations, which show that for the binary NIST curves, the Huff curve implementation is up to 7.4% faster than the reference implementation.

We also present the curve parameters for the binary Huff curves corresponding to the binary NIST curves and give formulas for back-and-forth conversion between binary Huff curves and binary curves in short Weierstrass form.

## 4.1 Deriving Curve Parameters

Deriving curve parameters $a, b, f \in \mathbb{F}_{2^m}$ from a given binary Weierstrass curve with parameters $a_2, a_6 \in \mathbb{F}_{2^m}$, works as follows [5, Proof of Proposition 2]:

1. Select an arbitrary $f \in \mathbb{F}_{2^m}$ so that $\mathrm{Tr}(f^{-1}) = \mathrm{Tr}(a_2)$ and $\mathrm{Tr}(f^8 a_6) = 0$,

2. find a solution $t \in \mathbb{F}_{2^m}$ to the equation $t^2 + (f^4 \sqrt{a_6})^{-1} t + 1 = 0$, and

3. determine $a, b \in \mathbb{F}_{2^m}$ such that $\sqrt{t} = ab^{-1}$,

where $\mathrm{Tr}(\cdot)$ is the trace function $\mathrm{Tr} : \mathbb{F}_{2^m} \to \mathbb{F}_2$, $x \mapsto \sum_{i=0}^{m-1} x^{2^i}$. The parameters we have obtained for the NIST-recommended curves [6] plus the value $s$ needed for $\Omega$ and $\Theta$ are listed in Table 1 and in Table 2, respectively.

## 4.2 Mapping between Huff and Weierstrass Curves

Let $P_W = (u, v)$ be a point on $E_W(\mathbb{F}_{2^m})$, $P_{W'} = (u', v') = \Theta(P_W) \in E_{W'}(\mathbb{F}_{2^m})$ and $P = \Omega(P_{W'})$ be the corresponding point on $E_H(\mathbb{F}_{2^m})$.

**Weierstrass to Huff Curve:** From the birational equivalence $\Phi \circ \Theta$, we derive the following formula for directly mapping $P_W$ to WZ-coordinates:

$$ (W:Z) = (ab(\mu^2u + a^2)(\mu^2u + b^2):\mu^6(v + su + \sqrt{a_6})((v + su + \sqrt{a_6}) + u)) $$

Through decomposition we get:

$$ -A = \mu^2 u, $$

$$ -B = (A + a^2), C = (A + b^2), $$

$$ -D = v_1 + su + \sqrt{a_6}, E = D + u, $$

$$ -W = ab \cdot B \cdot C, \text{ and} $$

$$ -Z = \mu^6 \cdot D \cdot E. $$

The values $a^2, b^2$, and $\sqrt{a_6}$ as well as the multiplication lookup tables for the values $\mu^2, \mu^6, s$, and $ab$ can be determined a priori. For this setting, we get a total of $2M + 4m_8$ for obtaining the WZ-coordinates of $P_W$. Of course, if $P_W$ is fixed, one can precompute its scaled WZ-coordinates.

**Huff to Weierstrass Curves:** In order to convert the result $W(k \cdot P) = (W_1 : Z_1)$, obtained from applying the differential Montgomery ladder on $E_H$, back to $E_W$, we need to evaluate the birational equivalence $\Omega \circ \Psi$. The naive approach would be to, firstly, compute the $x$-coordinate of the corresponding point on $E_{W'}$
as $u_1 = \frac{ab}{w(k \cdot P)}$ then, secondly, to map the result from $E_{W'}$ to $E_W$, and, finally, to recover its y-coordinate $v_1$ using the formula from [11]:

$$v_1 = \frac{(u_1 + u) ((u_1 + u)(u_2 + u) + u^2 + v)}{u} + v, \quad (9)$$

which requires the additional value $u_2 = \frac{ab}{w((k+1) \cdot P)}$, which can be computed using the point $W((k+1)P) = (W_2 : Z_2)$ from the last step of the Montgomery ladder. All in all, this would require several inversions, which can be saved by combining the formulas. To do so, one can replace $u_1 = \frac{ab}{w(k \cdot P)}$ with $u_1 = \frac{\delta \cdot Z_1}{W_1}$, where $w(k \cdot P) = \frac{W_1}{Z_1}$ as $W(k \cdot P) = (W_1 : Z_1)$, $\delta = \frac{ab}{\mu^2}$ and $\mu = (a+b)f$, and so implicitly apply $\Omega$. By inserting it into Equation (9), one derives the following formula:

$$v_1 = \frac{(\delta Z_1 + u W_1) ((\delta Z_1 + u W_1)(\delta Z_2 + u W_2) + (u^2 + v) W_1 W_2)}{u W_1^2 W_2} + v,$$

Now, one can compute

$$U_1 = \delta Z_1 u W_1 W_2 \quad \text{and} \quad V_1 = \beta (\beta (\delta Z_2 + u W_2) + (u^2 + v) W_1 W_2) + u v W_1^2 W_2$$

with $\beta = \delta Z_1 + uW_1$ and obtain $(u_1, v_1) = \left( \frac{U_1}{u W_1^2 W_2}, \frac{V_1}{u W_1^2 W_2} \right)$. Common sub-expression elimination yields the following relations:

$$-A = \delta Z_1, \quad B = \delta Z_2,$$

$$-C = u W_1, \quad D = u W_2,$$

$$-E = A + C, \quad F = B + D,$$

$$-G = W_1 W_2, \quad H = (u^2 + v),$$

$$-I = (C \cdot G)^{-1}, \quad J = A \cdot G,$$

$$-K = J \cdot I, \quad L = E \cdot I,$$

$$-u_1 = u K, \quad \text{and}$$

$$-v_1 = L \cdot (E \cdot F + H \cdot G) + v.$$

During the computation one can save the lookup tables of the intermediate values $I$ and $G$, replacing $4M$ by $2M + 2m_4$. Moreover, $\delta$ is constant and multiplications with it require $1m_8$. Finally, we recycle the lookup table of $u_1$, exchanging $3M$ for $1M + 2m_4$. In case the point $P_W = (u, v)$ is fixed, one can precompute the lookup tables of $u$ and $H$ using $w = 8$. Thus, one can trade $1M + 3m_4 + 1S$ for $4m_8$. To sum this up, the back-conversion including the y-coordinate recovery costs $1I + 6M + 5m_4 + 2m_8 + 1S$ in general, and $1I + 5M + 2m_4 + 6m_8$ for $P_W$ fixed.

**Implications:** If the point $P_W$ is not fixed, in which case one needs both back and forth conversions including a y-coordinate recovery, one obtains total costs of at most $1I + 8M + 5m_4 + 6m_8 + 1S$. Using XZ-coordinates on short Weierstrass curves, the formulas for restoring the y-coordinate turn out to be faster by only $2m_8$ and, hence, this difference is negligible. Taking the conversion to
WZ-coordinates into account, one gets a small difference of **2M** + **6m**<sub>8</sub>, which only becomes significant if $P_W$ is not known a priori. This minimal overhead for the conversion pays off, as for the scalar multiplication using WZ-coordinates one has **4M** + **2m**<sub>8</sub> + **5S** contrary to **5M** + **1m**<sub>8</sub> + **4S** per bit of the scalar $k$ when using XZ-coordinates.

## 4.3 Implementation Details and Optimizations

The implementation is written in Java and is based on the NIST recommended elliptic curves B-163, B-233, B-283, B-409 and B-571 [6]. We are using fast reductions for the underlying binary fields and long-arrays for values thereof, which are in polynomial representation. Furthermore, we perform squarings in linear time using table lookups [15] and multiplications using the windowed left-to-right comb multiplier. The latter works with precomputed multiplication lookup tables and is due to Lim and Lee (cf. [12, 7]). For ordinary binary field multiplications we use windows of size $w = 4$ and for multiplications with values known beforehand, such as curve parameters and combinations thereof, we use windows of size $w = 8$. Additionally, we cache these lookup tables for curve parameters and recurring intermediate values in the addition/doubling formulas resulting in a quite reasonable speedup. We point out that both implementations only restore the y-coordinates without scaling the result and, thus, return projective coordinates. The coordinate $W(2P - P) = W(P) = (\bar{W} : \bar{Z})$ gets scaled and, thus, one can ignore $\bar{Z}$. Furthermore, $\bar{W}$ is either fixed because of $P$ being the base point, or fixed throughout the whole ladder steps as the point difference stays the same. In both cases one can store the multiplication lookup tables for $w = 8$. Hence, the costs of the differential addition drop from **4M** + **2S** to **3M** + **1m**<sub>8</sub> + **2S**. With differential doubling requiring **1M** + **1m**<sub>8</sub> + **3S**, one gets an overall of **4M** + **2m**<sub>8</sub> + **5S** per bit of scalar $k$. In case $P$ is not fixed, one has additional one-time costs for scaling $(\bar{W} : \bar{Z})$, that is **1I** + **1M**, and one-time costs for assembling its lookup tables with window size $w = 8$.

Finally, we emphasize that the implementation of the differential Montgomery ladder on Huff curves is straight-forward and does not require more effort than its counterpart on Weierstrass curves, especially when the all-in-one formulas presented in this paper are being used.

**Timings:** All benchmarks were carried out on an Intel Core i5-2540M running Ubuntu Linux 12.10/amd64 and OpenJDK 7u15/amd64 in server mode. Table 3 shows the timings of one application of the Montgomery ladder on the test platform using both WZ and XZ-coordinates on the binary NIST curves, where in the former case we present the timings for both cases, i.e., for fixed $P$ fixed and random $P$. The performance gains achieved through precomputations, which are possible in case of fixed $P$, are reflected in the timings. Furthermore, all timings include the recovery of the y-coordinate as well as in case of WZ-coordinates the back-and-forth conversion between Weierstrass and Huff curves.

In Table 4, one can see the relative costs of one squaring and one multiplication with a curve parameter compared to an ordinary field multiplication. This
<table><caption>Table 3: Timings of the Montgomery ladder for WZ and XZ coordinates using binary NIST curves.</caption><thead><tr><th>Coordinates</th><th>B-163 [ms]</th><th>B-233 [ms]</th><th>B-283 [ms]</th><th>B-409 [ms]</th><th>B-571 [ms]</th></tr></thead><tbody><tr><td>XZ</td><td>0.709</td><td>1.315</td><td>1.896</td><td>4.203</td><td>8.403</td></tr><tr><td>WZ</td><td>0.692</td><td>1.251</td><td>1.826</td><td>4.040</td><td>8.143</td></tr><tr><td>Speedup</td><td><strong>2.46%</strong></td><td><strong>5.12%</strong></td><td><strong>3.83%</strong></td><td><strong>4.03%</strong></td><td><strong>3.19%</strong></td></tr><tr><td>WZ (P fixed)</td><td>0.662</td><td>1.224</td><td>1.778</td><td>3.928</td><td>8.039</td></tr><tr><td>Speedup</td><td><strong>7.10%</strong></td><td><strong>7.43%</strong></td><td><strong>6.64%</strong></td><td><strong>7.00%</strong></td><td><strong>4.53%</strong></td></tr></tbody></table>

analysis shows that trading 1M for 1m<sub>8</sub> + 1S per ladder iteration, as done by using WZ instead of XZ-coordinates, saves up to 0.54M per ladder step on the test platform.

<table><caption>Table 4: Costs of squarings and multiplications with curve parameters in relation to ordinary multiplications.</caption><thead><tr><th></th><th>F<sub>2</sub><sup>163</sup></th><th>F<sub>2</sub><sup>233</sup></th><th>F<sub>2</sub><sup>283</sup></th><th>F<sub>2</sub><sup>409</sup></th><th>F<sub>2</sub><sup>571</sup></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<sub>8</sub> =</td><td>0.369M</td><td>0.411M</td><td>0.387M</td><td>0.418M</td><td>0.430M</td></tr></tbody></table>

# 5 Conclusions

We have implemented binary Huff curves in software. For scalar multiplication, we were using a differential Montgomery ladder, based on the differential addition formulas given by Devigne and Joye in [5]. The timings show that for the binary NIST curves, this implementation is up to 7.4% faster than the reference implementation of the differential Montgomery ladder on the corresponding Weierstrass curves, to which we have applied the same set of optimizations.

We have presented fast all-in-one back-and-forth conversion formulas, which implicitly include the recovery of the y-coordinate. These conversions turn out to be almost as efficient as the y-coordinate recovery on Weierstrass curves, which is required anyway after using the Montgomery ladder on Weierstrass curves. This preserves most of the savings obtained through the faster differential addition formulas. Furthermore, we have presented curve parameters for Huff curves, which are birationally equivalent to the NIST-recommended binary Weierstrass curves.

Finally, we emphasize that when using the formulas presented in this paper, the implementation of the differential Montgomery ladder on Huff curves does not require more effort than its counterpart on Weierstrass curves. Thus, given the performance gains discussed in this paper such an implementation is an interesting alternative to conventional implementations.
References

1. Bernstein, D.J., Lange, T.: Explicit-formulas database. http://www.hyperelliptic.org/EFD/index.html

2. Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: ASIACRYPT. pp. 29–50 (2007)

3. Brumley, B.B., Tuveri, N.: Remote timing attacks are still practical. In: ESORICS. pp. 355–371 (2011)

4. Brumley, D., Boneh, D.: Remote timing attacks are practical. Computer Networks 48(5), 701–716 (2005)

5. Devigne, J., Joye, M.: Binary Huff curves. In: Proceedings of the 11th international conference on Topics in cryptology: CT-RSA 2011. pp. 340–355. CT-RSA’11, Springer-Verlag, Berlin, Heidelberg (2011)

6. Gallagher, P., Furlani, C.: Fips pub 186-3 federal information processing standards publication digital signature standard (dss) (2009)

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

8. Huff, G.B.: Diophantine problems in geometry and elliptic ternary forms. Duke Math. J. 15, 443–453 (1948)

9. Joye, M., Tibouchi, M., Vergnaud, D.: Huff’s model for elliptic curves. In: ANTS. pp. 234–250 (2010)

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

11. López, J., Dahab, R.: Fast multiplication on elliptic curves over GF(2<sup>m</sup>) without precomputation. In: Cryptographic Hardware and Embedded Systems, First International Workshop, CHES’99, Worcester, MA, USA, August 12-13, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1717, pp. 316–327. Springer (1999)

12. López, J., Dahab, R.: High-speed software multiplication in F<sub>2<sup>m</sup></sub>. 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. Schroeppel, R., Orman, H.K., O’Malley, S.W., Spatscheck, O.: Fast key exchange with elliptic curve systems. In: CRYPTO. pp. 43–56 (1995)

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

17. Stam, M.: On Montgomery-like representations for elliptic curves over GF(2<sup>k</sup>). In: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography. pp. 240–253. PKC ’03, Springer-Verlag, London, UK, UK (2003)

18. Zhang, Y., Juels, A., Reiter, M.K., Ristenpart, T.: Cross-vm side channels and their use to extract private keys. In: ACM Conference on Computer and Communications Security. pp. 305–316 (2012)