Finding the subgroup in isogeny-based cryptography

Question

Isogeny-based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is theorem:

Elliptic curves are isogenous over $F_p$ if and only if they have equal number of points.

Recently, isogeny based public key methods are widely used in articles. This methods are implemented in computer systems in milliseconds and in android systems in seconds. This show that in future we can use such post-quantum cryptographic systems in practical world.

I studied many articles about this method, and I saw only mathematical methods, not practical methods or source code. In program such as the MAGMA we can find all isogenous curves with given curves defined over rational field, but I looking for finite field. Also in sage we can find $l$-isogeny with subgroup of order $l$, but in several time our defined curve have not any subgroup with order $l$.

This is one of interesting article. In this article we have some computational example (page $15$). Can you help me fo understand this example. When I send mail to its authors I face with mail error.

How can we find cyclic subgroup of order $l$ of the elliptic curve $E(\overline{\mathbf F_p})$, over the algebraic closure of the finite field?

Answer 1

While there is a sub-exponential attack to compute isogenies on ORDINARY elliptic curves (the basis for the Rostovev and Stulbunov paper that you reference) there is not (yet at least) a sub-exponential attack to compute isogenies on SUPERSINGULAR elliptic curves. The cryptosystem proposed by DeFeo, Jao, and Plut back in 2011 is based on Supersingular rather than ordinary elliptic curves. Microsoft Research recently published a paper on this cryptosystem. The paper contains a good overview of research on this problem to date. An preprint of Microsoft's paper is found here.

Answer 2

There is a quantum sub-exponential time algorithm to extract the private keys from the system you cite. Another paper by Luca De Feo, David Jao, and Jerome Plut improves upon that system, addresses the attack, and gives references to all this, so read that one.

All these post-quantum systems should be considered suspect because recent work has even produced quantum attacks against some symmetric crypto systems! There is good discussion and references here but the important take away is : Although these attacks on symmetric systems assume an unrealistic adversary, that adversary is not unrealistic for a public key system, so periodicity in the system could render it vulnerable to new quantum algorithms. I think this applies both to isogeny based systems as well as Ring-LWE based systems.

At the same time, all these post-quantum systems remain interesting because they admit slightly different homomorphic properties, meaning they might be useful in different situations.