Paper 2021/153

On the Isogeny Problem with Torsion Point Information

Tako Boris Fouotsa, LASEC-EPFL, Switzerland
Péter Kutas, University of Birmingham, UK, Eötvös Loránd University, Hungary
Simon-Philipp Merz, Royal Holloway, University of London, UK
Yan Bo Ti, DSO, Singapore
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.