Thread by @gro_tsen

This thread attempts to answer the question “why do we use elliptic curves in cryptography (for things like discrete logarithms)” and I think makes a very good job at explaining it, but there is one point which is a bit glossed over. •1/12

https://twitter.com/SchmiegSophie/status/1367286254291677188

Basically what we want is a group C which is “cyclic but not trivially cyclic”, i.e., that there be an isomorphism ℤ/ℓℤ → C, easily computable (given a choice of generator of C) as well as the group operation in C, but that the reverse isomorphism be hard. •2/12

This is a bizarre quest, because in mathematics we aren't used to distinguishing isomorphic objects, even less the existence of an isomorphism in one direction from that in the other! (Of course here both exist, but one is “easy” and the other is “hard”.) •3/12

Note that the easiness of computing ℤ/ℓℤ → C follows from the easiness of computing in C (by fast exponentiation), though there is maybe the issue of computing the order ℓ itself (for elliptic curves this isn't a problem, but there's room for further discussion here). •4/12

Also, this is because ℤ/ℓℤ has some extra structure besides addition, namely, multiplication. So essentially we're looking for a cyclic group without that extra structure, because it would make computing the reverse map C → ℤ/ℓℤ easy in exactly the same way. •5/12

But anyway, elliptic curves (over finite fields) give us this sort of group C. The big question is why specifically elliptic curves? Sophie gives a very convincing explanation if we assume that C comes from algebraic geometry, … •6/12

… but I think this doesn't do justice to the question “why polynomials? why algebraic geometry?”. And, to be fair, I don't think anyone really has an answer to this question! I see it as a mystery. •7/12

https://twitter.com/SchmiegSophie/status/1367286265968689152

I mean, groups (arising as symmetries (automorphisms) of various structures) abound nearly everywhere in mathematics, and cyclic groups are the simplest of them. So we might expect to have lots of examples of “cyclic but not trivially cyclic” groups. •8/12

Galois groups? Class groups? Drinfel'd modules? Subgroups generated by elements of large orders in linear algebraic groups? Cohomology? Even if we don't look too far away, apparent candidates abound. Yet all seem to fail for various reasons. •9/12

I get the point that polynomials (hence algebraic groups) are something natural to look at because it's easy to add and multiply numbers, but there are all sorts of other computational structures in mathematics which “might have” provided cyclic groups to work with. •10/12

This is all the more mysterious in that we aren't looking for a complicated structure with a lot of conditions: on the contrary, we are looking for an absence of complicated structure: just a cyclic group in “pure” form, that we can compute in. •11/12

I really don't have an answer to why we end up with such a dearth of “cyclic but not trivially cyclic”, and I don't think anyone has a good answer. I see it as a rather profound mystery. Is it our ignorance or is there a deeper reason? [See also:

https://twitter.com/gro_tsen/status/1096010514973511681

‌] •12/12