Isogenibaserad kryptografis framtid

Castryck-Decrus knäckning av SIKE i juli 2022 förändrade isogenifältet dramatiskt. Före knäckningen var isogenibaserad kryptografi en lovande postkvantumriktning med små nyckelstorlekar, aktiva standardiseringsinsatser och en växande forskargrupp. Efter SIKE:s fall tvingades området ompröva sina grundvalar. Den centrala frågan är vilka delar av isogenibaserad kryptografi som fortfarande är svåra efter de nya Richelot-isogeniteknikerna. Svaret verkar vara att svårighetsproblem baserade på endomorfismringar (som används i SQISign) och kommutativa klassgruppsverkningar (CSIDH) fortfarande håller. Det är läckaget av hjälptorsionspunkter som är specifikt för SIDH som har brutits, inte isogenier i allmänhet.

SQISign (Short Quaternion and Isogeny Signature, De Feo et al., 2020) är det mest kompakta kända postkvantumsignaturschemat. Publik nyckel: 64 byte (en supersingulär j-invariant). Signatur: 177 byte på nivå 1. Som jämförelse har ML-DSA (Dilithium) publika nycklar på 1312 byte och signaturer på 2420 byte på nivå 2. SQISign:s säkerhet bygger på Deuring-korrespondensen: problemet att beräkna en isogeni av föreskriven grad mellan två givna supersingulära kurvor är likvärdigt med att hitta ett ideal i kvaternionalgebran för endomorfismringen. SQISign använder ett Fiat-Shamir-baserat identifieringsschema för detta svåra problem och skapar en signatur som en komprimerad representation av svarisisogenin.

SQISigns kompakthet medför en betydande prestandakostnad. Signering kräver att en isogeni av stor grad (omkring p^{1/4}) beräknas genom att ideal omvandlas till isogenier i kvaternionalgebran — en beräkningsintensiv operation som tar ungefär 60–600 sekunder på en stationär CPU, beroende på parameteruppsättningen. Verifiering går snabbare (omkring 200 ms), men är fortfarande mycket långsammare än verifiering av ML-DSA (mikrosekunder). SQISign 2.0 (2023) förbättrade prestandan 100 gånger genom algoritmförbättringar, vilket minskade signeringstiden till 1–10 sekunder. SQISign HD (high degree) och andra varianter fortsätter att optimeras. Den avsedda användningen är tillämpningar där bandbredden är starkt begränsad (IoT-certifikat, blockkedjedata och rymdkommunikation) och beräkningshastigheten är mindre viktig.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) är ett KEM som uttryckligen utformats för att undvika SIDH-liknande läckage av torsionspunkter. Den centrala designidén är att FESTA, i stället för att publicera phi_A(P_B) och phi_A(Q_B) som i SIDH, använder en annan isogenistruktur där krypterarens publika nyckel endast är bildkurvan (inga torsionsbilder). FESTA använder 2^n-isogenier på ett modifierat sätt som möjliggör dekryptering utan motpartens bilder av torsionsbasen. Tidiga analyser tyder på att FESTA står emot Castryck-Decru-attacken tack vare sin annorlunda struktur för hjälpinformation. FESTA är en lovande riktning, men kräver mer kryptoanalytisk granskning — isogeniforskarna är försiktiga efter SIKE:s överraskande knäckning.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) hanterar CSIDH:s svaghet vad gäller kvantsäkerhet. CSIDH:s lilla primtal p = 512 bitar ger endast cirka 65 bitars kvantsäkerhet (Kuperbergs subexponentiella algoritm). SCALLOP använder en annan algebraisk struktur: kurvor med komplex multiplikation av stora imaginära kvadratiska ordningar, där klassgruppen är särskilt utformad för att stå emot kvantattacker av Kuperberg-typ. SCALLOP uppnår en större effektiv klassgrupp med parametrar som ger 128-bitars kvantsäkerhet vid mindre parameterstorlekar än CSIDH-5000. Kompromissen är att SCALLOP:s algebraiska uppbyggnad är mer komplex och har fått mindre oberoende analys än CSIDH.

Med tanke på isogenischemanas unika kompakthet (SQISigns 177-byte-signaturer och CSIDH:s 64-byte-nycklar) och deras andra svårighetsantaganden än gitterbaserade scheman kombinerar hybridkonstruktioner isogeni- och gitterkomponenter för försvar i flera lager. Ett hybrid-KEM kapslar in med ML-KEM-512 OCH med CSIDH-512 och hashar båda hemligheterna tillsammans. Den kombinerade nyckeln kräver att både ML-KEM (LWE-svårigheten) och CSIDH (klassgruppsverkan) bryts. Om någon av dem förblir obruten är hybriden säker. Detta förhållningssätt med kryptografisk agilitet rekommenderas av NIST och NSA för organisationer som vill ha ytterligare försäkran utöver en enskild postkvantumprimitiv, särskilt när tidsplanerna för kvantdatorer är osäkra.

Isogenibaserade nollkunskapsbevis är ett framväxande forskningsområde. Isogenivägsproblemet (hitta phi: E -> E' givet båda kurvorna) kan fungera som ett svårt problem för bevis-av-kunskap-scheman. Sigmaprotokoll för "Jag känner till en isogeni från E till E'" möjliggör autentisering utan att isogenin avslöjas. Vero (2022) demonstrerar ett praktiskt isogenibaserat ZK-bevissystem. Dessa ZK-bevis är naturligt kompakta (påståendet består endast av två j-invarianter), men är för närvarande för långsamma för praktisk driftsättning. När beräkningen av isogenier förbättras kan isogenibaserade ZK-bevis erbjuda alternativ till gitterbaserade eller hashbaserade bevis i tillämpningar där mångfald av säkerhetsantaganden värdesätts.

Isogenitekniker är inte bara relevanta för postkvantumkryptografi — de används även inom klassisk kryptografi med elliptiska kurvor. Schoof-Elkies-Atkin-algoritmen (SEA) för att räkna punkter på elliptiska kurvor använder isogenier för att beräkna Frobenius-spåret, vilket möjliggör effektiv generering av säkra parametrar för elliptiska kurvor. Isogenier förekommer i förbättringar av Pollards rho-metod för beräkning av ECDLP. CM-metoden (Complex Multiplication) för att konstruera kurvor med föreskriven ordning använder klasspolynom, som i grunden är isogeniobjekt. Isogenibaserade verktyg för kryptoanalys (för att hitta isogenivägar av slät grad) används för att utvärdera föreslagna parametrar för elliptiska kurvor med avseende på dolda bakdörrar — något som är direkt relaterat till farhågorna kring Dual EC DRBG.

År 2024 hade inget isogenibaserat schema standardiserats av NIST eller andra större organisationer. NIST:s PQC-process standardiserade ML-KEM, ML-DSA, SLH-DSA och FN-DSA — alla gitter- eller hashbaserade. NIST genomför en andra omgång av utvärderingen av PQC-signaturer; SQISign skickades in men möter prestandaproblem. Isogeniforskarna arbetar mot en mer mogen SQISign 3.0 med praktiska signeringstider (målet är under en sekund). ISO och ETSI har inte standardiserat något isogenischema. Den troligaste vägen till standardisering på kort sikt är SQISign för nischade tillämpningar som kräver minimala signaturstorlekar, eventuellt som en informativ standard snarare än en obligatorisk primitiv. En bred driftsättning kräver prestandaförbättringar med flera storleksordningar.

Aktiva forskningsinriktningar inom isogenibaserad kryptografi år 2024: (1) SQISign-varianter (SQISign 2.0, HD, Fast SQISign) som förbättrar signeringsprestandan mot körning på under en sekund. (2) Analys av kvantsäkerheten hos CSIDH och dess varianter — att förfina uppskattningarna av Kuperberg-attacken och utforska algebraiska strukturer som står emot den. (3) Nya svårighetsantaganden — beräkningar i supersingulära endomorfismringar och modulproblem över imaginära kvadratiska ringar. (4) Isogenibaserade oblivious PRF:er och tillämpningar i integritetsskyddande protokoll. (5) Hårdvaruimplementationer av isogeniaritmetik — med utnyttjande av FPGA-parallellism för CSIDH:s klassgruppsverkan. (6) Integration av isogenibaserade gruppverkningar med generiska ramverk för kryptografi med gruppverkningar för nya scheman för funktionskryptering och attributbaserade scheman.

Knäckningen av SIKE kan ge intrycket att man helt bör överge kryptografi baserad på isogenier. Kryptosamhället intar motsatt ståndpunkt: knäckningen var värdefull just eftersom den visade vilka strukturer som är osäkra (SIDH:s läckage från torsionspunkter) och vilka som fortfarande är svåra att angripa (endomorfringar och klassgruppsverkningar). Det är fortfarande viktigt att studera isogenier av följande skäl: (1) mångfald inom postkvantumskryptografi — säkerhetsantaganden som inte bygger på gitter minskar systemrisken om LWE skulle knäckas; (2) SQISign ger unikt kompakta signaturer utan någon motsvarighet i dag; (3) isogenitekniker ger insikter i kryptanalys av elliptiska kurvor och validering av parametrar; (4) matematiken är vacker och fruktbar — verktygen som utvecklades i samband med knäckningen av SIKE förbättrade direkt förståelsen av endomorfringar för elliptiska kurvor, som används i andra sammanhang.

Efter knäckningen av SIKE 2022 fortsätter kryptografi med isogenier, men med andra hårdhetsantaganden. SQISign ger postkvantsäkra signaturer på 177 byte (de minsta kända), baserade på svårigheten hos endomorfringar; prestandan förbättras (målet är under en sekund). FESTA utformas kring SIDH:s läckage från torsionspunkter för KEM:er. SCALLOP siktar på 128 bitars kvantsäkerhet med orienterade kurvor. Hybridscheman med isogenier och gitter ger en mångfald av säkerhetsantaganden. Ingen isogenibaserad algoritm är för närvarande standardiserad. Standardisering av SQISign är den mest sannolika vägen på kort sikt. Knäckningen av SIKE gav en djupare förståelse för vad som måste döljas i isogeniprotokoll och ledde till nya matematiska verktyg som används inom elliptisk kurvkryptografi.