Elliptiske kurveisogenier: Matematisk grundlag

En isogeni mellem to elliptiske kurver E og E' over et legeme k er en ikke-konstant rational afbildning phi: E -> E', som også er en gruppehomomorfi — den afbilder gruppeloven for E til gruppeloven for E'. Enhver isogeni phi har en dual isogeni phi_hat: E' -> E, sådan at phi_hat sammensat med phi er lig med multiplikation med deg(phi) på E. Graden af en isogeni er størrelsen på dens kerne: En isogeni af grad l har en kerne med størrelsen l. Isogenier generaliserer skalarmultiplikation: multiplikation med n er en isogeni fra E til sig selv med graden n^2. Isogenier over endelige legemer beregnes som rationale funktioner (polynomier), der kan evalueres effektivt.

Velus formler (1971) giver eksplicitte formler til beregning af en isogeni phi: E -> E/G, når en undergruppe G af E er givet. Billedkurven E/G = E' og den rationale afbildning phi bestemmes fuldstændigt af G. Velus formler beregner billedkurvens koefficienter og den rationale afbildning som rationale funktioner af grad |G|. For en kerneundergruppe G af primtalorden l har isogenien graden l og kan beregnes med O(l) operationer. sqrt-Velu-algoritmer (Bernstein et al., 2019) reducerer dette til O(sqrt(l))-operationer for store l og gør CSIDH's effektive isogenier med store primtal mulige. Velus formler er det beregningsmæssige grundlag for al isogenibaseret kryptografi.

Elliptiske kurver over et endeligt legeme Fp kan organiseres i en isogenigraf. Toppunkterne er j-invarianter for elliptiske kurver, altså en kanonisk invariant, der bestemmer kurven op til isomorfi. Kanterne er l-isogenier: Hver ordinær kurve har præcis l+1 udgående l-isogenier for et lille primtal l, hvilket følger af strukturen af l-torsionsundergrupper. l-isogenigrafen over Fp er en (l+1)-regulær graf. Disse grafers Ramanujan-egenskab, altså at de er ekspandergrafer, betyder, at tilfældige vandringer på dem hurtigt bliver blandet. Det giver den antagelse om beregningsmæssig vanskelighed, som isogenibaseret kryptografi bygger på: Tilfældige vandringer med længden O(log p) giver uniforme fordelinger over j-invarianter.

Elliptiske kurver over Fp falder i to kategorier. Ordinære kurver har en ikke-triviel p-rang, hvilket betyder, at der findes p^2 isomorfiklasser og en kompleks isogenigraf med en vulkanstruktur med kratere og gulve. Supersingulære kurver har p-rang 0 og ligger alle i én sammenhængende isogenigraf over Fp2. Antallet af supersingulære j-invarianter over Fp er omtrent p/12. SIDH og SIKE bruger supersingulære kurver, fordi deres isogenigraf er en Ramanujan-graf med stærke ekspansionsegenskaber og uden en vulkanstruktur, der kunne afsløre vandringens retning. CSIDH bruger også supersingulære kurver, men over Fp i stedet for Fp2, og udnytter en anden algebraisk struktur.

Isogenibaseret kryptografi bygger på to beslægtede vanskelige problemer. Problemet med supersingulære isogenier (SSIP): Givet to supersingulære elliptiske kurver E og E' over Fp2 skal man finde en isogeni phi: E -> E'. Problemet med beregning af supersingulære isogenier (CSSI): Givet E, E' = phi(E) og graden af phi skal man finde phi. Den bedste klassiske algoritme til SSIP bruger O(p^{1/4}) tid. Den bedste kvantealgoritme, Tanis algoritme til søgning efter kløer, bruger O(p^{1/6}) tid. For p = 2^{434} giver dette 128-bit sikkerhed mod klassiske angreb. Det er en betydeligt mindre kvantefartforøgelse end Shors algoritmes eksponentielle fartforøgelse mod RSA/ECC, hvilket gør isogenibaserede ordninger postkvantesikre.

SIDH (Supersingular Isogeny Diffie-Hellman) bruger et særligt struktureret primtal p = 2^a * 3^b - 1, som sikrer, at kurven E over Fp2 har 2^a-torsionspunkter, altså mængden af punkter P med 2^a * P = 0, samt tilgængelige 3^b-torsionspunkter. Alices hemmelighed er en 2^a-isogeni phi_A: E -> E_A med en kerne, der genereres af et tilfældigt element fra 2^a-torsionen. Bobs hemmelighed er en 3^b-isogeni phi_B: E -> E_B. De udveksler billeder af torsionspunkter: Alice offentliggør E_A og phi_A(P_B), phi_A(Q_B). Bob offentliggør E_B og phi_B(P_A), phi_B(Q_A). Det giver hver part mulighed for at beregne isogenier fra modpartens kurve og nå frem til den samme delte j-invariant.

Endomorfiringen End(E) for en elliptisk kurve er ringen af alle isogenier fra E til sig selv, herunder skalarmultiplikationer. For ordinære kurver over Fp er End(E) en orden i et imaginært kvadratisk legeme. For supersingulære kurver er End(E) en maksimal orden i en quaternionalgebra, der er forgrenet ved p og uendelig. Strukturen af End(E) bestemmer fuldstændigt kurven op til isomorfi. Problemet med endomorfiringen — at beregne End(E) ud fra E — menes at være vanskeligt og er ækvivalent med SSIP for supersingulære kurver. Castryck-Decru-angrebet på SIDH/SIKE udnyttede ekstra oplysninger, der blev lækket i SIDH-protokollen, til effektivt at genskabe en del af endomorfiringen og bryde ordningen.

En isogeni af graden l, phi: E -> E', kan repræsenteres som et polynomium af graden l eller l/2 efter en symmetrioptimering, der udnytter, at inverse punkter har samme x-koordinat. Beregning af phi(P) for et givet punkt P kræver O(l)-multiplikationer ved hjælp af Velus formler. For SIDH med l = 2^a omkring 2^216 virker dette uoverkommeligt, men SIDH udnytter, at 2^a-isogenier kan opdeles i en kæde af a individuelle 2-isogenier — hver 2-isogeni er billig, og en kæde på a trin giver en 2^a-isogeni. Tilsvarende gælder det for 3^b. sqrt-Velu gør det muligt at beregne store isogenier med ulige primtal i CSIDH med O(sqrt(l)) i stedet for O(l), hvilket gør CSIDH praktisk anvendeligt.

SIKE (Supersingular Isogeny Key Encapsulation) var en NIST-PQC-kandidat, der bestod alle runder indtil fjerde runde, hvor den blev brudt. SIKE var bemærkelsesværdig på grund af de mindste nøglestørrelser blandt alle NIST-kandidater: 374 byte for SIKEp434 (NIST-niveau 1). Til sammenligning har ML-KEM-512 offentlige nøgler på 800 byte. SIKE opnåede denne kompakthed, fordi den delte hemmelighed udledes af en enkelt j-invariant, altså et legemselement på cirka 430 bit. Kompakthed havde dog en pris: SIKE var 100-1000 gange langsommere end de øvrige kandidater. Da Castryck og Decru brød SIKE i juli 2022 ved hjælp af et klassisk angreb, der kunne køre på få minutter på en bærbar computer, blev SIKE straks fjernet fra NIST-konkurrencen.

Isogenibaseret kryptografi indtager en unik position blandt postkvantetilgange. Nøglestørrelserne er meget mindre end for gitterbaserede metoder (ML-KEM: over 800 byte) eller hashbaserede signaturer (SLH-DSA: offentlig nøgle på 32-49 byte, men signaturer på 7856-49856 byte). Ydeevnen er meget lavere end for alle alternativer (SIKE var 100-1000 gange langsommere end ML-KEM). Sikkerhedsantagelsen adskiller sig fra LWE, der bruges i ML-KEM/ML-DSA, SIS og hashfunktioner, og giver dermed kryptografisk diversitet. Grundlaget for den postkvante sikkerhed er isogenisti-problemet, som ingen kendt kvantealgoritme i polynomiel tid kan løse, i modsætning til RSA/ECC, som Shors algoritme bryder fuldstændigt. SIKE's klassiske brud viser, at isogeniernes vanskelighed stadig bliver undersøgt, i modsætning til det velundersøgte LWE-problem.

Selv efter SIKE blev brudt, er isogenibaseret kryptografi fortsat et aktivt forskningsområde. SQISign (Short Quaternion and Isogeny Signature) er en isogenibaseret signaturordning med signaturer på 177 byte mod ML-DSA's 2420 byte for niveau 2 — de mindste kendte PQC-signaturer. SQISign bruger det vanskelige problem at beregne en isogeni med en foreskrevet grad mellem to givne supersingulære kurver, formaliseret som problemet med endomorfiringen. FESTA (Fast Encryption from Supersingular Torsion Attacks) er et nyt KEM-design, der undgår de ekstra hjælpedata om torsionspunkter, som gjorde SIDH sårbar. CTIDH (Constant-Time CSIDH) forbedrer CSIDH's ydeevne. Disse ordninger holder forskningen i isogenier relevant, selv efter SIKE blev fjernet.

En isogeni er en rational afbildning phi: E -> E', som er en gruppehomomorfi, og hvis grad er lig med størrelsen på dens kerne. Velus formler beregner billedkurven og afbildningen ud fra kerneundergruppen. Isogenigrafer organiserer kurver som toppunkter med l-isogenikanter, der danner (l+1)-regulære Ramanujan-grafer. Supersingulære kurver, som bruges i SIDH/SIKE/CSIDH, har isogenigrafer med stærk ekspansion. Problemerne SSIP og CSSI ligger til grund for isogenisikkerheden. SIDH bruger torsionspunktstrukturen med skiftevis 2- og 3-isogenikæder. Beregning af endomorfiringen er ækvivalent med SSIP. SQISign og FESTA repræsenterer aktive forskningsretninger efter SIKE, der bruger vanskeligheden ved beregning af endomorfiringen.