Score:2

Why points at infinity are relevant in Twisted Edwards elliptic curves?

rs flag

I've been navigating through many of StackExchange's history questions about point at infinity, and there's something that still doesn't "click" for me.

Let me share my understanding (and its logic) and maybe become apparent where I fail.

Let's say I have an elliptic curve equation, particularly a Twisted Edwards Curve equation. The first thing to note, contrary to 90% of texts on the internet, the identity point isn't the point at infinity. (I think it's true in other kind of curves).

OK, so if the points at infinity aren't relevant to define the identity element, the question I'm asking myself is: why are they relevant at all?

I think in this case (Twisted Edwards), points at infinity are solutions in the equation in projective form with $Z=0$. (Is this correct?).

I'd guess we call those solutions "points at infinity" because we can't project them to $Z=1$ (i.e: affine coordinates). (Right?).

If I set $Z=0$ in the projective form of Twisted Edwards $(x^2+y^2).z^2=z^4+d.x^2.y^2$, what I get is $0=d.x^2.y^2$, thus any point $(x, 0, 0)$ or $(0, y, 0)$ is a point at infinity. (Right?)

OK, so my understanding of "why is this relevant?", is that we want to be sure that when we apply the group law in projective form, we would like to never get one of these points as they don't map to affine coordinates. (Right?).

Is that the reason why Twisted Edwards curve might want to find a way to avoid points at infinity?

honzaik avatar
cn flag
I am not sure what you mean by "relevant". I haven't really tried to implement EC arithmetic so I am not really experienced in this field but my understanding is that Twisted Edwards curves having this advantage of neutral point (wrt to the group operation) being affine makes the addition formulas simpler (there are some restrictions on the curve parameters $a,d$) without special cases (those formulas are "complete"). Therefore, they are considered practically more secure (less chance to mess up).
Enthusiast avatar
rs flag
@honzaik, I mean that if you do arithmetic in projective form, I'd guess that you should understand which are the points at infinity. Since you can't map them to affine point. So I guess that's usually "a problem". (Again, I'm not an expert! I'm trying to validate what a usual analysis involves and why)
honzaik avatar
cn flag
Well, if you add two projective points which correspond to an affine point (their coordinate $Z\neq 0$) then it is proven that the result of the addition is also a point with $Z\neq 0$ therefore "an affine point". The proof is here https://eprint.iacr.org/2007/286.pdf (Theorem 3.3). Of course it has the assumptions on the curve parameters that need to be met. Is this what you mean? We do not "care" about points $Z=0$ because they never come up in the calculation. It's been a while since I studied this so I hope I am spreading some misinformation :`)
Enthusiast avatar
rs flag
@honzaik, the problem is that is assuming `a` is a square and `d` isn't a square. In those cases, as you said before citing Wikipedia, the formulas are complete. So, in that case, it's true that "you're always adding affine points, and getting affine points". (Actually that Theorem assumes `a=1` which is a square). So in other cases where that assumption doesn't hold, then you might have undetermined points. So.. I guess you have to take care of them in projective form.
honzaik avatar
cn flag
you're right. If those conditions on $a$ or $d$ are not met then those formulas aren't proven complete therefore you might encounter projective points (I guess it would depend on the specific curve). I guess the relevancy point here is that AFAIK all "relevant" (Twisted) Edwards curves used in crypto fulfil those assumptions (Curve25519 or Ed448-Goldilocks) therefore points at infinity are not mentioned. I would guess those on https://safecurves.cr.yp.to/ also, if they are Edwards.
I sit in a Tesla and translated this thread with Ai:

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.