SIDH and SIKE: Design and Cryptanalysis

Supersingular Isogeny Diffie-Hellman (SIDH), proposed by Jao and De Feo in 2011, is a public-key exchange protocol analogous to Diffie-Hellman but using isogenies on supersingular elliptic curves. Both parties start with the same supersingular curve E over Fp2. Alice computes a secret isogeny phi_A: E -> E_A (random kernel in 2^a-torsion), publishes E_A and images of Bob's torsion generators under phi_A. Bob computes phi_B: E -> E_B (random kernel in 3^b-torsion), publishes E_B and images of Alice's torsion generators under phi_B. Alice uses Bob's published data to compute phi_A': E_B -> E_AB; Bob computes phi_B': E_A -> E_AB. Both arrive at j(E_AB) as the shared secret.

SIDH's special prime form p = 2^a * 3^b * f - 1 (f is a small cofactor for primality) ensures that the curve E over Fp2 has the necessary torsion structure. For SIKEp434 (NIST Level 1, 128-bit post-quantum security): p = 2^216 * 3^137 - 1, a = 216, b = 137. This means Alice takes a walk of 216 steps of 2-isogenies, Bob takes 137 steps of 3-isogenies. Key sizes: Alice's public key is E_A plus two Fp2 points (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 bytes. SIKEp751 targets 192-bit classical / 128-bit quantum security and has 564-byte public keys. These are the smallest public keys of any NIST PQC candidate — at the cost of being 100-1000x slower.

SIKE (Supersingular Isogeny Key Encapsulation) is an IND-CCA2 secure KEM built from SIDH using the Fujisaki-Okamoto transform. SIKE.Encaps: pick a random message m, compute (c0 = SIDH public key with seed m, c1 = H2(m) XOR pk), send (c0, c1). SIKE.Decaps: recover m from c0 using secret key, verify c1, recompute (c0, c1) to check consistency, output K = H3(m, c0). The FO transform converts the SIDH CPA-secure exchange into CCA2-secure KEM. SIKE competed in all four rounds of NIST PQC (2017-2022), surviving extensive cryptanalysis — until a devastating classical attack appeared in July 2022.

From 2011 to 2022, SIDH withstood significant cryptanalytic effort. The best known attacks against SIDH were: (1) Generic SSIP algorithm: O(p^{1/4}) classically, O(p^{1/6}) quantumly using Tani's algorithm. (2) Meet-in-the-middle on the isogeny path: O(p^{1/4}) classical, same as SSIP. (3) Polynomial-time algorithms for specific structural attacks (van Oorschot-Wiener): not applicable to SIDH. Dozens of papers analyzed SIDH security, and no polynomial-time classical or quantum attack was found in 11 years. This track record made SIKE a credible NIST finalist. The eventual break came not from direct attack on the SSIP but from exploiting SIDH's auxiliary torsion point information.

On July 30, 2022, Wouter Castryck and Thomas Decru posted a preprint showing a polynomial-time classical attack on SIDH. The attack uses the extra information in SIDH's auxiliary torsion points phi_A(P_B), phi_A(Q_B): this information essentially reveals the action of phi_A on the 3^b-torsion subgroup. Combined with the image curve E_A, this allows reconstructing the kernel of phi_A (and hence phi_A itself) using techniques from the theory of elliptic curves with complex multiplication and Richelot isogenies. The attack ran in 62 minutes on a laptop for SIKEp434 — a parameter set supposed to provide 128-bit post-quantum security. Within days, independent researchers confirmed and extended the attack to all SIDH parameters.

SIDH's design required both parties to publish images of the other party's torsion basis points under their secret isogeny. This was necessary for the protocol to work: without phi_A(P_B) and phi_A(Q_B), Bob could not transport his isogeny to Alice's curve to compute the shared secret. But this extra information — which reveals the action of phi_A restricted to the 3^b-torsion — turned out to be catastrophically more information than expected. The Castryck-Decru attack uses genus-2 curves (Richelot isogenies) to lift the problem to higher-genus objects where the restricted action completely determines phi_A. This leakage is structural to SIDH and cannot be fixed without changing the protocol's fundamental design.

On July 5, 2022 (before Castryck-Decru), NIST had announced its initial PQC standardization choices: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+), and FN-DSA (Falcon) — SIKE was not among them (it was in a second round of consideration). The Castryck-Decru attack in July 2022 led NIST to formally eliminate SIKE from consideration entirely. NIST stated: "SIKE is no longer under consideration for standardization." This was the most dramatic cryptanalytic development in the NIST PQC competition, demonstrating that even a scheme that survived 11 years of analysis could be broken by a fundamentally new mathematical insight.

Within a week of Castryck-Decru, Thomas Decru and Luciano Maino (independently) and later Damien Robert posted further improvements. Robert's variant of the attack uses the same insight but computes the endomorphism ring of E_A rather than directly computing the isogeny kernel, and is arguably simpler to describe mathematically. These rapid independent rediscoveries confirmed that the Castryck-Decru attack identified a fundamental structural weakness, not an obscure trick. The speed of subsequent papers also reflected how many researchers had been studying SIDH's torsion-point leakage as a potential attack vector, aware it was an unusual information disclosure but unable to exploit it until Castryck and Decru found the genus-2 bridge.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) is a KEM design inspired by SIDH but avoiding the torsion-point auxiliary data. FESTA uses a different protocol structure: the public key does not include images of the counterparty's torsion basis — instead, the secret isogeny is committed to via the image curve only (no auxiliary points). FESTA encrypts using isogenies in a way that reveals less structural information. Early security analysis suggests FESTA avoids the Castryck-Decru attack structure. However, FESTA is newer and has received less scrutiny than SIKE's 11-year track record, and the isogeny community is cautious about deploying new schemes before extensive analysis.

SIKE's break offers important lessons. (1) Auxiliary information disclosure is dangerous: SIDH's extra torsion-point data was necessary for the protocol but fatally leaked information. Protocol designers must analyze every piece of public data, not just the main values. (2) Track record is not a security proof: 11 years without a known attack is reassuring but not a guarantee. Cryptographic proofs (reduction to a well-defined hard problem) are more reliable than argument by authority or survived scrutiny. (3) Novel mathematical tools create risks: the Castryck-Decru attack used genus-2 Richelot isogenies — a tool from mathematics not previously applied to isogeny cryptanalysis. Cryptanalysts surveying new primitives must consider new mathematical domains.

Despite SIKE's break, isogeny-based cryptography continues as a research discipline. SQISign signatures (177 bytes at Level 1) remain the most compact PQC signatures known and use a different hardness assumption (endomorphism ring problem) not affected by the SIDH attack. CSIDH-based protocols use the class group action structure (commutative isogenies) with no torsion-point leakage, though CSIDH faces its own challenges (slower than SIDH was, quantum security analysis ongoing). The isogeny community views the SIKE break as a learning experience that sharpened understanding of what information must be hidden in isogeny protocols — valuable knowledge for designing future schemes.

What aspect of SIDH's design enabled the Castryck-Decru attack?

SIDH uses alternating 2^a and 3^b isogeny chains between two parties, sharing auxiliary torsion point images to enable the key exchange. SIKE wraps SIDH with Fujisaki-Okamoto for CCA2 security. SIKE had the smallest keys of any NIST PQC candidate (374 bytes) but was 100-1000x slower. After 11 years of security, Castryck-Decru broke SIKE in July 2022 using genus-2 Richelot isogenies to exploit torsion-point leakage. NIST eliminated SIKE. FESTA avoids torsion-point disclosure. SQISign continues using endomorphism ring hardness. The SIKE break illustrates that auxiliary public data must be analyzed as carefully as primary protocol values.