class group

the mathematical structure

let O = Z[pi] be the endomorphism ring of a supersingular elliptic curve E over F_q, where pi is the Frobenius endomorphism (pi^2 = -q on the curve).

the ideal class group cl(O) is a finite abelian group that acts on the set Ell(O, pi) of supersingular curves with endomorphism ring O.

action: cl(O) x Ell(O, pi) -> Ell(O, pi)

key property: the action is COMMUTATIVE.

[a] * ([b] * E) = [b] * ([a] * E)

ideal representation

an ideal [a] in cl(O) is represented as a vector of exponents:

[a] = [l_1]^e_1 * [l_2]^e_2 * ... * [l_n]^e_n

where [l_i] is the ideal class generated by the prime l_i, and e_i in {-m, ..., 0, ..., m}.

the class group is generated by these n ideal classes. the security parameter m controls the key space: |key space| = (2m+1)^n.

for CSIDH-512: n = 74, m = 5, key space ~ 2^256.

class number

|cl(O)| ~ sqrt(q) / 12 (Deuring's theorem, approximate).

for CSIDH-512: |cl(O)| ~ 2^256.

group structure

cl(O) is a finite abelian group, so by the structure theorem:

cl(O) ~ Z/d_1 x Z/d_2 x ... x Z/d_k

where d_1 | d_2 | ... | d_k. the exact structure for the CSIDH-512 prime is not fully known (computing the class group structure is itself a hard problem), but the order is approximately 2^256.

security assumptions

GAIP (Group Action Inverse Problem): given E_0 and [a] * E_0, find [a].

best known attack: quantum subexponential (Kuperberg's algorithm, ~2^(sqrt(log q))).

this is NOT broken by Shor's algorithm (which breaks discrete log and factoring). isogeny problems have a fundamentally different structure.

MT (Multi-Target): given E_0 and multiple [a_i] * E_0, find any [a_i]. reduces to GAIP with polynomial overhead.