Paper 2020/633

Improved torsion-point attacks on SIDH variants

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

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 [30] 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 [30] 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 [16], 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 [19].

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in CRYPTO 2021
Keywords
supersingularisogenycryptanalysistorsionSIDHSIKE
Contact author(s)
chloe martindale @ bristol ac uk
kstange @ math colorado edu
History
2021-07-14: last of 2 revisions
2020-06-03: received
See all versions
Short URL
https://ia.cr/2020/633
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/633,
      author = {Victoria de Quehen and Péter Kutas and Chris Leonardi and Chloe Martindale and Lorenz Panny and Christophe Petit and Katherine E.  Stange},
      title = {Improved torsion-point attacks on {SIDH} variants},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/633},
      year = {2020},
      url = {https://eprint.iacr.org/2020/633}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.