CryptoDB
Katherine E. Stange
Publications
Year
Venue
Title
2024
ASIACRYPT
Extending class group action attacks via sesquilinear pairings
Abstract
We introduce a new tool for the study of isogeny-based cryptography, namely pairings which are sesquilinear (conjugate linear) with respect to the O-module structure of an elliptic curve with CM by an imaginary quadratic field O. We use these pairings to study the security of problems based on the class group action on collections of oriented ordinary or supersingular elliptic curves. This extends work of [CHM+23] and [FFP24].
2021
CRYPTO
Improved torsion-point attacks on SIDH variants
📺
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].
Coauthors
- Victoria de Quehen (1)
- Yara Elias (1)
- Péter Kutas (1)
- Kristin E. Lauter (1)
- Chris Leonardi (1)
- Joseph Macula (1)
- Chloe Martindale (1)
- Ekin Ozman (1)
- Lorenz Panny (1)
- Christophe Petit (1)
- Katherine E. Stange (3)