Constructing elliptic curve isogenies in quantum subexponential time

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

Constructing elliptic curve isogenies in quantum subexponential time, by Andrew M. Childs, David Jao and Vladimir Soukharev (arXiv:1012.4019).

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

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Constructing elliptic curve isogenies in quantum subexponential time

  1. David Jao says:

    As an author of the paper, I thought I’d add some remarks concerning Kuperberg’s algorithm.

    Kuperberg’s algorithm only solves the special case of the hidden shift problem where the functions are injective. So that is why Kuperberg’s algorithm is not so well known — it doesn’t show up if you just look for general quantum algorithms for hidden shift, and Stolbunov (for example) cited the hidden shift problem in his paper, but not Kuperberg’s algorithm. Also, to the best of my knowledge, our paper is the first result that uses Kuperberg’s algorithm to solve a non-blackbox computational problem. We plan to clarify these points in the next draft of our paper.

  2. First of all, I’m always happy to be cited! I think that the biggest reason that one might not have heard of my algorithm, is that it’s a quantum algorithm. As far as injectivity goes, it’s actually good enough for the functions to only be approximately injective in some statistical sense. There must be some such assumption, because in the extreme case where they are as far as possible from injective, say Kronecker delta functions, then you are reduced to blind guessing to find the hidden shift. Now, blind guessing for a quantum computer is better than for a classical computer, by Grover’s algorithm, but Grover’s algorithm is known to be optimal and this takes exponential time.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s