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 scalar multiplication method for Koblitz curves over binary fields. However, extending comparable $\tau$-adic acceleration techniques for prime-field curves has remained challenging. In this paper, we settle this problem for the family $E_b: y^2 = x^3 + b$ over $\mathbb{F}_p$ with prime $p \equiv 1 \pmod 3$. This family includes several practically important curves used in blockchain (e.g., secp256k1) and pairing-based cryptography (e.g., BN254, 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 leads to 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 the 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.5\%$, and $20.9\%$ for $256$, $384$, and $512$-bit group orders, respectively.