Improved torsion-point attacks on SIDH variants

Victoria de Quehen*, Péter Kutas, Chris Leonardi, Chloe Martindale, Lorenz Panny, Christophe Petit, Katherine E. Stange

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Downloads (Pure)


SIDH is a post-quantum key exchange algorithm based on the presumed difficulty of finding isogenies between supersingular elliptic curves. However, SIDH and related cryptosystems also reveal additional information: the restriction of a secret isogeny to a subgroup of the curve (torsion-point information). Petit [31] was the first to demonstrate that torsion-point information could noticeably lower the difficulty of finding secret isogenies. In particular, Petit showed that “overstretched” parameterizations of SIDH could be broken in polynomial time. However, this did not impact the security of any cryptosystems proposed in the literature. The contribution of this paper is twofold: First, we strengthen the techniques of [31] by exploiting additional information coming from a dual and a Frobenius isogeny. This extends the impact of torsion-point attacks considerably. In particular, our techniques yield a classical attack that completely breaks the n-party group key exchange of [2], first introduced as GSIDH in [17], for 6 parties or more, and a quantum attack for 3 parties or more that improves on the best known asymptotic complexity. We also provide a Magma implementation of our attack for 6 parties. We give the full range of parameters for which our attacks apply. Second, we construct SIDH variants designed to be weak against our attacks; this includes backdoor choices of starting curve, as well as backdoor choices of base-field prime. We stress that our results do not degrade the security of, or reveal any weakness in, the NIST submission SIKE [20].

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2021
Subtitle of host publication41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings, Part III
EditorsTal Malkin, Chris Peikert
Number of pages39
ISBN (Electronic)9783030842529
ISBN (Print)9783030842512
Publication statusPublished - 11 Aug 2021
Event41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12827 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online

Bibliographical note

Funding Information:
Author list in alphabetical order; see culture/CultureStatement04.pdf. Lorenz Panny was a PhD student at Technische Uni-versiteit Eindhoven while this research was conducted. Péter Kutas and Christophe Petit’s work was supported by EPSRC grant EP/S01361X/1. Katherine E. Stange was supported by NSF-CAREER CNS-1652238. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET) and in part by NWO project 651.002.004 (CHIST-ERA USEIT). Date of this document: 2021-06-25. ©c IACR 2021. This article is the final version submitted by the author(s) to the IACR and to Springer-Verlag on June 25, 2021. The version published by Springer-Verlag is available at <DOI>.”.

Publisher Copyright:
© 2021, International Association for Cryptologic Research.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Improved torsion-point attacks on SIDH variants'. Together they form a unique fingerprint.

Cite this