1
$\begingroup$

I have a question about multiplication of two points belong to elliptic curve. I know every think about adding and scalar multiplication but not about multiplication of two points. Is there any method for this?

The reason that I need this is that in paper "Attributed-based encryption for fine-grained access control of encrypted data", we need choose group G and then a point g as the generator of this group. Then in setup algorithm, we should calculate g to the power of t1, while t1 is a number. So it means that we should multiply g into itself for t1 times. If we choose an elliptic field, how could we do this multiplication?

Thanks

$\endgroup$

2 Answers 2

5
$\begingroup$

I have a question about multiplication of two points belong to elliptic curve. I know every think about adding and scalar multiplication but not about multiplication of two points.

Actually, when the paper talks about 'multiplying' two points, it's talking about what we more conventionally call 'point addition'; and hence what they call "g to the power to t1", we conventionally call "multiply the point g by the integer t1, that is, g added to itself t1 times".

It's not clear why they decided to refer to the elliptic curve as a multiplicative group and not an additive one. Their paper is from 2006; I had thought that, by that time, the additive convention was fairly prevalent. One possibility is that they looked at the convention of $\mathbb{G}_2$. The group $\mathbb{G}_2$ has an operation which is multiplication over a finite field (at least with any pairing operation you'd actually use), and hence is always written multiplicatively. Perhaps they decided to write the operations in $\mathbb{G}_1$ (the elliptic curve group) to be consistent with it.

$\endgroup$
7
  • $\begingroup$ @tesoke: if you think my answer is helpful, please accept it (and upvote it if you're allowed) $\endgroup$
    – poncho
    May 5, 2018 at 0:07
  • $\begingroup$ I did not know anything about this voting and so on. Thanks again. $\endgroup$
    – tesoke
    May 5, 2018 at 2:01
  • $\begingroup$ Actually it is rather common in papers on schemes or protocols that involve pairings to use multiplicative notation for the elliptic curve groups. It hepls to make the description much more compact. Also if you consider bilinear groups just as abstract objects independent of how they are implemented it does not matter much which notation you actually use. $\endgroup$
    – DrLecter
    May 5, 2018 at 18:31
  • $\begingroup$ Thanks but your comment is vague for me. Did You mean that it does not matter that we propose multiplication or power in our protocols?!!! $\endgroup$
    – tesoke
    May 6, 2018 at 0:06
  • $\begingroup$ @tesoke: no, I'm saying it doesn't matter whether we call it multiplication or power $\endgroup$
    – poncho
    May 6, 2018 at 2:00
2
$\begingroup$

A short explanation for people not trained in group theory:

A group is a set $G$ with a binary operation $\circ$, i.e. for each pair of elements $g\in G$ and $h \in G$ you have $g \circ h$ being again an element of $G$. And furthermore, this group operation needs to fulfill some properties like being associative (i.e. $f\circ(g\circ h)=(f\circ g)\circ h$), there needs to be some identity element $e\in G$ (i.e. $e\circ g=g\circ e =g$ for all $g\in G$), and there needs to be an inverse, i.e. for each $g\in G$ there is an $h\in G$ such that $g\circ h=h\circ g=e$. And with those few and simple requirements you can prove already a whole lot of nice and useful theorems.

A general group does not have to be commutative, i.e. $g\circ h$ is in general not equal to $h \circ g$. Such non-commutative groups we usually write in a "multiplicative" way, that is we write the group operation $\circ$ as multiplication. So we write $gh$ instead of $g \circ h$, we write $g^{-1}$ for the inverses, and we often write $1$ for the identity element.

In contrast, if commutativity holds (i.e. $g\circ h=h\circ g$ holds for all $g$ and $h$ from $G$) we often (but not always) write the group in an "additive" fashion, i.e. $g+h$ for the group operation, $-g$ for the inverse and $0$ for the identity element. The reason for doing it this way is, that addition is always commutative, while multiplication often is not.

The elliptic group is a commutative (also sometimes called Abelian) group, thus often written in this additive fashion. But here you also have to note that point addition in an elliptic curve is not normal geometric point addition, but this strange group operation defined by intersecting the straight line through the points with the curve and mirroring the result at the $x$-axis. And further the zero (identity) element is the "point at infinity" and $-P$ is not the "normal" geometric mirroring at the origin, but mirroring at the $x$-axis. The symbols $+$, $-$ and $0$ are only used here, because the group has this commutative structure.

People could just as well have chosen to write the elliptic curve group in a multiplicative way, with $\cdot$ for the group operation, $g^{-1}$ for the inverse, and $1$ for the identity. There are even ways people talk, where this multiplicative notion still comes out, especially when it comes to the discrete logarithm problem. In a multiplicative group its about finding some integer $k$ that fulfills $g^k=h$ for given $g$ and $h$. In an elliptic curve group its about finding $k$ such that $kP=Q$ for some given $P$ and $Q$, but both are essentially the same: $g^k=g\cdot g\cdot\dots \cdot g=g\circ g\circ\dots \circ g$ vs. $kP=P+P+\dots+P=P\circ P\circ \dots\circ P$. In both cases its just $k-1$ times the application of the group operation and you need to find that $k$.

And whether you call that group operation now $\cdot$ or $+$ is just a matter of personal preference or history or common usage in your community or whatever. For elliptic curves the nowadays standard seems to be to call the operation "point addition" while the authors behind the paper you cite prefer to use multiplicative notation. An advantage I can see in this, is that this is more in line with cryptographic algorithms that are based on modular arithmetic where multiplicative notation prevails (and where the notion "discrete logarithm problem" makes much more sense, cause in additive notation this is much more of a "discrete division problem"...)

$\endgroup$
6
  • $\begingroup$ I found this answer more confusing to beginners. Almost everybody ( I mean major articles and major books) uses point addition. If you call this point multiplication then you need to rename scalar multiplication. If some article uses multiplicative notation (interestingly the OPs article has no mention of the strings "elliptic" or "curve") It should stay there. And actually one can define a point multiplication if they can solve CDH. It is the academic community that decides this over the years as C22519 turned into X22519 for ECDH. $\endgroup$
    – kelalaka
    Feb 8, 2022 at 12:18
  • $\begingroup$ But it's not a point addition in the usual geometric sense. It's a group operation, that is commutative, and so people chose to use additive notation. However, that's a very arbitrary choice. In the OPs article multiplicative notation is used with groups and that's where probably his confusion comes from: what to do with things like $g h$, because there is no point "multiplication" like $P Q$ in elliptic curves, but only point "addition" $P+Q$. $\endgroup$ Feb 8, 2022 at 13:59
  • $\begingroup$ poncho told him in his answer and the comments, that "it doesn't matter whether we call it multiplication or power" and in my view that's very confusing for someone with a "standard" math background for whom multiplication and addition have a fixed meaning and are not as arbitrary as in group theory.. $\endgroup$ Feb 8, 2022 at 13:59
  • $\begingroup$ I think the Dr.Lecter's comment is the best; it depends on the context, though + is more general for abelian groups... $\endgroup$
    – kelalaka
    Feb 8, 2022 at 15:23
  • $\begingroup$ I still don't think its enough for people not having some knowledge of group theory or abstract algebra. It's just not natural for them to be able to "choose" whether they want to call it addition or multiplication. You have to get used to the thought that this is some abstract operation that you can call whatever you want $+$, $\cdot$, $\otimes$... That's what I wanted to get across with my answer. If you don't like it, so be it. But different people learn and understand things often in a different way, so maybe for some it's helpful... $\endgroup$ Feb 8, 2022 at 19:20

Your Answer

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

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