Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Isogenies
Hardness assumption

Supersingular isogeny path

In plain words

Find a path of special maps connecting two elliptic curves. Believed hard even for quantum computers.

The idea: Picture a giant map of elliptic curves where each curve has roads (isogenies) to a few neighbors. Taking a random walk from a starting curve is easy. Given only where you ended up, finding any route back is believed hard, even for quantum computers, because the map is enormous and has no helpful structure. Your secret is the route. Your public key is the destination.

Why it matters: The basis of very compact quantum-safe signatures (SQIsign).

The details

On the map: ≡ computing endomorphism rings

An isogeny is a special map from one elliptic curve to another. Given two supersingular curves, finding a chain of isogenies connecting them (equivalently, computing their endomorphism rings)[1] is believed hard, even for quantum computers[2].

It underlies SQIsign. The SIDH variant handed attackers extra information and was broken in 2022[3], but this core problem still stands.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (3 boxes)

References

  1. Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). doi:10.1109/focs52979.2021.00109
  2. Denis X. Charles, Kristin E. Lauter and Eyal Z. Goren. Cryptographic Hash Functions from Expander Graphs. Journal of Cryptology, 2009. doi:10.1007/s00145-007-9002-x
  3. 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