Score:1

Why does point addition work on EC curves?

in flag

This may be more of a math question but I cannot find an intuitive answer.

On an EC curve why is 2P+2P equal to P+P+P+P?

The addition operation seems to a layman as some arbitrary sequence of steps. Draw a line here, flip the y coordinate, and so on. And yet point doubling twice brings up the same point. How is this so? (how is it that point addition is associative)

kelalaka avatar
in flag
[Scalar multiplication](https://crypto.stackexchange.com/a/68595/18298). Doubling brings up the same point? Not clear. See the [Group Law](https://crypto.stackexchange.com/q/66288/18298) where we have that the group law has a geometric maning. Hard to find one dupe!
kelalaka avatar
in flag
If those answer doesn't resolve your points, please indicate.
Frank avatar
in flag
@kelaka ok it points me in the right direction. I need to look into 'groups'. Still i cannot yet understand how this seemingly arbitrary operation was created that 2P added yields the same as P added 4 times
Frank avatar
in flag
In other words, how is it that that operation is associative?
kelalaka avatar
in flag
Elliptic Curves Number Theory and Cryptography Second Edition LAWRENCE C. WASHINGTON, section 2.4 provides a great deal for associative, it is a long process, you might assume that it is true if you are not a Mathematician.
Frank avatar
in flag
@kelalaka Thanks. I am not a mathematician, but I don't mind plunging head first into the maths. I tried quantum mechanics recently and ended up going from almost zero maths knowledge to a working understanding. I think it is important because EC crypto is the underpinning for many new crypto systems, the distributed ledger technologies, which IMO form a nascent industry akin to the 90s Web, poising itself to replace all traditional financial infrastructure. The philosophical basis for this movement is decentralisation. But how can this be if EC crypto is understood by a tiny few?
Frank avatar
in flag
@kelaka On the other hand, I would rather see the pinnacle of trust be academic institutions than banks. I think it would be of monumental value if someone could put together an intuitive explication of all the fundamental components of EC crypto, including why one should or should not trust them, the potential backdoors, the history, etc.
kelalaka avatar
in flag
Also, you might be interested in the [Elliptic Tales](https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number/dp/0691151199) as a gentle introduction. And one of the many answers from math.se; [Group Law for an Elliptic curve](https://math.stackexchange.com/q/5167/338051)
Score:4
kr flag

There do exist proofs of the associativity of the elliptic curve group law based on the geometric definition (together with some results in projective geometry), but they are definitely non trivial. Cassels' little book on elliptic curves contains such a proof (and it's a nice introduction to the theory of elliptic curves in general, so I would definitely recommend it).

The most elementary way of proving associativity is of course to just write down the coefficients for $(P+Q)+R$ and $P+(Q+R)$ and observe that they are the same, but I certainly agree that this doesn't explain anything.

There are more highbrow approaches that explain the reason why the addition law looks like that, but they require more math. The underlying argument goes like this: there is an additive group associated to any algebraic curve called the group of degree-zero divisors, and it is actually a group “variety” in the sense that it can be represented by a geometric object (called the Jacobian variety) with the group operations given by geometric maps. Moreover, the dimension of that geometric object turns one to be the genus, a number which is $1$ exactly for elliptic curves, or more properly, for things that become elliptic curves once you fix a distinguished point. And once you fix that distinguished point, there is a simple way to map any point on the curve to a degree-zero divisor. This gives you a map between the original curve and the Jacobian, which turns out to be an isomorphism, and so the group law on the original elliptic curve comes from the natural group law on the Jacobian, for which all the group properties hold trivially. Due to how divisors behave, it is also easy to see that three points sum to zero if and only if they are on a line, so you recover the traditional geometric description.

Making the above entirely rigorous requires a good amount of algebraic geometry machinery, but it is in some sense the correct way to see where associativity comes from. (Historically, things came about differently, via analytic methods that extended the addition laws from trigonometric functions to so-called elliptic functions, but that historical way doesn't map very well to the finite field setting that we use in cryptography).

Frank avatar
in flag
Many thanks Mehdi. Well I now have a rabbit hole of maths to dive into that was created by a dinosaur sized rabbit, but at least i now know that it is the correct rabbit!
Frank avatar
in flag
Book ordered!
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.