### 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.

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
See all versions
Short URL
https://ia.cr/2021/153

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},
note = {\url{https://eprint.iacr.org/2021/153}},
url = {https://eprint.iacr.org/2021/153}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.