Problem with efficiency of projective coordinates in Elliptic Curve arithmetic

Question

Ok sort of long post incoming. Will go slow to make it as clear as possible

I'm trying to build a C library for Elliptic Curve Arithmetic. Since the idea is to learn from the process, I decided to support many different coordinate systems. So far, I've implemented the group arithmetic for Affine and Projective coordinates for curves in Short Weierstrass form. Before moving on to Jacobian coordinates and other types of curves such as Twisted Edwards, I wanted to check the speed-up gained from using projective coordinates. I created an instance of the BN128 curve and, to my surprise, they actually take the same or longer! To my knowledge, the results of the calculations are correct (both coordinate systems match each other and both match those using https://github.com/ethereum/py_ecc/tree/main). I know the idea of using projective coordinates is to avoid performing field inversions. Some sources like https://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html assume 1I = 100M, but that's not what I found at all, at least on my HW. So I decided come here and ask whether what's happening is expectable, and what some shortcomings of my library might be.

To make it more digestable, I separated the algorithms cost (the cost in terms of ops of each arithmetic function) from the final combined result (comparing the cost of different ops on the base field). Since I'm interested in computing pairings, I did this not only for the curve over $F_p$ (in which case the first part is pretty trivial) but also for the curve over different field extensions up to $F_{p^{12}}$.

Field Operations

The following is the table of how many operations in the underlying field each top-level operation costs, with the usual notation: M=multiplication, S=squaring, a=addition, I=inversion, sm=scalar/constant integer multiplication, neg=negation. In the case of the BASE, which is the base field $F_p$ without any extension, the costs described are in terms of the operations using the gmp library, so M=mpz_mul, Sqmod=mpz_powm_ui, a=mpz_add, mod=mpz_mod, Imod=mpz_invert.

So for example a multiplication in a cubic extension of a field needs 8 multiplications and 15 additions of the underlying field it is extending, and so on. Most if not all of these come from the book Guide to Pairing Based Cryptography.

Computational cost of basic operations

This is somewhat difficult to calculate because it is hardware dependent and variable within the same HW as well. It is also dependent on the prime number of the field. For all the measurements here I used the prime field of the curve BN128. I measured the time each basic gmp operation took and compared it to the addition operation by averaging over a big number of repetitions. These are the approximate results on my HW (everything in units of addition):

As you can see, for the base field at least, the cost of an inversion is not at all 100x that of a multiplication, but rather 10x. If we consider the fact that I perform a modulo operation after each mpz multiplication (this might be overkill and innefficient, but didn't find a straightfowrad way to do it in some other way), the difference is around 5x.

Elliptic Curve arithmetic

To perform the group operation on points of an EC, we need to be able to add points together. There are two separate algorithms for when the points are different and for when they are equal, adding and doubling. In the case of projective coordinates, there are 3 adding algorithms for the cases $Z_1=Z_2=1$, $Z_1\neq1 \& Z_2=1$ and $Z_1, Z2\ne1$, and 2 doubling algorithms for when $Z=1$ and $Z\neq1$. The algorithms for projective coordinates were taken from https://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html

This is the comparative performance of all 5 algorithms, measured both in low level base field operations and overall performance taking into account the relative cost of the different operations, for different field extensions:

$F_{p}$:

As you can see, there's no meaningful difference that benefits the proyective coordinates. If anything, it's the other way around!

$F_{p^{12}}$:

In the case of the full field tower, the situation is much worse for the projective coordinates, taking anywhere between 1.5x and 3x the time to complete.

Question

Am I missing something big? Is this expected behavior? Did I forget something really obvious? I know doing the mpz_mod so often might be overkill and super inefficient but still there's quite a bit of difference to be expected. Thanks a lot in advance! I know this is quite the mouthful.

Answer 1

Projective coordinates allow multiplication of an elliptic curve point by an integer $k$ with no inversion in the field (modular inversion for a prime field). Inversion is several times more costly than multiplication in the field, and required at each point addition or doubling in Cartesian coordinates, thus about proportionally to the bit size of $k$ if we use Cartesian coordinates during the point multiplication. That allows projective coordinates to provide a net speed gain for $k$ more than a few bits, even when we need the result in Cartesian coordinates as is typically the case, since that requires a single inversion.

As a side benefit, projective coordinates do not require a special case for the point at infinity.

---

Consider a curve in short Weierstrass equation $y^2=x^3+a\,x+b$. In projective coordinates, a point of the elliptic curve other than the point at infinity is represented by $(X,Y,Z)$ with $(x,y)$ satisfying the curve's equation, $x\,Z=X$ and $y\,Z=Y$ in the base field (e.g. $\mathbb F_p$ for prime $p$). The point at infinity has representation $(0,Y,0)$ with $Y\ne 0$.

To convert from Cartesian coordinates $(x,y)$ (other than for the point at infinity) to projective coordinates, we can set $X=x$, $Y=y$, $Z=1$. To convert back to Cartesian, we can use $x=Z^{-1}\,X$ and $y=Z^{-1}\,Y$.

For curves with short Weierstrass equation, the formulas for point addition and point doubling use only addition and multiplication in the field.

We can perform scalar multiplication $k\times P$ where $k>0$ is an integer and $P$ is a point on the Elliptic Curve (other than for the point at infinity) known by it's $(x,y)$ coordinates by:

• set $(X,Y,Z)=(x,y,1)$
• for each bit $b$ of $k$ starting from second higher bit
  • double point $(X,Y,Z)$ in projective coordinates
  • if $b=1$, add $(x,y,1)$ to point $(X,Y,Z)$ in projective coordinates^*
• if $Z\ne 0$, output $(Z^{-1}\,X, Z^{-1}\,Y)$ which is the result in Cartesian coordinates. Otherwise, output the representation for the point at infinity, perhaps $(0,0)$.

Critically, a single inverse needs to be computed (at the last step). Therefore the cost of that among the total cost of point multiplication becomes negligible as the bit size of $k$ increases.

---

^* Note: That still requires a special case for point doubling, unless the formulas used are complete or the context insures doubling can't occur, e.g. the curve has prime order $n$ and $k\le n$.