Improved Torsion-Point Attacks on SIDH Variants
Victoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale, Lorenz Panny, Christophe Petit, 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].
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
6 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- M-SIDH and MD-SIDH: Countering SIDH Attacks by Masking Information cites Breaking SIDH in Polynomial Time
- M-SIDH and MD-SIDH: Countering SIDH Attacks by Masking Information cites Supersingular Curves You Can Trust
- A Direct Key Recovery Attack on SIDH cites Breaking SIDH in Polynomial Time
- Supersingular Curves You Can Trust cites A Direct Key Recovery Attack on SIDH
- Supersingular Curves You Can Trust cites Rational Isogenies from Irrational Endomorphisms
- CSI -Otter: Isogeny-Based (Partially) Blind Signatures from the Class Group Action with a Twist cites Breaking SIDH in Polynomial Time
- CSI -Otter: Isogeny-Based (Partially) Blind Signatures from the Class Group Action with a Twist cites M-SIDH and MD-SIDH: Countering SIDH Attacks by Masking Information
- CSI -Otter: Isogeny-Based (Partially) Blind Signatures from the Class Group Action with a Twist cites A Direct Key Recovery Attack on SIDH
Cited by top-tier papers6
- Breaking SIDH in Polynomial TimeDamien RobertEUROCRYPT 2023 · 158 citations
- A Direct Key Recovery Attack on SIDHLuciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope et al.EUROCRYPT 2023 · 136 citations
- M-SIDH and MD-SIDH: Countering SIDH Attacks by Masking InformationTako Boris Fouotsa, Tomoki Moriya, Christophe PetitEUROCRYPT 2023 · 52 citations
- Supersingular Curves You Can TrustAndrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo et al.EUROCRYPT 2023 · 43 citations
- CSI -Otter: Isogeny-Based (Partially) Blind Signatures from the Class Group Action with a TwistShuichi Katsumata, Yi-Fu Lai, Jason T. LeGrow, Ling QinCRYPTO 2023 · 22 citations
Builds on1
Related papers
- An Efficient Key Recovery Attack on SIDHWouter Castryck, Thomas DecruEUROCRYPT 2023 · 284 citations
- One-Way Functions and Malleability Oracles: Hidden Shift Attacks on Isogeny-Based ProtocolsPéter Kutas, Simon-Philipp Merz, Christophe Petit, Charlotte WeitkämperEUROCRYPT 2021 · 15 citations
- Quantum Security Analysis of CSIDHXavier Bonnetain, André SchrottenloherEUROCRYPT 2020 · 103 citations
- Better Bounds for Finding Fixed-Degree Isogenies via Coppersmith's MethodMarius A. Aardal, Diego F. Aranha, Yansong Feng, Yiming Gao et al.EUROCRYPT 2026 · 2 citations
- SQIsignHD: New Dimensions in CryptographyPierrick Dartois, Antonin Leroux, Damien Robert, Benjamin WesolowskiEUROCRYPT 2024 · 69 citations
