TLDR - Point doubling and addition on elliptic curve points requires a field inversion and several multiplications. We consider a field $K$ (of characteristic that is neither $2$ or $3$). Given an inversion in $K$ is significantly more expensive than multiplication, then it is generally more efficient to use projective point coordinates to compute these operations.
What is a projective point?
The projective form of the Weistrass equation (see Guys blog last week) for an elliptic curve $E$ is an alternative but equivalent way of defining a point. We do not gain any additional functionality and, in fact, we can define an equivalence relation. Let $c$ and $d$ be positive integers and $K$ is a field (of characteristic that is neither $2$ or $3$), then the equivalence relation $\sim$ on the set $K^{3}\backslash\{0,0,0\}$ of nonzero triples over the field $K$ is
$(X_1,Y_1,Z_1) \sim (X_2,Y_2,Z_2)$ if $X_1 = \lambda^c X_2,Y_1 = \lambda^d Y_2,Z_1= \lambda Z_2$ for some $\lambda \in K^*$.
The equivalence class containing $(X,Y,Z) \in K^3 \backslash \{0,0,0\}$ is
$(X:Y:Z) = \{(\lambda^c X, \lambda^d Y, \lambda Z) : \lambda \in K^*\}$.
We now have the projective point $(X:Y:Z)$ and its representation $(X,Y,Z)$.
Various projective coordinate systems have been proposed in the literature but for the purpose of this blog we consider the Jacobian coordinate system. In this representation, the projective point $(X:Y:Z)$ where $Z \not= 0$ corresponds to the affine point $(\frac{X}{Z^2}, \frac{Y}{Z^3})$.
What are the advantages to using projective point representation?
Using projective point representation to compute point addition and doubling results in fewer field inversions and a higher number of multiplications (in comparison to working with affine coordinates). This can be demonstrated by converting the projective points to affine coordinates and attempting to simplify for addition and doubling operations. The resulting equation clears the denominators and hence removes the field inversion. At face value, this doesn't seem like a great achievement, however, evaluating a field inversion is significantly more computationally expensive than multiplication given the current state of the art in computer systems. To give an idea of the number of operations comparison for Affine vs Jacobian:
| Format | Doubling | Addition |
|---|---|---|
| Affine | 1I, 2M, 2S | 1I, 2M, 1S |
| Jacobian | 4M, 4S | 12M, 4S |
Operation counts for point addition and doubling on $y=x^3 - 3x + b$. I = inversion, M = multiplication, S = squaring.
Exact performance counters are tricky as they will be dependant on the underlying platform and implementation. However, as long as field inversions remain significantly more expensive than multiplications, using affine coordinates will incur a high performance penalty over projective points.
Any drawbacks?
Not that I know of (although I wouldn't consider myself an expert in this field). As ever, there is always the scope to cock-up the implementation and potentially leak bits of the underlying discrete logs through $Z$[1].
No comments:
Post a Comment