Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- post-quantumisogeny-based cryptographyendomorphism rings(B-)SIDH
- Contact author(s)
-
simon-philipp merz 2018 @ rhul ac uk
p kutas @ bham ac uk
takoboris fouotsa @ uniroma3 it - History
- 2022-10-23: last of 3 revisions
- 2021-02-12: received
- See all versions
- Short URL
- https://ia.cr/2021/153
- License
-
CC BY