What is an isogeny? (2019)

The previous post said that isogenies between elliptic curves are the basis for a quantum-resistant encryption method, but we didn’t say what an isogeny is.

It’s difficult to look up what an isogeny is. You’ll find several definitions, and they seem incomplete or incompatible.

If you go to Wikipedia, you’ll read “an isogeny is a morphism of algebraic groups that is surjective and has a finite kernel.” The possibly misleading term here is “algebraic group.” It may sound like they’re throwing in the term “algebraic” for clarification as if to say “a group like the kind you’d talk about in math, as opposed to the kind of group you might talk about somewhere else like in sociology.” An algebraic group is indeed a group, but one with additional structure. A “morphism” is a structure-preserving map, and so here “morphism” means a function that preserves the algebraic and topological structure of an algebraic group.

The algebraic groups we care about are elliptic curves, so let’s specialize to elliptic curves. For the rest of this post all definitions and theorems will come from Handbook of Elliptic and Hyperelliptic Curve Cryptography by Cohen and Frey. This book defines isogeny implicitly by defining what it means for two curves to be isogenous.

Two curves E/K and E‘/K are isogenous over K if there exists a morphism φ : E → E‘ with coefficients in K mapping the neutral element of E to the neutral element of E‘.

Here K is the field the curves are defined over. The neutral element is the identity element of the curve as a group, the point at infinity.

Something strange is going on here. The definition talks about two curves being isogenous. That sounds like a symmetric relationship, but the definition is not symmetric. It specifies the existence of a morphism in one direction but not in the other. But the book goes on to explain that if an isogeny exists in one direction, there necessarily exists a unique isogeny in the opposite direction, the dual isogeny, though it’s not obvious why this should be.

Another puzzling thing is that it doesn’t seem to take much for a function to be an isogeny, just map the group identity to the group identity. But there are other requirements implicit in the statement that φ is a morphism in the context of algebraic groups. Cohen and Frey do not require φ to be a homomorphism, as some authors do, but they point out that in fact φ will turn out to be a group homomorphism. They say “for more background on isogenies, we refer to section 4.3.4.” OK, let’s go there.

In that section the authors say that a morphism between Abelian varieties (a special case of algebraic groups which includes elliptic curves) is an isogeny if and only if it is surjective and has a finite kernel. That seems like a much stronger requirement than the definition above. However, in this context simply requiring a morphism to map the group identity to the group identity implies that the morphism will be surjective and have a finite kernel, and vice versa.

An isogeny is not an isomorphism

An isogeny is a group homomorphism, but not an isomorphism, not in the modern usage of the term. Historically, however, the term “isomorphism” was used for what we now call an isogeny.

We said above that the existence of an isogeny in one direction implied the existence of a dual isogeny in the opposite direction. These functions are not inverses of each other: their composition is not the identity. However, their composition does have a simple form: it is multiplication by an integer n, called the degree of the isogeny. (Multiplication here means repeated group addition, i.e. the composition takes an element x to the sum of n copies of x using the group law on the elliptic curve.)

Example

Cohen and Frey give the example

of an isogeny of degree 2 between the elliptic curves

y² = x³ + 1132x + 278

and

y² = x³ + 500x + 1005

over the field with 2003 elements. The curves are not isomorphic because the group structure of the former is a cyclic group and the group structure of the latter is not.

Incidentally, there is a theorem that says two elliptic curves over a finite field are isogenous if and only if they have the same number of points. So a brute-force approach to showing that the curves above are isogenous would be to show that they both have the same number of points. And indeed, both have 1956 points.

More ECC posts

from Hacker News https://ift.tt/YPigLFf