3
$\begingroup$

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.

enter image description here

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):

enter image description here

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}$:

enter image description here

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}}$:

enter image description here

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.

$\endgroup$
8
  • $\begingroup$ You might be missing the point that the base fields are in general not arbitrary primes or primes powers. The reduction can be easily implemented and GMP cannot see this. Your question lacks many details that we cannot answer completely. $\endgroup$
    – kelalaka
    Jan 21 at 16:24
  • $\begingroup$ I think the question is missing that projective coordinates become useful when doing point multiplication by a scalar of more than few bits, because they reduce the number of modular inversions drastically, since that's necessary only for the final result. $\endgroup$
    – fgrieu
    Jan 21 at 16:41
  • $\begingroup$ The performance numbers you give in the table don't make much sense; for example, the time for "Sqmod" (10) is more than the time given for a M (multiply) plus mod. Given that a modular squaring can be implemented by multiplying a number by itself, and then taking the modular reduction, it's unclear why there's a specific Sqmod operation that's actually more expensive. $\endgroup$
    – poncho
    Jan 21 at 17:15
  • $\begingroup$ @kelalaka good point. I’ll try to implement better reduction algorithms and give it another shot. Still, even with reduction going to zero at first glance the advantage is not too clear, but I’ll try and see. Thanks for the input! $\endgroup$
    – popeye
    Jan 21 at 17:16
  • $\begingroup$ @fgrieu thanks a lot for the input. I don’t quite understand why the advantage would come when performing scalar multiplication by an integer with lots of bits when the unitary arithmetic operations that are performed in each loop seem to be as or more efficient in affine coordinates. $\endgroup$
    – popeye
    Jan 21 at 17:19

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.