## Constructing elliptic curve isogenies in quantum subexponential time

I thought I’d say a few things about the following new paper:

## Background on the isogeny problem

Let E1 and E2 be elliptic curves over a finite field F_q with the same number of points. Then there is an isogeny from E1 to E2 over F_q. What is an isogeny? An isogeny is a function from E1 to E2 which is both a group homomorphism and a geometric map (i.e., given by rational functions). The isogeny problem is to explicitly compute an isogeny from E1 to E2.

The isogeny problem is interesting for several reasons. First, it tells something about the difficulty of the elliptic curve discrete logarithm problem among curves with the same number of points (an isogeny is a group homomorphism, so it maps an instance of the DLP in the group E1( F_q ) to an instance of the DLP in E2( F_q )). It is natural to wonder whether the ECDLP is equally hard for curves with the same number of points. If the isogeny problem was easy to solve then this would be true. The first paper about this topic was my paper Constructing isogenies between elliptic curves over finite fields (relying heavily on David Kohel’s PhD thesis). A more useful formulation of the result was given by Jao, Miller and Venkatesan in the paper “Do all elliptic curves of the same order have the same difficulty of discrete log?”. You can download this paper from David Jao’s webpage.

A second motivation for the isogeny problem is that there have been various cryptosystems proposed which rely on it, for example:

We now distinguish between supersingular curves and ordinary curves. The supersingular case (used for the hash function) is quite different, and we will not discuss it further here.

In the ordinary case there is one serious problem: the endomorphism rings End(E1) and End(E2) are orders in some imaginary quadratic field. The index of End(E1) in the maximal order is called the conductor. If there is a very large prime dividing the conductor of E1, but not the conductor of E2 (or vice versa) then the isogeny problem is very hard. Interestingly, there seems to be no way to efficiently generate pairs of elliptic curves with this property. Hence, from a computational point of view, it is reasonable to assume that this problem does not arise; in which case we say that the conductors are “comparable”.

For elliptic curves with comparable conductor I gave an algorithm in 1999 which requires exponential (essentially O( q^{1/4} )) time and space (this also works for supersingular curves). For ordinary elliptic curves, my paper with Hess and Smart gives a low storage algorithm with the same exponential running time. Note that these algorithms are much faster than the best algorithms to solve the ECDLP (which require O( q^{1/2 } ) operations); hence the isogeny problem (at least, for comparable conductors) really is “easier” than the ECDLP.

## The new paper

As we have seen, the previous best methods for the isogeny problem require exponential-time. The new paper improves this to subexponential-time for elliptic curves with comparable conductor, which is a great result. (The results are conditional on a generalised Riemann hypothesis, but that doesn’t bother me at all.) The approach is to combine subexponential-time algorithms for computing general isogenies (essentially the ideas of Galbraith-Hess-Smart, but using improvements due to Bisson-Sutherland and Jao-Soukharev together with some technical innovations in the paper) with Kuperberg’s quantum hidden shift algorithm. I had never heard of Kuperberg’s algorithm before. But it seems that the action of the ideal class group on the set of isomorphism classes of elliptic curves with a given endomorphism ring fits the framework of that result.

A consequence of the paper of Childs, Jao and Soukharev is that cryptosystems whose security relies on the difficulty of isogeny computation for ordinary elliptic curves seem to be less attractive.

It should be stressed that the new paper has no implications for the Charles-Goren-Lauter hash function, as the hash function is based on the supersingular isogeny graph. The new paper also does not solve the problem of conductors which are not comparable.

As mentioned above, with classical computation, the isogeny problem is “easier” than the ECDLP. Whereas with quantum computation the ECDLP is polynomial-time, whereas the isogeny problem is only subexponential-time. From this I deduce that I have no intuition about quantum algorithms!

— Steven Galbraith