Introduction

In 2022 a post-quantum cryptography competition run by NIST was entering its final round. Among the finalists sat SIKE — a system that had survived seven years of public scrutiny, built on a branch of mathematics so exotic that most cryptographers barely recognized it.

Six weeks before the announcement, two Belgian researchers, Wouter Castryck and Thomas Decru, published a preprint. They had broken SIKE completely: a single-core laptop needed about one hour to recover any private key. No quantum computer required.

The scheme relied on isogeny-based cryptography — a technique for building key-exchange protocols by walking through a vast graph of elliptic curves, where each edge is a structure-preserving map called an isogeny. The hope was that finding the exact path someone took through this graph was computationally hopeless. The reality turned out to be more subtle, and more humbling.

To understand what went wrong, we need to understand what isogenies are, why walks on their graph seemed so safe, and what extra information SIKE accidentally leaked.

Walk the Isogeny Graph

The demo below builds a small isogeny graph. Each node is an elliptic curve (labeled by its j-invariant), and each edge is a degree-2 isogeny — a structure-preserving map between curves.

<p class="hint">
  Each node is an elliptic curve labeled by its <em>j</em>-invariant (mod a small prime). Edges are degree-2 isogenies. Click <b>Random Walk</b> to simulate Alice choosing a secret path. Then click <b>Reveal Torsion Info</b> to see the auxiliary data SIKE would have published — and watch how it pins down the secret path.
</p>
<div id="graph-wrap">
  <canvas id="c" width="480" height="300"></canvas>
</div>
<div class="controls">
  <button id="btn-walk" type="button">Random Walk (Alice’s secret)</button>
  <button id="btn-torsion" type="button" disabled>Reveal Torsion Info</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="info" class="info-box"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
#graph-wrap { background: #f4f7fa; border-radius: 10px; overflow: hidden; margin-bottom: .7rem; }
canvas { display: block; max-width: 100%; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border-radius: 8px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.info-box { font-size: .88rem; line-height: 1.55; min-height: 2.4em;
            background: #eef3f8; border-radius: 8px; padding: .5rem .8rem; color: #1d3557; }
.info-box.warn { background: #fff3cd; color: #7a5200; }
.info-box.danger { background: #fde8ea; color: #8b1e26; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Toy isogeny graph: 13 supersingular j-invariants mod 431 (a small prime where
// the supersingular locus has ~floor((431-1)/12)+1 = 36+ curves, but we use 13 hand-chosen nodes that form a connected 3-regular degree-2 isogeny graph).
// This is illustrative — real SIKE uses p~434 bits, ~2^130 nodes.

const NODES = [
  {id:0,  j:0,   x:240, y:150},
  {id:1,  j:8,   x:340, y:80},
  {id:2,  j:27,  x:380, y:190},
  {id:3,  j:64,  x:300, y:260},
  {id:4,  j:125, x:180, y:270},
  {id:5,  j:216, x:100, y:200},
  {id:6,  j:343, x:90,  y:90},
  {id:7,  j:512, x:170, y:50},
  {id:8,  j:1,   x:420, y:140},
  {id:9,  j:9,   x:430, y:260},
  {id:10, j:16,  x:240, y:30},
  {id:11, j:25,  x:50,  y:150},
  {id:12, j:36,  x:140, y:300},
];

// Edges: each node has exactly 3 degree-2 isogeny neighbours (3-regular graph)
const EDGES = [
  [0,1],[0,6],[0,10],
  [1,2],[1,7],
  [2,3],[2,8],
  [3,4],[3,9],
  [4,5],[4,12],
  [5,6],[5,11],
  [6,7],
  [7,10],
  [8,9],[8,10],
  [9,12],
  [10,11],
  [11,12],
];

// Build adjacency list
const ADJ = NODES.map(() => []);
EDGES.forEach(([a,b]) => { ADJ[a].push(b); ADJ[b].push(a); });

const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');

// State
let secretPath = [];      // Alice’s walk (list of node ids)
let torRevealed = false;
let attackStep = 0;
let animFrame = null;

function draw() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  // Draw edges
  EDGES.forEach(([a, b]) => {
    const A = NODES[a], B = NODES[b];
    const onPath = isOnPath(a, b);
    ctx.beginPath();
    ctx.moveTo(A.x, A.y);
    ctx.lineTo(B.x, B.y);
    ctx.strokeStyle = onPath ? '#e63946' : '#b0bec5';
    ctx.lineWidth = onPath ? 3 : 1.5;
    ctx.stroke();
  });

  // Draw nodes
  NODES.forEach(node => {
    const inPath = secretPath.includes(node.id);
    const isStart = secretPath[0] === node.id;
    const isEnd = secretPath.length > 0 && secretPath[secretPath.length - 1] === node.id;
    const pinned = torRevealed && isPinned(node.id);

    // Circle
    ctx.beginPath();
    ctx.arc(node.x, node.y, 18, 0, 2 * Math.PI);
    if (isStart) ctx.fillStyle = '#2a9d8f';
    else if (isEnd) ctx.fillStyle = '#e9c46a';
    else if (pinned) ctx.fillStyle = '#e63946';
    else if (inPath) ctx.fillStyle = '#457b9d';
    else ctx.fillStyle = '#dce8f0';
    ctx.fill();
    ctx.strokeStyle = inPath ? '#1d3557' : '#90a4ae';
    ctx.lineWidth = inPath ? 2 : 1;
    ctx.stroke();

    // Label
    ctx.fillStyle = inPath || pinned ? '#fff' : '#455a64';
    ctx.font = '700 10px ui-monospace, monospace';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText('j=' + node.j, node.x, node.y);
  });

  // Legend
  if (secretPath.length > 0) {
    ctx.font = '11px system-ui';
    ctx.fillStyle = '#555';
    ctx.textAlign = 'left';
    ctx.fillText('● Start  ● End  — Secret walk', 8, H - 10);
  }
}

function isOnPath(a, b) {
  for (let i = 0; i < secretPath.length - 1; i++) {
    if ((secretPath[i] === a && secretPath[i+1] === b) ||
        (secretPath[i] === b && secretPath[i+1] === a)) return true;
  }
  return false;
}

// Simulate torsion-point constraint: the auxiliary data narrows candidates
// to those nodes that "agree" with the published image. Here we fake this by flagging any node within 1 hop of the secret end that is NOT on the path.
function isPinned(id) {
  if (!torRevealed || secretPath.length < 2) return false;
  const endNode = secretPath[secretPath.length - 1];
  return ADJ[endNode].includes(id) && !secretPath.includes(id);
}

function randomWalk(startId, steps) {
  const path = [startId];
  for (let i = 0; i < steps; i++) {
    const cur = path[path.length - 1];
    const prev = path.length > 1 ? path[path.length - 2] : -1;
    const choices = ADJ[cur].filter(n => n !== prev);
    path.push(choices[Math.floor(Math.random() * choices.length)]);
  }
  return path;
}

function setInfo(msg, cls = '') {
  const el = document.getElementById('info');
  el.innerHTML = msg;
  el.className = 'info-box ' + cls;
}

document.getElementById('btn-walk').addEventListener('click', () => {
  const start = Math.floor(Math.random() * NODES.length);
  secretPath = randomWalk(start, 4 + Math.floor(Math.random() * 3));
  torRevealed = false;
  document.getElementById('btn-torsion').disabled = false;
  draw();
  setInfo(
    fmt('<b>Alice’s secret walk:</b> %map%<br>The red path is her private key. She publishes only the <b>endpoint</b> (yellow) + torsion images.', { map: secretPath.map(i => 'j=' + NODES[i].j).join(' → ') })
  );
});

document.getElementById('btn-torsion').addEventListener('click', () => {
  if (secretPath.length < 2) return;
  torRevealed = true;
  draw();
  const end = NODES[secretPath[secretPath.length - 1]];
  const pinned = NODES.filter(n => isPinned(n.id));
  setInfo(
    fmt('<b>Torsion images published.</b> The endpoint is j=%j%. The auxiliary torsion data constrains the possible secret walks: the red-highlighted neighbours of the endpoint are now <em>ruled in</em> as structural witnesses. In real SIKE, Castryck &amp; Decru used this to reconstruct Alice’s entire secret isogeny in polynomial time — <b>the graph became transparent.</b>', { j: end.j }),
    'danger'
  );
  document.getElementById('btn-torsion').disabled = true;
});

document.getElementById('btn-reset').addEventListener('click', () => {
  secretPath = [];
  torRevealed = false;
  document.getElementById('btn-torsion').disabled = true;
  draw();
  setInfo('Click <b>Random Walk</b> to simulate Alice choosing a secret path through the isogeny graph.');
});

draw();
setInfo('Click <b>Random Walk</b> to simulate Alice choosing a secret path through the isogeny graph.');

// Verify: check that the graph is connected and every node has degree >= 2
(function verify() {
  const visited = new Set();
  const q = [0];
  while (q.length) {
    const n = q.shift();
    if (visited.has(n)) continue;
    visited.add(n);
    ADJ[n].forEach(m => q.push(m));
  }
  const allConnected = visited.size === NODES.length;
  const minDeg = Math.min(...ADJ.map(a => a.length));
  console.assert(allConnected, 'Graph must be connected');
  console.assert(minDeg >= 2, 'Every node must have degree >= 2');
  console.log(fmt('Graph OK — connected: %allConnected% | min degree: %minDeg%', { allConnected: allConnected, minDeg: minDeg }));
})();
Result
Console

In the real SIKE protocol, Alice picks a secret random walk (a path through the graph) and publishes where she ended up, together with auxiliary torsion-point images that helped the other party do their own computation. Those extra points are what Castryck and Decru exploited: the auxiliary data constrained Alice's secret path so tightly that a classical algorithm could recover it efficiently. The graph looked like a labyrinth — but SIKE handed the attacker a map.

The Real Complexity

Isogeny cryptography sits on a genuinely hard mathematical problem — but that problem is not the one SIKE was actually relying on.

The hard part (still standing): given two elliptic curves E and E′, find an isogeny between them. For random curves over large fields the best known algorithms run in subexponential time classically and in roughly O(p1/4)O(p^{1/4}) time with a quantum computer — slow enough to be practical, and offering real post-quantum resistance. Systems like CSIDH and SQIsign build on this and remain active research candidates.

The SIDH problem (what SIKE used): the Supersingular Isogeny Diffie-Hellman protocol had Alice and Bob each walk the graph along secret paths of different prime degrees, then exchange endpoints. The security assumption was that recovering the secret walk from the endpoint alone was hard. And it was.

The fatal leak: SIKE also transmitted images of torsion points — fixed reference points mapped through each party's secret isogeny — to let the other party finish the handshake. Castryck and Decru showed that these images give a classical attacker enough structural information to reconstruct the secret isogeny via an elegant attack using Richelot isogenies and gluing of higher-dimensional abelian varieties. The attack runs in polynomial time once those torsion images are available.

The lesson is sharp: the underlying isogeny path problem is hard. The specific extra data SIKE exposed broke the problem down into something solvable. NIST removed SIKE from the competition immediately after the preprint appeared. Factoring and discrete logarithms fell to Shor's quantum algorithm; SIKE fell to a classical attack on information it volunteered.

Where It Still Matters

SIKE's collapse did not kill isogeny cryptography — it killed one particular protocol that leaked too much.

  • SQIsign (Short Quaternion and Isogeny Signature): a digital signature scheme based on the hardness of computing isogenies between supersingular curves. It offers extremely compact signatures (~200 bytes) and remains a serious NIST candidate. No torsion-point images are exposed.
  • CSIDH (Commutative SIDH): uses ordinary (non-supersingular) elliptic curves and a commutative group action, avoiding the auxiliary data that sank SIKE. Its quantum security is debated but classically it is solid.
  • Threshold and verifiable delay functions: isogenies' algebraic structure makes them attractive for protocols where multiple parties must compute jointly without any one seeing the secret.
  • Proof-of-work and time-lock puzzles: the sequential nature of isogeny chains (you cannot parallelize a walk easily) makes them a natural primitive for time-locked cryptography.

The SIKE saga illustrates a general principle that shows up in lattice cryptography too: the hard problem and the protocol built on it are different things. Leaking auxiliary structure can collapse the security gap even when the core problem stays unsolved.

Conclusion

SIKE's defeat was one of the most dramatic moments in modern cryptography: a finalist in a six-year standardization process, broken overnight by a classical algorithm, on a laptop, with elegant mathematics that many experts said they should have seen coming.

The underlying problem — walking an isogeny graph without being detected — remains genuinely hard. What failed was the decision to hand the attacker extra structural information in the name of efficiency. In cryptography, efficiency and security are always in tension, and SIKE found the wrong side of that line.

Post-quantum cryptography continues. NIST standardized CRYSTALS-Kyber (lattice-based), CRYSTALS-Dilithium, and FALCON in 2024. Isogeny schemes like SQIsign remain active contenders for the next round. The graph of elliptic curves is still a formidable labyrinth — you just have to be careful what you hand to the person trying to find your path. See also: Shor's algorithm and factoring for the quantum threats that started the post-quantum race.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/isogeny-crypto/Content licensed under CC BY-NC 4.0.