Meet-in-the-middle and the supersingular path problem

Given two supersingular elliptic curves, find an isogeny between them. Every isogeny-based scheme still standing rests on some form of this problem, and for thirty years the best classical algorithms took about p1/2 steps. In 2026 that exponent moved to 1/3, at the price of memory just as large.

Problem
Given supersingular E, E′ over Fp2, find an isogeny E → E′ of smooth degree
Cost
Õ(p1/2) with polynomial memory (Delfs–Galbraith); p1/3+o(1) time and memory (Wesolowski, 2026)
Quantum
Õ(p1/4) (Biasse, Jao and Sankar)
Equivalent to
Computing the endomorphism ring of a supersingular curve (Wesolowski, 2021, under GRH)
Affects
SQIsign parameters; the Charles–Goren–Lauter hash; any scheme resting on the general path problem

The problem

Fix a prime p. Up to isomorphism there are about p/12 supersingular elliptic curves over the algebraic closure of Fp, all of them defined over Fp2. Join two of them whenever there is an isogeny of degree ℓ between them, for a fixed small prime ℓ, and you get the supersingular ℓ-isogeny graph: connected, (ℓ+1)-regular, of diameter about log p, and an excellent expander. The isogeny note draws it for p = 431.

The path problem asks for a path in that graph between two given vertices, which amounts to an isogeny of degree a power of ℓ between two given curves. Because the graph mixes so fast, a random walk of length about log p lands on a nearly uniform curve, which is exactly how the Charles–Goren–Lauter hash function and SIDH-style key generation used it. Finding a collision in that hash, or recovering an SIDH key without the torsion information, means solving an instance of the path problem.

The problem has a second face. Wesolowski proved in 2021, assuming the generalised Riemann hypothesis, that finding paths and computing endomorphism rings are equivalent under reductions of polynomial expected time. Knowing both endomorphism rings, a path can be computed in polynomial time with the KLPT algorithm; this is how SQIsign's signer, who knows End(Epk), answers challenges a forger cannot.

Meet in the middle

The generic attack treats the graph as a black box. Grow a ball of curves around E by computing isogenies of degree ℓ, ℓ2, …, grow another around E′, and stop when a curve appears in both: its two paths joined give the answer. By the birthday bound the two balls meet once each holds about √(p/12) curves, so the search costs Õ(p1/2) isogeny evaluations and as much memory. Searching from one side alone would need the ball to hold a constant fraction of the whole graph, about p/12 curves.

The memory is the catch. Van Oorschot and Wiener's parallel collision search trades it away, replacing the stored balls with random walks and distinguished points, as in Pollard's rho. Adj, Cervantes-Vázquez, Chi-Domínguez, Menezes and Rodríguez-Henríquez costed both approaches against SIKE's parameters in 2018 and concluded that, with realistic memory, van Oorschot–Wiener was the cheaper, which led to SIKE's parameters being reduced. The same accounting now decides how much the 2026 algorithm matters.

Delfs–Galbraith: going through Fp

Delfs and Galbraith observed that the curves defined over Fp itself, rather than Fp2, form a subset of only Õ(p1/2) vertices, and that paths between them are easy to find, because over Fp the curves carry a commutative class-group action of the kind CSIDH uses. So the attack walks randomly from each end until it lands on a curve defined over Fp, which takes about p1/2 steps, and then joins the two landing points cheaply. The total is Õ(p1/2) time, the same exponent as meet-in-the-middle, but with polynomial memory.

The graph for p = 10,007 has 77 curves with j-invariant in Fp, where √p is about 100. From every start and target curve in the trials above, a breadth-first search reached one of them within 6 steps, and the median was 4. At this size a curve over Fp is always close by. At a 256-bit prime they make up roughly one curve in 2124, and finding one is the whole cost of the attack.

The same route is why quantum computers help here only modestly. Biasse, Jao and Sankar replaced the random search for an Fp curve with Grover's algorithm and the class-group step with a quantum subexponential algorithm, for a total of Õ(p1/4). The general path problem has no known quantum attack better than that. This is the reason SQIsign's security depends on classical cryptanalysis, while CSIDH's commutative structure exposes it to Kuperberg's subexponential quantum algorithm.

The p1/3 algorithm

In 2026 Wesolowski gave a heuristic algorithm for the path problem, equivalently the endomorphism ring problem, running in time and memory p1/3+o(1). Instead of joining two arbitrary curves, it looks for a short isogeny from a single curve to its Galois conjugate, the curve obtained by applying the Frobenius p-th power map to its coefficients. Such an isogeny, composed with Frobenius, gives a new endomorphism, and a few endomorphisms determine the whole ring. A meet-in-the-middle search over isogenies of smooth degree finds one after p1/3+o(1) steps rather than p1/2.

Three qualifications decide what this means in practice:

  • It is heuristic. The running time rests on explicit, stated heuristics about the distribution of these isogenies, not on a proof.
  • The o(1) is not small. It hides a superpolynomial factor, so at cryptographic sizes the cost is well above p1/3.
  • Memory equals time. Like any meet-in-the-middle search it stores what it searches. No low-memory variant analogous to van Oorschot–Wiener is known, and the concrete cost therefore depends on how much memory an attacker is assumed to have.

SQIsign's designers answered it in version 3.0 of their specification by raising the prime at each level and costing the attack under memory limits of 280, 2120 and 2160 stored entries. With those limits the estimated costs clear NIST's targets, and the designers say plainly that a version of the attack without the memory requirement would force the parameters to be revisited. The SQIsign page has the numbers.

The boundary

  • SIDH and SIKE were not broken by any of this. They fell to torsion-point attacks, which exploit extra information those schemes published. Without that information the path problem is untouched by those attacks.
  • Special curves are easy. If the starting curve's endomorphism ring is known, as it is for j = 1728 when p ≡ 3 mod 4, a path from it to anything is exactly as hard as the endomorphism ring problem for the other end. Schemes must never let a secret curve's endomorphism ring leak.
  • Parameter sizing should now be done against p1/3+o(1) time and memory, with an explicit memory bound, rather than against p1/2. Whether the exponent can go below 1/3, or the memory be reduced, is open.
  • The quantum picture is unchanged: Õ(p1/4) remains the best known quantum algorithm for the general problem.

Primary sources

  1. D. X. Charles, K. E. Lauter and E. Z. Goren, "Cryptographic hash functions from expander graphs", Journal of Cryptology 22 (2009)
  2. C. Delfs and S. D. Galbraith, "Computing isogenies between supersingular elliptic curves over Fp", Designs, Codes and Cryptography 78 (2016)
  3. J.-F. Biasse, D. Jao and A. Sankar, "A quantum algorithm for computing isogenies between supersingular elliptic curves", INDOCRYPT 2014
  4. G. Adj, D. Cervantes-Vázquez, J.-J. Chi-Domínguez, A. Menezes and F. Rodríguez-Henríquez, "On the cost of computing isogenies between supersingular elliptic curves", SAC 2018
  5. K. Eisenträger, S. Hallgren, K. Lauter, T. Morrison and C. Petit, "Supersingular isogeny graphs and endomorphism rings: reductions and solutions", EUROCRYPT 2018
  6. B. Wesolowski, "The supersingular isogeny path and endomorphism ring problems are equivalent", FOCS 2021
  7. B. Wesolowski, "The supersingular isogeny problem in time and memory p1/3+o(1)" (2026)
  8. SQIsign team, "SQIsign: algorithm specifications and supporting documentation", version 3.0 (September 2026)