Paper 2021/153
On the Isogeny Problem with Torsion Point Information
Abstract
It has recently been rigorously proven (and was previously known under certain heuristics) 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, Petit, Shani and Ti 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 of degree approximately $p^{1/2}$. The method does not extend to other SIDH-type schemes, where secret isogenies of larger degree are used and 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. We show that this system will have a unique solution that can be lifted to the integers if some mild conditions on the parameters are satisfied. This lift then yields the secret isogeny. One consequence of this work is that the choice of the prime $p$ in B-SIDH is tight. Finally, we show that our reduction still applies for SIDH variations deploying recently proposed countermeasures against a series of classical polynomial time attacks against SIDH.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in PKC 2022
- Keywords
- post-quantum isogeny-based cryptography endomorphism rings (B-)SIDH
- Contact author(s)
-
takoboris fouotsa @ uniroma3 it
p kutas @ bham ac uk
simon-philipp merz 2018 @ rhul ac uk
yanbo ti @ gmail com - 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
BibTeX
@misc{cryptoeprint:2021/153, author = {Tako Boris Fouotsa and Péter Kutas and Simon-Philipp Merz and Yan Bo Ti}, title = {On the Isogeny Problem with Torsion Point Information}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/153}, year = {2021}, url = {https://eprint.iacr.org/2021/153} }