Score:0

Is it possible to give a definition for point multiplication on elliptic curve?

ie flag

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?

kelalaka avatar
in flag
There is a Math theory behind this: [Z-Module](https://en.wikipedia.org/wiki/Module_(mathematics)); That is, every abelian group is a module over the ring of integers Z in a unique way...
user77340 avatar
ie flag
@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!
kelalaka avatar
in flag
Related [How do I multiply two points on an elliptic curve?](https://crypto.stackexchange.com/q/88214/18298)
Score:4
ng flag

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

user77340 avatar
ie flag
that's what I want! Thanks!
kelalaka avatar
in flag
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.
Score:2
sa flag

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.

user77340 avatar
ie flag
I see. I just think if it is possible to give one. But anyway, thanks!
kelalaka avatar
in flag
@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!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.