by less_less | 2025-05-20 11:57:32+00:00
The theory of elliptic curves goes amazingly deep. Scratching the surface slightly more, to fill in the article's "ignore the labels like 2P":

Intersecting the curve with lines the way the author does is, perhaps shockingly, a commutative group operation, known as point addition. You define this operation by saying that the three points A,B,C on a line sum to zero: that is A+B+C=0 or in other words, A+B = -C. Reflecting across the curve's line of symmetry is negation (there's an alternative definition that extends to curves without reflection symmetry). Combining the two defines an operation A+B which adds two points on the curve and gives a third one: draw the line from A to B, intersect it with the curve to find a point -A-B (using the same type of formula given in this article) and then reflect it to get A+B. This addition operation obviously commutes (meaning, the line between A and B is the same as the line between B and A), but surprisingly it also associates and you get a group operation.

(For math olympiad nerds out there: so the union of a conic and a line is also a bivariate cubic equation. You can carry out the same "addition" operation there. Again the operation clearly commutes. But it also associates! This is basically Pascal's theorem.)

The theory of elliptic curves is also the basis of elliptic curve cryptography. In that case, instead of the curve being over the reals, all the calculations are done mod some prime p, which destroys structure based on continuity and prevents the numbers from becoming too large. There are a bunch of subtleties here but the key is that you can still straightforwardly compute addition in this context, with basically the same formulas. Then from addition you can get n*A, both for small integers n (eg 5*A = A+A+A+A+A) but also for large n (e.g. 2*A = A+A; 66*A = 2*2*2*2*2*2*A + 2*A). This "scalar multiplication" operation is a one-way operation for appropriately chosen curves: it's easy to calculate n*A from (n,A), but as far as we know it is hard to calculate n from (A,n*A) ... at least if you can't build a large quantum computer.

This gives you mix of easy operations (eg, addition and scalar multiplication) plus problems believed to be hard, which is a great starting point to build cryptography. There are a lot of important technical details, though fewer than with the new lattice schemes.

(Further comment on the olympiad thing: so you can do this with conic+line too, extending from addition to multiplication and using the same formulas mod p. But it's not as good: it's not hard to find a projection that sends the line to infinity and the conic to the unit circle or similar, and then the group operation becomes equivalent to multiplying the points' coordinates as complex numbers or similar. If the group operation is equivalent to multiplication, then scalarmul becomes equivalent to exponentiation, which ends up being in Fp or Fp^2 depending on some Legendre symbol or other. Exponentiation is still potentially secure: it's basically classical Diffie-Hellman. However, more attacks are known on exponentiation in Fp or Fp^2: the attacks don't outright break it but you need p to be much bigger.)

Edit: unescaped stars make italics.