In this work, we present new arithmetic formulas for a projective version of the affine point representation\((x,x+y/x),\) for\(x\ne 0,\) which leads to an efficient computation of the scalar multiplication operation over binary elliptic curves. A software implementation of our formulas applied to a binary Galbraith–Lin–Scott elliptic curve defined over the field\(\mathbb {F}_{2^{254}}\) allows us to achieve speed records for protected/unprotected single/multi-core random-point elliptic curve scalar multiplication at the 127-bit security level. When executed on a Sandy Bridge 3.4 GHz Intel Xeon processor, our software is able to compute a single/multi-core unprotected scalar multiplication in 69,500 and 47,900 clock cycles, respectively, and a protected single-core scalar multiplication in 114,800 cycles. These numbers are improved by around 2 and 46 % on the newer Ivy Bridge and Haswell platforms, respectively, achieving in the latter a protected random-point scalar multiplication in 60,000 clock cycles.

1. The benchmarking was run on Intel platforms Xeon E31270 3.4 GHz (Sandy Bridge), Core i5 3570 3.4 GHz (Ivy Bridge), and Core i7 4770K (Haswell). In addition, our library was submitted to the ECRYPT Benchmarking of Asymmetric Systems (eBATS) where it is publicly available.

2. See Sect.2.5 for a definition of the trace function\(\mathrm{Tr}(c).\)

3. Notice that theatomic doubling and addition operation are exclusive of the\(\lambda \)-projective coordinate system. For the sake of a fair comparison, in the second row and fifth column of Table3, the cost of performing a non-atomic point doubling plus a mixed point addition using LD coordinates is reported.

4. We stress that\(k\) can be recovered at a very low computational effort. From our experiments, the scalar\(k\) could be reconstructed with cost lower than\(5\tilde{m}\).

5. For\(w = 4\), the method is described as follows.\(Q_5 = Q_5 + Q_7\),\(Q_3 = Q_3 + Q_5\),\(Q_1 = Q_1 + Q_3\),\(Q_7 = Q_7 + Q_5 + Q_3\),\(Q = 2Q_7 + Q_1\), which requires six point additions and one point doubling.

6. The pseudo-instructionBarrier refers to an OpenMP synchronization clause that forces each thread to wait until all the other threads have completed their assigned tasks.

We wish to thank Sanjit Chatterjee, Patrick Longa and Alfred Menezes for their useful discussions.

Authors and Affiliations

1. Computer Science Department, CINVESTAV-IPN, Mexico City, Mexico

   Thomaz Oliveira & Francisco Rodríguez-Henríquez

2. Institute of Computing, University of Campinas, Campinas, Brazil

   Julio López

3. Department of Computer Science, University of Brasília, Brasília, Brazil

   Diego F. Aranha

Corresponding author

Correspondence toDiego F. Aranha.

T. Oliveira and F. Rodríguez-Henríquez: A portion of this work was performed while the authors were visiting the University of Waterloo. The authors acknowledge partial support from the CONACyT project 132073. J. López: The author was supported in part by the Intel Labs University Research Office.

Appendix A: Proofs

Proof of Theorem 1

Let\(P=(x_{P}, \lambda _{P})\) be an elliptic point in\(E_{a,b}(\mathbb {F}_{2^m})\). Then, a formula for\(2P = (x_{2P}, \lambda _{2P})\) is given by

From [23], page 81, we have the formulas:\(x_{2P} = \lambda ^2_{P} + \lambda _{P} + a\) and\(y_{2P} = x^2_{P} + \lambda _{P}x_{2P} + x_{2P}\). Then, a formula for\(\lambda _{2P}\) can be obtained as follows:

In affine coordinates, the doubling formula requires one division and two squarings. Given the point\(P = (X_{P}, L_{P}, Z_{P})\) in the\(\lambda \)-projective representation, an efficient projective doubling algorithm can be derived by applying the doubling formula to the affine point\((\frac{X_P}{Z_P},\frac{L_P}{Z_P})\). For\(x_{2P}\) we have

For\(\lambda _{2P}\), we have

From the\(\lambda \)-projective equation, we have the relation\(T \cdot X^2_{P} = X^4_{P} + b \cdot Z^4_{P}\). Then, the numerator\(w\) of\(\lambda _{2P}\) can also be written as follows,

This completes the proof.\(\square \)

Proof of Theorem 2

Let\(P=(x_{P}, \lambda _{P})\) and\(Q=(x_{Q}, \lambda _{Q})\) be elliptic points in\(E_{a,b}(\mathbb {F}_{2^m})\). Then, a formula for\(P+Q = (x_{P+Q}, \lambda _{P+Q})\) is given by

Since\(P\) and\(Q\) are elliptic points on a non-supersingular curve, we have the following relation:\(y^2_{P} + x_{P} \cdot y_{P} + x^3_{P} + a \cdot x^2_{P} = b = y^2_{Q} + x_{Q} \cdot y_{Q} + x^3_{Q} + a \cdot x^2_{Q}\). The known formula for computing the\(x\)-coordinate of\(P + Q\) is given by\(x_{P+Q} = s^2 + s + x_{P} + x_{Q} + a\), where\(s = \frac{y_{P} + y_{Q}}{x_{P} + x_{Q}}\). Then, one can derive the new formula as follows,

For computing\(\lambda _{P+Q}\), we use the observation that the\(x\)-coordinate of\((P + Q) - P\) is\(x_{Q}\). We also know that for\(-P\) we have\(\lambda _{-P} = \lambda _{P} + 1\) and\(x_{-P} = x_{P}\). By applying the formula for the\(x\)-coordinate of\((P + Q) + (-P)\) we have

Then\(\lambda _{P+Q} = \frac{x_{Q} \cdot (x_{P+Q} + x_{P})^2}{x_{P+Q} \cdot x_{P}} + \lambda _{P} + 1\).

To obtain a\(\lambda \)-projective addition formula, we apply the formulas above to the affine points\((\frac{X_{P}}{Z_{P}}, \frac{L_{P}}{Z_{P}})\) and\((\frac{X_{Q}}{Z_{Q}}, \frac{L_{Q}}{Z_{Q}})\). Then, the\(x_{P+Q}\) coordinate of\(P + Q\) can be computed as:

For the\(\lambda _{P+Q}\) coordinate of\(P + Q\), we have

In order that both\(x_{P+Q}\) and\(\lambda _{P+Q}\) have the same denominator, the formula for\(x_{P+Q}\) can be written as

Therefore,\(x_{P+Q} = \frac{X_{P+Q}}{Z_{P+Q}}\) and\(\lambda _{P+Q} = \frac{L_{P+Q}}{Z_{P+Q}}\). This completes the proof.\(\square \)

Proof of Theorem 3

The\(\lambda \)-projective formula is obtained by adding the\(\lambda \)-affine points\(2Q = (\frac{X_{2Q}}{Z_{2Q}}, \frac{L_{2Q}}{Z_{2Q}})\) and\(P = (x_{P}, \lambda _{P})\) with the formula of Theorem 2. Then, the\(x\) coordinate of\(2Q + P\) is given by

The\(\lambda _{2Q+P}\) coordinate of\(2Q + P\) is computed as

The formula for\(x_{2Q+P}\) can be written with denominator\(Z_{2Q+P}\) as follows:

Therefore,\(x_{2Q+P} = \frac{X_{2Q+P}}{Z_{2Q+P}}\) and\(\lambda _{2Q+P} = \frac{L_{2Q+P}}{Z_{2Q+P}}\). This completes the proof.\(\square \)

Appendix B: Operation count for 2-GLV double-and-add using\(\lambda \)-coordinates

Basically, three cases can occur in the 2-GLV double-and-add main loop. The first one, when the digits of both scalars\(k_1, k_2\) equal zero, we just perform a point doubling (\(D\)) in the accumulator. The second one, when both scalar digits are different from zero, we have to double the accumulator and sum two points. In this case, we perform one doubling and addition (\(DA\)) followed by a mixed addition (\(A\)). Finally, it is possible that just one scalar has its digit different from zero. Here, we double the accumulator and add a point, which can be done with only one doubling and addition operation.

Then, as the nonzero bit distributions in the scalars represented by the\(w\)-NAF are independent, we have for the first case

For the second case

And for the third case

Consequently, the operation count can be written as

Appendix C: Parameters used for the Galbraith–Lin–Scott elliptic curve

Using the notation given in Sect.4, let\(q=2^m,\) with\(m=127.\) The towering of the fields\(\mathbb {F}_{q}\) and its quadratic extension\(\mathbb {F}_{q^{2}}\cong \mathbb {F}_{q}[u]/(g(u))\) are constructed by means of the irreducible trinomials\(f(x) = x^{127} + x^{63} + 1\) and\(g(u) = u^2 + u +1\), respectively. Let\(E/\mathbb {F}_{q} : y^2 + xy = x^3 + ax^2 + b\), with\(a, b \in \mathbb {F}_{q}\), be a binary elliptic curve and define the quadratic twist of\(E\) as the Galbraith–Lin–Scott elliptic curve

with\(a' \in \mathbb {F}_{q^{2}}\) such that\(\mathrm{Tr}(a') = 1\). Given\(\#E(\mathbb {F}_q)=q+1-t,\) it follows that\(\#\tilde{E}_{a', b}(\mathbb {F}_{q^2}) = (q-1)^2+t^2=h\cdot r,\) where\(t\) is the trace of Frobenius of the curve\(E\),\(h=2\) and\(r\) is\(253\)-bit prime number.

In this work, the binary GLS elliptic curve\(\tilde{E}_{a',b}(\mathbb {F}_{q^2})\) was defined with the following parameters

• \(a' = u\)

• \(b\in \mathbb {F}_q\) is a degree\(126\) binary polynomial that can be represented in hexadecimal format as,\(b = 0x59C8202CB9E6E0AE2E6D944FA54DE7E5\)

• The\(253\)-bit prime order\(r\) of the main subgroup of\(\tilde{E}_{a',b}(\mathbb {F}_{q^2})\) is

  $$\begin{aligned} r&= 0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFF\\&FFDAC40D1195270779877DABA2A44750A5; \end{aligned}$$

• The base point\(P=(x_p, \lambda _p)\) of order\(r\) specified in\(\lambda \)-affine coordinates is,

  $$\begin{aligned} x_p&= 0x203B6A93395E0432344038B63FBA32DE\\&\quad + 0x78E51FD0C310696D5396E0681AA10E0D\cdot u\\ \lambda _p&= 0x5BD7653482085F55DEB59C6137074B50\\&\quad + 0x7F90D98B1589A17F24568FA5A1033946\cdot u. \end{aligned}$$

Reprints and permissions