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  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  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 , first introduced as GSIDH in , 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 .
|Title of host publication||Advances in Cryptology – CRYPTO 2021|
|Subtitle of host publication||41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings, Part III|
|Editors||Tal Malkin, Chris Peikert|
|Number of pages||39|
|Publication status||Published - 11 Aug 2021|
|Event||41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online|
Duration: 16 Aug 2021 → 20 Aug 2021
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||41st Annual International Cryptology Conference, CRYPTO 2021|
|Period||16/08/21 → 20/08/21|
Bibliographical noteFunding Information:
Author list in alphabetical order; see https://www.ams.org/profession/leaders/ 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>.”.
© 2021, International Association for Cryptologic Research.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)