Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Isogenies
Hardness assumptionKE: gives key exchangeHistorically broken

SIDH problem (+ torsion points)

In plain words

A variant of the isogeny puzzle that leaked extra hints. In 2022 those hints let researchers break it completely.

The idea: SIDH needed two people's secret walks to fit together, so each published extra clues: where certain points ended up after their walk. In 2022 Castryck and Decru showed that those clues, combined with a 1997 theorem, pin down the secret walk efficiently. The underlying map stayed hard. The clues were the leak.

Why it matters: A lesson: extra assumptions can fail even when the core problem holds.

The details

On the map: ✗ broken 2022 (Castryck-Decru): the extra torsion points leak the secret

SIDH key exchange revealed where certain auxiliary points (torsion points) land under the secret isogeny, because the protocol needed them to work.

In July 2022 Castryck and Decru[1, 2] used exactly that extra information, together with a 1997 theorem of Kani, to recover secret keys in polynomial time. It is a textbook case of an extra assumption failing while the underlying problem (the isogeny path) survived.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.

References

  1. Wouter Castryck and Thomas Decru. An Efficient Key Recovery Attack on SIDH. Advances in Cryptology – EUROCRYPT 2023. doi:10.1007/978-3-031-30589-4_15
  2. Damien Robert. Breaking SIDH in Polynomial Time. Advances in Cryptology – EUROCRYPT 2023. doi:10.1007/978-3-031-30589-4_17