Improved torsion-point attacks on SIDH variants

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

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

9 Downloads (Pure)

Abstract

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
PublisherSpringer
Pages432-470
Number of pages39
ISBN (Electronic)9783030842529
ISBN (Print)9783030842512
DOIs
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

Conference

Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online
Period16/08/2120/08/21

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this