You are looking at a specific version 20210212:074053 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.