0
$\begingroup$

As we know that at least in cryptography, the group operation on elliptic curve is just the point addition(https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication), which is defined on $E:y^{2}=x^{3}+a x+b$ as: $\left(x_{p}, y_{p}\right)+\left(x_{q}, y_{q}\right)=\left(x_{r}, y_{r}\right)$, $\lambda=\frac{y_{q}-y_{p}}{x_{q}-x_{p}}$, $x_{r}=\lambda^{2}-x_{p}-x_{q}$, $y_{r}=\lambda\left(x_{p}-x_{r}\right)-y_{p}$. My question is: can we give a meaningful definition for point multiplication?

$\endgroup$
3
  • 1
    $\begingroup$ There is a Math theory behind this: Z-Module; That is, every abelian group is a module over the ring of integers Z in a unique way... $\endgroup$
    – kelalaka
    Oct 27 '21 at 9:13
  • 1
    $\begingroup$ Related How do I multiply two points on an elliptic curve? $\endgroup$
    – kelalaka
    Oct 29 '21 at 8:05
  • 1
    $\begingroup$ @kelalaka Thank you so much! Your answer also helps me understand this better. Yeah, I just find it useful to my research if there is one such technique. But now I know it is not the case. Thanks! $\endgroup$
    – user77340
    Oct 31 '21 at 7:17
4
$\begingroup$

On an elliptic curve we have

  • point addition $C:=A+B$ defined for any two points $A$ and $B$ of the curve (often with special rules for $A=B$ or some special points, depending on the coordinate system).
  • neutral $\infty$ such that $A+\infty=\infty+A=A$ for all $A$ on the curve (including $\infty$)
  • opposite $-A$ of any $A$ on the curve such that $A+(-A)=(-A)+A=\infty$ (with $\infty$ it's own opposite).

Point addition is associative, and commutative.

From this we can define point multiplication by an integer $i\in\mathbb Z$ (also known as scalar multiplication), as $$i\times A\underset{\text{def}}=\begin{cases} \infty&\text{if }i=0\\ ((i-1)\times A)+A&\text{if }i>0\\ (-i)\times (-A)&\text{if }i<0 \end{cases}$$

From this it follows that for all $A$ and $B$ on the curve (including $\infty$) and all integers $i$, $j$, it holds $$\begin{align} (i+j)\times A&=(i\times A)+(j\times A)\\ i\times(A+B)&=(i\times A)+(i\times B)\\ (i\times j)\times A&=i\times (j\times A)\\ \end{align}$$ where in the above, the top left addition and bottom left multiplication are in $\mathbb Z$, and all the other operations are point addition or point multiplication by an integer.

When we talk about multiplication in Elliptic Curve cryptography, that's most often this multiplication by an integer.


In order to define multiplication of points, we need to designate a particular point $G$ and restrict to points $A$ that can be obtained as $A=a\times G$ for some integer $a\in\mathbb Z$. They form a subgroup of the curve. Many groups used in Elliptic Curve Cryptography are cyclic, meaning there exists $G$ such that any point of the group can be obtained in this way. For some curves (those with a prime number of point including $\infty$, e.g secp256k1 or secp384r1), any point $G$ other than $\infty$ can be used and all points of the curve are of this form $A=a\times G$.

For elliptic curves on a finite field as used in cryptography, there is some minimal strictly positive integer $n$ such that $n\times G=\infty$ (the order of $G$), and that's also the order (the number of elements) of said subgroup. For any $A$ in this subgroup, there is a uniquely defined $a\in[0,n)$ with $A=a\times G$.

We can then define the product of point $A=a\times G$ and $B=b\times G$ with $a,b\in[0,n)$ as the point $$A\times B\underset{\text{def}}=(a\times b\bmod n)\times G$$ That product of elliptic curve points inherits associativity, commutativity, neutral $G$, from the corresponding properties of multiplication in $\mathbb Z_n$. Distributivity w.r.t. point addition holds. Also, $(i\times A)\times B=i\times(A\times B)$ holds for all points $A$, $B$ which product is defined, and all integers $i$.

When $n$ is prime (which holds for most curves and generators $G$ used in ECC), any point $A$ except $\infty$ has inverse $A^{-1}$ such that $A\times A^{-1}=A^{-1}\times A=G$. If $A=a\times G$, then $A^{-1}=(a^{-1}\bmod n)\times G$.

Notice that this definition of multiplication depends on the choice of $G$, and is for the whole curve only when the elliptic curve group is cyclic.

Also, we can compute $C=A\times B$ efficiently if we know $a$ with $A=a\times G$ (as $C:=a\times B$) or know $b$ with $B=b\times G$ (as $C:=b\times A$). But otherwise, the best known algorithms have cost $\Theta(\sqrt n)$ on standard computers, thus are not polynomial time w.r.t. the bit size of $n$.

$\endgroup$
2
  • $\begingroup$ that's what I want! Thanks! $\endgroup$
    – user77340
    Oct 28 '21 at 9:55
  • $\begingroup$ Since you went to an educative answer, you should mention scalar multiplication. The theory about this is the Modules, and ECs are Z-Modules since they are forming an abelian group under addition. Modules are relaxation from Vector spaces. The multiplication is not well defined, maybe you should write it as $\times_G$ indicating the action of $G$ on the operation. $\endgroup$
    – kelalaka
    Oct 28 '21 at 17:44
2
$\begingroup$

A group by definition has only one operation. You would need at least a semiring with the new “multiplication” operation also being compatible with the Elliptic Curve addition.

To the best of my knowledge no such meaningful definition exists.

$\endgroup$
2
  • $\begingroup$ I see. I just think if it is possible to give one. But anyway, thanks! $\endgroup$
    – user77340
    Oct 27 '21 at 4:32
  • 1
    $\begingroup$ @user77340 No, it is not possible to define a group operation as multiplication. EC forms a Z-module, that is. What Fgriue defined is not multiplication as we know from the group theory. What is defined as is the action of the selected base element. If already had we could be talking about EC is a ring! $\endgroup$
    – kelalaka
    Oct 29 '21 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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