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.