Fremtiden for isogenibasert kryptografi

Castryck-Decru-bruddet på SIKE i juli 2022 endret isogenifeltet dramatisk. Før bruddet var isogenibasert kryptografi en lovende postkvante-retning med små nøkkelstørrelser, aktive standardiseringsforsøk og et voksende fagmiljø. Etter at SIKE falt, måtte fagfeltet revurdere grunnlaget sitt. Det sentrale spørsmålet er: hvilke deler av isogenibasert kryptografi er fortsatt vanskelige etter de nye Richelot-isogeniteknikkene? Svaret ser ut til å være at vanskelighetsproblemene knyttet til endomorfismeringer (brukt i SQISign) og kommutative klassegruppehandlinger (CSIDH) fortsatt er intakte. Lekkasje fra SIDH-spesifikke ekstra torsjonspunkter er den ødelagte komponenten, ikke isogenier generelt.

SQISign (Short Quaternion and Isogeny Signature, De Feo et al., 2020) er den mest kompakte kjente postkvante-signaturordningen. Offentlig nøkkel: 64 byte (en supersingulær j-invariant). Signatur: 177 byte på nivå 1. Til sammenligning har ML-DSA (Dilithium) offentlige nøkler på 1312 byte og signaturer på 2420 byte på nivå 2. Sikkerheten til SQISign bygger på Deuring-korrespondansen: problemet med å beregne en isogeni av foreskrevet grad mellom to gitte supersingulære kurver er ekvivalent med å finne et ideal i kvaternionalgebraen til endomorfismeringen. SQISign bruker en Fiat-Shamir-identifikasjonsordning over dette vanskelige problemet og produserer en signatur som en komprimert representasjon av responsisogenien.

SQISigns kompakthet har en høy ytelseskostnad. Signering krever beregning av en isogeni med stor grad (rundt p^{1/4}) ved hjelp av oversettelse fra ideal til isogeni i kvaternionalgebraen – en beregningsintensiv operasjon som tar omtrent 60–600 sekunder på en stasjonær CPU, avhengig av parametersettet. Verifisering går raskere (rundt 200 ms), men er fortsatt mye tregere enn verifisering av ML-DSA (mikrosekunder). SQISign 2.0 (2023) forbedret ytelsen 100 ganger gjennom algoritmiske forbedringer og reduserte signeringstiden til 1–10 sekunder. SQISign HD (high degree) og andre varianter fortsetter optimaliseringen. Målområdet er bruksområder der båndbredden er sterkt begrenset (IoT-sertifikater, blokkjede-data og romkommunikasjon), og beregningshastighet er mindre viktig.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) er en KEM som er utformet spesielt for å unngå torsjonspunktlekkasje i SIDH-stil. Den sentrale designideen er at FESTA, i stedet for å publisere phi_A(P_B) og phi_A(Q_B) slik som i SIDH, bruker en annen isogenistruktur der kryptererens offentlige nøkkel bare er bildeflaten til kurven (ingen torsjonsbilder). FESTA bruker 2^n-isogenier på en modifisert måte som muliggjør dekryptering uten bildene av motpartens torsjonsbasis. Foreløpige analyser tyder på at FESTA motstår Castryck-Decru-angrepet på grunn av den annerledes strukturen for ekstra informasjon. FESTA er en lovende retning, men krever grundigere kryptanalytisk granskning – isogenifeltet er forsiktig etter SIKEs overraskende brudd.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) tar sikte på å løse CSIDHs svakhet når det gjelder kvantesikkerhet. Det lille primtallet p på 512 bit i CSIDH gir bare ~65 biters kvantesikkerhet (Kuperbergs subeksponentielle algoritme). SCALLOP bruker en annen algebraisk struktur: kurver med kompleks multiplikasjon av store imaginære kvadratiske ordener, der klassegruppen er spesifikt utformet for å motstå kvanteangrep i Kuperberg-stil. SCALLOP oppnår en større effektiv klassegruppe med parametere som gir 128-biters kvantesikkerhet ved mindre parametersett enn CSIDH-5000. Avveiningen er at SCALLOPs algebraiske oppsett er mer komplekst og har fått mindre uavhengig analyse enn CSIDH.

Med tanke på isogeniordningenes unike kompakthet (SQISigns 177-byte-signaturer og CSIDHs 64-byte-nøkler) og deres andre vanskelighetsantakelser enn gitterordningene, kombinerer hybride konstruksjoner isogeni- og gitterkomponenter for forsvar i dybden. En hybrid KEM: kapsle inn med ML-KEM-512 OG med CSIDH-512, og hash begge hemmelighetene sammen. Den kombinerte nøkkelen krever at både ML-KEM (LWE-vanskelighet) og CSIDH (klassegruppehandling) brytes samtidig. Hvis én av dem forblir ubrutt, er hybriden sikker. Denne tilnærmingen med kryptografisk fleksibilitet støttes av NIST og NSA for organisasjoner som ønsker ekstra sikkerhet utover ett enkelt postkvanteprimitiv, særlig der tidslinjen for kvantedatamaskiner er usikker.

Isogenibaserte nullkunnskapsbevis er en fremvoksende forskningsretning. Isogenistiproblemet (å finne phi: E -> E' når begge kurvene er gitt) kan fungere som et vanskelig problem for kunnskapsbevisordninger. Sigma-protokoller for «Jeg kjenner en isogeni fra E til E'» muliggjør autentisering uten å avsløre isogenien. Vero (2022) demonstrerer et praktisk isogenibasert ZK-bevissystem. Disse ZK-bevisene er naturlig kompakte (utsagnet består bare av to j-invarianter), men er foreløpig for trege for praktisk bruk. Etter hvert som beregningen av isogenier forbedres, kan isogenibaserte ZK-bevis bli et alternativ til gitterbaserte eller hashbaserte bevis i bruksområder der mangfold av sikkerhetsantakelser verdsettes.

Isogeniteknikker er ikke bare relevante for postkvantekryptografi – de har også anvendelser innen klassisk kryptografi med elliptiske kurver. Schoof-Elkies-Atkin-algoritmen (SEA) for opptelling av punkter på elliptiske kurver bruker isogenier til å beregne Frobenius-sporet, noe som muliggjør effektiv generering av sikre parametere for elliptiske kurver. Isogenier inngår i forbedringer av Pollards rho for beregning av ECDLP. CM-metoden (Complex Multiplication) for å konstruere kurver med foreskrevet orden bruker klassepolynomer som i bunn og grunn er isogeniobjekter. Isogenibaserte kryptanalyseverktøy (for å finne isogenistier med glatt grad) brukes til å evaluere foreslåtte elliptiske kurveparametere for skjulte bakdører – direkte knyttet til bekymringen rundt Dual EC DRBG.

Per 2024 er ingen isogenibasert ordning standardisert av NIST eller andre ledende standardiseringsorganer. NISTs PQC-prosess standardiserte ML-KEM, ML-DSA, SLH-DSA og FN-DSA – alle gitter- eller hashbaserte. NIST gjennomfører en andre runde med evaluering av PQC-signaturer; SQISign er sendt inn, men møter ytelsesutfordringer. Isogenifeltet arbeider mot en mer moden SQISign 3.0 med praktiske signeringstider (mål: under ett sekund). ISO og ETSI har ikke standardisert noen isogeniordning. Den mest sannsynlige veien til standardisering på kort sikt er SQISign for nisjebruksområder som krever minimale signaturstørrelser, muligens som en informasjonsstandard snarere enn et obligatorisk primitiv. Utbredt bruk krever ytelsesforbedringer på en størrelsesorden.

Aktive forskningsretninger innen isogenibasert kryptografi per 2024: (1) SQISign-varianter (SQISign 2.0, HD og Fast SQISign) som forbedrer signeringsytelsen mot operasjoner under ett sekund. (2) Analyse av kvantesikkerheten til CSIDH og varianter – å stramme inn estimatene for Kuperberg-angrepet og utforske algebraiske strukturer som motstår det. (3) Nye vanskelighetsantakelser – beregning av supersingulære endomorfismeringer og modulproblemer over imaginære kvadratiske ringer. (4) Isogenibaserte oblivious PRF-er og anvendelser i personvernbevarende protokoller. (5) Maskinvareimplementasjoner av isogeniaritmetikk – utnyttelse av FPGA-parallellisme for CSIDHs klassegruppehandling. (6) Integrasjon av isogenibaserte gruppehandlinger med generiske rammeverk for gruppehandlingskryptografi for nye ordninger for funksjonell kryptering og attributtbaserte ordninger.

Bruddet på SIKE kan gi inntrykk av at man bør forkaste isogenibasert kryptografi fullstendig. Kryptografimiljøet ser det motsatt: Bruddet var verdifullt nettopp fordi det viste hvilke strukturer som er usikre (lekkasje av torsjonspunkter i SIDH), og hvilke som fortsatt er vanskelige å bryte (endomorfismeringer og virkninger av klassegrupper). Det er fortsatt viktig å studere isogenier av fire grunner: (1) mangfold i postkvantekryptografien – sikkerhetsantakelser som ikke bare bygger på gitterproblemer, reduserer systemrisikoen dersom LWE brytes; (2) SQISign gir uvanlig kompakte signaturer uten reell konkurranse i dag; (3) isogeniteknikker gir innsikt i kryptanalyse av elliptiske kurver og validering av parametere; (4) matematikken er vakker og fruktbar – verktøyene som ble utviklet i forbindelse med bruddet på SIKE, forbedret direkte forståelsen av endomorfismeringer for elliptiske kurver, som brukes i andre sammenhenger.

Etter bruddet på SIKE i 2022 fortsetter isogenibasert kryptografi med andre hardhetsantakelser. SQISign gir postkvantesignaturer på 177 byte (de minste som er kjent), basert på at problemet med endomorfismeringer er vanskelig; ytelsen blir stadig bedre (målet er under ett sekund). FESTA er utformet for å unngå SIDHs lekkasje av torsjonspunkter i KEM-er. SCALLOP sikter mot 128-biters kvantesikkerhet ved hjelp av orienterte kurver. Hybride isogeni- og gitterbaserte ordninger gir mangfold i sikkerhetsantakelsene. Ingen isogenibasert ordning er standardisert ennå. Standardisering av SQISign er den mest sannsynlige veien på kort sikt. Bruddet på SIKE ga en bedre forståelse av hva som må holdes skjult i isogeniprotokoller, og frembrakte nye matematiske verktøy som brukes i hele kryptografien for elliptiske kurver.