June 16, 2021


Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

On the Isogeny Problem with Torsion Point Information, by Tako Boris Fouotsa and Péter Kutas and Simon-Philipp Merz

It is well known that the general supersingular isogeny problem reduces to the supersingular endomorphism ring computation problem. However, in order to attack SIDH-type schemes, one requires a particular isogeny which is usually not returned by the general reduction. At Asiacrypt 2016, Galbraith et al. presented a polynomial-time reduction of the problem of finding the secret isogeny in SIDH to the problem of computing the endomorphism ring of a supersingular elliptic curve. Their method exploits the fact that secret isogenies in SIDH are short, and thus it does not extend to other SIDH-type schemes where this condition is not fulfilled.

We present a more general reduction algorithm that generalises to all SIDH-type schemes. The main idea of our algorithm is to exploit available torsion point images together with the KLPT algorithm to obtain a linear system of equations over a certain residue class ring. Lifting the solution of this linear system yields the secret isogeny. As a consequence, we show that the choice of the prime $p$ in B-SIDH is tight.