How Does the Adaptive Attack on SIDH Work?

TL;DR

SIDH exposes images of torsion points so participants can push secret kernels through each other’s isogenies, but that extra information also creates cryptanalytic opportunities. The proposed approach generalizes Petit’s torsion-point method to situations where images of torsion groups are available, using several pairwise disjoint cyclic groups, pairing equations, discrete logarithms, and knowledge of the starting curve’s endomorphism ring.

Transcript

Hello, everyone. Welcome to this presentation. I am Tako Boris Fota from University of Roma Tre, and I'm going to present our result, a new adaptive attack on SIDH, which is joint work with Christophe Petit from Université Libre de Bruxelles and University of Birmingham. So isogeny-based cryptography is a branch of post-quantum cryptography that of... Read More

Key Insights

• SIDH is an isogeny-based protocol whose compact public information includes a destination curve and images of torsion basis points under a secret isogeny. These images allow each participant to push a secret kernel through the other participant’s isogeny and obtain a common j-invariant.
• Elliptic-curve isogenies are rational maps that also preserve the group structure of elliptic-curve points. Their degree is closely related to the size of their kernel, and they can be computed efficiently when that degree is smooth, unlike isogenies with large, non-smooth degree.
• The security problem in SIDH is not merely the pure isogeny problem because an attacker receives more than the starting and destination curves. The public data also reveals how the secret isogeny acts on selected torsion points, while the starting curve has a known endomorphism ring.
• Petit’s torsion-points attack works by pushing a known endomorphism of the starting curve through the secret isogeny, producing an endomorphism of the destination curve. Adding an integer endomorphism creates a map whose action can be evaluated on publicly exposed torsion points.
• A suitable destination-curve endomorphism can be decomposed into isogenies whose degrees reflect the torsion order and a small remaining factor. Public torsion-point images recover the larger components, while the small-degree component can be found by brute force, revealing the endomorphism’s kernel.
• The secret isogeny kernel can be recovered by intersecting the kernel of the reconstructed endomorphism, after subtracting its integer component, with the relevant torsion subgroup. Under stated conditions, this yields either the full kernel or a large portion whose remainder can be brute-forced.
• Petit’s original method is efficient only for unbalanced SIDH variants because finding the required endomorphism reduces to a norm equation whose efficient solution depends on an imbalance between parameter sizes. The transcript states that the original balanced SIDH parameters are not covered by that polynomial-time attack.
• The generalized torsion-groups method uses images of pairwise disjoint cyclic groups instead of exact torsion-point images. This information determines the action of an unknown scalar multiple of the secret isogeny, and pairing equations plus a discrete logarithm reveal the scalar’s square, but not necessarily the scalar itself.

Questions & Answers

Q: How does SIDH establish a shared secret with isogenies?

SIDH begins with a shared supersingular elliptic curve and agreed torsion-point bases. Each participant computes a secret isogeny, publishes the resulting curve, and reveals the secret isogeny’s action on torsion points used by the other participant. Those images let each side push its own secret kernel through the other side’s isogeny. The resulting curves coincide or have the same j-invariant, which serves as the shared value.

Q: Why does SIDH publish images of torsion points?

Supersingular isogenies do not generally commute, so exchanging only the destination curves does not provide an obvious way for both participants to construct matching results. Published torsion-point images show how each secret isogeny acts on the subgroup used by the other participant. With that information, each participant can transport a secret kernel through the received isogeny and complete the commuting diagram needed to obtain a shared j-invariant.

Q: What security problem underlies SIDH?

SIDH relies on a supersingular isogeny problem with torsion-point information, not the pure problem of finding any isogeny between two given isogenous curves. An attacker knows the fixed starting curve, the public destination curve, and the action of the secret isogeny on selected torsion points. The starting curve’s endomorphism ring is also known, which provides additional algebraic structure that cryptanalytic methods can exploit.

Q: How does Petit’s torsion-points attack recover a secret isogeny?

The attack starts with a known endomorphism of the SIDH starting curve and pushes it through the secret isogeny to obtain an endomorphism of the destination curve. An integer endomorphism is added to form a suitable map. Public torsion-point images help decompose and reconstruct that map. Once its kernel is known, intersecting an adjusted kernel with the relevant torsion subgroup reveals all or much of the secret isogeny’s kernel.

Q: Why does Petit’s attack target unbalanced SIDH variants?

The attack requires a suitable starting-curve endomorphism and an integer adjustment whose resulting degree has a specific form involving the public torsion order and a small factor. For the stated starting curve, finding these values reduces to solving a norm equation. The transcript says efficient solutions are available only when the relevant parameter sizes satisfy an imbalance condition, so the polynomial-time method applies to unbalanced variants rather than the original balanced parameters.

Q: How are torsion-point images validated in SIDH?

A pairing equation provides the basic validation described in the presentation. It checks that the published images of the torsion basis points are linearly independent and are likely to be images produced by an isogeny of the expected degree. This validation concerns the structure and relationship of the disclosed points, which are needed so the receiving participant can use them to push a secret kernel through the published isogeny.

Q: How does the generalized attack use torsion groups?

The generalized problem provides the starting and destination curves together with images of several pairwise disjoint cyclic groups of the relevant torsion order. The presentation states that knowing these group images is equivalent to being able to evaluate an unknown scalar multiple of the secret isogeny on the full torsion subgroup. This reformulation extends the torsion-points approach to settings where exact images of individual torsion points are unavailable.

Q: Why is recovering the unknown scalar difficult?

Pairing equations applied to the available torsion-group information, followed by solving a discrete logarithm, can recover the square of the unknown scalar. Recovering the scalar from its square is not automatically efficient when the torsion order is not a prime power, because the square may have more than two square roots. The transcript identifies this ambiguity as an obstacle in moving from group-image information to the exact scalar action.

Summary & Key Takeaways

• SIDH is an isogeny-based key-exchange protocol built from supersingular elliptic curves. Because supersingular isogenies do not generally commute, each participant publishes a curve together with images of torsion basis points. Those images let the other participant transport a secret kernel through the published isogeny and derive a curve with the same j-invariant.

• Petit’s torsion-points attack exploits two special forms of public information: the known endomorphism ring of SIDH’s starting curve and the disclosed action of a secret isogeny on torsion points. A suitable endomorphism of the destination curve can reveal the secret kernel, provided an associated norm equation can be solved efficiently under favorable parameter conditions.

• The generalized attack replaces exact torsion-point images with images of pairwise disjoint cyclic torsion groups. That group information permits evaluation of an unknown scalar multiple of the secret isogeny on the torsion subgroup. Pairing equations and a discrete logarithm recover the scalar’s square, although extracting the scalar itself can remain difficult for non-prime-power torsion orders.