I’ve been meaning to write about isogeny-based crypto for a long while. This area has steadily become more and more active and there are now many researchers working seriously on it. The main motivation is its potential to provide a key exchange primitive that is efficient enough for practical deployment, yet potentially secure against an adversary with a quantum computer.
The first suggestions to use isogenies in crypto were due to Couveignes (in a talk in 1997), Charles, Lauter and Goren (a hash function proposed in 2005) and Rostovtsev and Stolbunov (eprint, 2006). But the biggest impetus came from the paper by David Jao and Luca De Feo in PQCrypto 2011. This paper presents the supersingular isogeny Diffie-Hellman (SIDH) key exchange scheme that has potential to be post-quantum secure.
The first thing to note is that the Jao and De Feo scheme is based on supersingular elliptic curves. Readers might think: Supersingular curves are weak for classical crypto, and ECDLP is broken by Shor’s algorithm, so how can this be a good idea? The point is that we are no longer basing security on discrete logarithms, or any “algebraic” property of a specific elliptic curve. Instead, the basic structure is group homomorphisms between curves.
There are several reasons to be interested in supersingular isogeny crypto.
- The pool of potential post-quantum assumptions is very small, and so all avenues need to be fully explored and tested.
- There has been a huge body of knowledge and experience developed over the last 20 years in support of elliptic curve crypto, and so it is natural to try to continue using elliptic curves if possible.
- Some of the underlying computational problems have already been considered by researchers in classical elliptic curve crypto and computational number theory, and so there is some good evidence that the assumptions are reasonable, at least against classical computers.
- It is straightforward to choose parameters to achieve a given security level. In contrast, selecting parameters for lattice crypto that achieve a given security level is still problematic. For example, different models of how the BKZ algorithm performs lead to quite different results (although it is possible to make conservative choices that still lead to a practical scheme).
However, there are also several serious concerns about supersingular isogeny crypto.
- One of the most serious concerns is that the systems have not been sufficiently scrutinised by researchers in quantum algorithms. A contributing factor is that there are significant mathematical preliminaries needed to fully understand isogeny crypto, and so it is not an easy field for non-experts to work in.
- Another concern, especially in contrast to lattices, is that isogenies are not a very “expressive” tool. Lattice crypto has provided a rich suite of cryptographic functionalities including encryption, signatures, id-based crypto, homomorphic encryption, and more. On the other hand, the only practical isogeny crypto primitive known is key exchange. We do not even have a practical digital signature scheme based on isogenies (see Yoo et al in FC2017 and this paper, which is to appear at Asiacrypt 2017), and signatures are a relatively basic primitive.
The main conceptual idea of isogeny key exchange is the following: In the original Diffie-Hellman protocol Alice sends to Bob 
An isogeny is a group homomorphism from an elliptic curve 
The key exchange protocol is then seen to be analogous to the Diffie-Hellman protocol. Fix an elliptic curve 
One reason to choose supersingular elliptic curves is that it makes key generation and some computational and theoretical aspects of the protocol much more simple and efficient than if using other elliptic curves.
The fundamental computational problem underlying isogeny crypto is the problem: Given two elliptic curves 
However, it is important to note that the Jao-De-Feo key exchange scheme relies on a weaker variant of this problem. In the scheme one gets two elliptic curves 
In conclusion, isogeny crypto is a very interesting and active area of research in crypto. However, more investigation is needed by researchers in quantum algorithms before we can be confident that it really is post-quantum secure. If you wish to learn more about the subject then I recommend this paper for a tutorial on the basic theory, and for a discussion of computational problems of interest.
— Steven Galbraith
ellipticnews 
Hi Steven, what is the 97 Couveignes talk you have in mind? Best, JPF
This is documented in a paper called “Hard Homogeneous Spaces” by Couveignes. He writes “This note was written in 1997 after a talk I gave at the séminaire de complexité et cryptographie at the École Normale Supérieure”.
I don’t think that isogeny based crypto is secure. In all the examples I’ve seen so far, the actual isogeny was quite a simple function, e.g. the x-coordinate on the original curve was mapped to some value (a*x+b)^2 mod p (p a suitable prime) becoming the new x-coordinate on the image curve. Imo it should be possible to recover the coefficients (a, b in that example), since an isogeny works like a homomorphism. If you know one point A and its image under the isogeny, lets call it i(A), you can create an arbitrarily amount of pairs of points and their images, just by adding up the As on the original curve and the i(A)s on the image curve. So it should be possible to put up some system of equations and calculate a and b. This would also work, if the isogeny was a rational function, you’d just write it as e.g. (a*x^2+b*x+c)/(d*x^2+e*x+f). In the worst case, if you’d wrongly assumed a rational type function, d and e would become zero, f would become 1. Of course you could make things more complicated by raising the degree of the polynomials, e.g. degree 4 and mixing x and y in the functions, but it would still be a polynomial task to retrieve all the coefficients.
So either I’m just making a serious error in reasoning, or isogeny based crypto does have serious issues, maybe you could save it by making the actual isogeny a very very complicated function.
Thanks for your comment on the blog. What you are saying is all true. The problem is that what is published is the end point of a long sequence of isogenies. Each isogeny by itself has small degree, and the equations have small degree. But the composition has exponential degree. Since the attacker only sees the points at the beginning and the end then they have to solve an exponentially large system of equations.
If one accidently leaked the intermediate values (eg from a side-channel attack or other) then the system would be insecure.
This is all well-known to the experts, see Note (1) in Section 7.1 of https://eprint.iacr.org/2017/774
Yes, maybe I’ve been too superficial. I’m neither a student nor an “official” scientist or researcher, and elliptic curves and isogenies aren’t my main interest. So I’m hoping, that I’m not making a complete fool out of myself here. Anyway, I’m seeing this as a chance to learn something.
My other approach to SIDH would have been finding two different points (on the original curve), which would be mapped to the same point on the image curve, so that I could calculate one element of the kernel of the isogeny. Let us assume, there is a point A on the original curve with order o(A), mapped to the point B=i(A) on the image curve, and the order of its image would be smaller than the order of A, i.e. o(B)<o(A), then it would be quite easy to find two points on the original curve with the same image. I'd multiply A on the original curve with a factor k1, o(B)<k1<o(A). Now set k2 = k1 mod o(B). The points A*k1 and A*k2 wouldn't be identical and still be mapped to the same point B. Since this would be way too easy, I presume that the order of the images can't be smaller than the order of the original points. On the other hand, how would you then get a kernel with more than one element?
Yes that would be an attack. This is *exactly* why in SIDH we publish the images of points of order 3^m along a 2^n isogeny. It would be totally insecure to publish the image of points of order 2^n.
Slightly modified approach: I’ve got a point A on the original curve, which is mapped to B on the image curve. Assuming that the order of B, o(B), is divisible by 3, while o(A) isn’t. Also o(B) shall not be divisible by 2. Now I choose two points A1 and A2, A1=3*A and A2=2*A, which are mapped to points B1 and B2, B1=i(A1)=i(3*A)=3*i(A) and B2=i(A2)=i(2*A)=2*i(A).
I’d like to find a factor k on the image curve, so that B1=k*B2, i.e. 3*i(A)=k*2*i(A). If you know the order of B, o(B), you can simply calculate a value for k, which would correspond to 3/2 mod o(B). Now what I’d like to do is bring the value of k (as a huge integer) back to the original curve. I’d assume, that 3*A and k*2*A would be the same point on the original curve, othwerwise we already had a candidate for a kernel element. Then I’d put up the equation 3*A=k*2*A (on the original curve) and divide by 3, so that A=k/3*2*A. I can divide by 3, since the order of A isn’t divisible by 3, so I can multiply with the inverse of 3, without having to adapt the modulus. k as a huge integer already contains a factor 3, since o(B) is divisible by 3, so I wouldn’t even have to mess with inverses on k. All I’d have to do is to cancel a factor 3 throughout the equation.
Now the interesting question, if we are lucky and k/3*2 is smaller than o(A), then the two points can’t be identical, can they? If so, the assumption, that the two points were identical, was wrong and we’d have a candidate for a nontrivial kernel element. The factor 3 (in the starting equation) was chosen more or less arbitrarily, I could have set it to 9, 27, 81,…, as long as it would still be a divisor of o(B). Also the factor 2 was chosen arbitrarily, the only issue that may arise, would be, if o(B) was divisible by 2, then you couldn’t write k as 3/2 mod o(B).
Hello,
I don’t really have any spare time for this. So thus will be my final reply.
> I’ve got a point A on the original curve, which is mapped to B on the image curve.
> Assuming that the order of B, o(B), is divisible by 3, while o(A) isn’t.
The map is a group homomorphism. So if [N]A = 0 and B = phi(A) then [N]B = 0.
Hence the order of B must be a factor of the order of A (maybe equal).
The order of B can’t be divisible by a new prime.
Steven