Paper 2024/1906

On Efficient Computations of $y^2=x^3+b/\mathbb{F}_p$ for Primes $p\equiv 1 \mod 3$

Abstract

Since its introduction, Solinas' window $\tau$-NAF algorithm has been a landmark method for accelerating scalar multiplication on Koblitz curves over binary fields. A long-standing open problem has been to identify a suitable family of elliptic curves over prime fields for which the window $\tau$-NAF approach can be effectively extended. In this paper, we settle this problem by establishing such an extension for the family $E_b: y^2=x^3+b$ over $\mathbb{F}_p$ with prime $p\equiv1\pmod 3$. This family includes several practically important curves used in blockchain applications (e.g., secp256k1) and pairing-based cryptography (e.g., BN254 and BLS12-381). By considering a nonzero nonunit element of minimal norm in the ring of Eisenstein integers $\mathbb{Z}[\omega]$, we identify the endomorphism $\tau=1-\omega$ as a natural choice for $\tau$-adic scalar multiplication on $E_b/\mathbb{F}_p$. In Jacobian projective coordinates, the map $\tau P$ can be evaluated using only $6\mathbf{M}$ (where $\mathbf{M}$ denotes a field multiplication). This also yields a new point-tripling formula requiring only $10\mathbf{M}$, improving upon the previous best cost of $15\mathbf{M}$. Furthermore, we optimize the pre-computation stage by choosing a set of coefficients invariant under the unit group $U\subset\mathbb{Z}[\omega]$. Exploiting this sixfold symmetry reduces the pre-computation cost by approximately five-sixths. The $U$-invariant structure also plays an important role in further accelerating window $\tau$-NAF evaluation. Our optimized method achieves performance improvements of $16.7\%$, $17.6\%$, and $18\%$ over the current state-of-the-art GLV method for $256$-, $384$-, and $512$-bit group orders, respectively. We also develop a regular window $\tau$-NAF variant as a countermeasure against side-channel attacks. Compared with the regularized GLV method, this variant reduces the scalar multiplication cost by $17.7\%$, $19.8\%$, and $20.9\%$ for $256$-, $384$-, and $512$-bit group orders, respectively.