Cryptology ePrint Archive: Report 2021/153

On the Isogeny Problem with Torsion Point Information

Boris Fouotsa Tako and Péter Kutas and Simon-Philipp Merz

Abstract: 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 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.

Category / Keywords: public-key cryptography / post-quantum, isogeny-based cryptography, endomorphism rings, (B-)SIDH

Date: received 11 Feb 2021

Contact author: simon-philipp merz 2018 at rhul ac uk, p kutas@bham ac uk, takoboris fouotsa@uniroma3 it

Available format(s): PDF | BibTeX Citation

Version: 20210212:074053 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]