Isogeniapohjaisen kryptografian tulevaisuus

Heinäkuussa 2022 tapahtunut Castryck-Decru-hyökkäys muutti isogeniapohjaisen kryptografian kenttää merkittävästi. Ennen murtamista isogeniapohjainen kryptografia oli lupaava postkvanttisuuntaus, jolla oli pienet avainkoot, aktiivisia standardointipyrkimyksiä ja kasvava yhteisö. SIKE:n kaatumisen jälkeen alan oli arvioitava perusteensa uudelleen. Keskeinen kysymys kuuluu: mitkä isogeniapohjaisen kryptografian osa-alueet ovat edelleen vaikeita uusien Richelot-isogeniatekniikoiden jälkeen? Vastaus näyttää olevan, että endomorfismirenkaaseen perustuva vaikeus (jota käytetään SQISign:ssa) ja kommutatiiviset luokkaryhmätoiminnot (CSIDH) ovat edelleen murtamattomia. SIDH:lle ominainen ylimääräisten torsio-pisteiden vuoto on murtunut osa, eivät isogeniat yleisesti.

SQISign (Short Quaternion and Isogeny Signature, De Feo et al., 2020) on kompaktein tunnettu postkvantti-allekirjoitusjärjestelmä. Julkinen avain: 64 tavua (supersingulaarinen j-invariantti). Allekirjoitus: 177 tavua tasolla 1. Vertailun vuoksi ML-DSA:lla (Dilithium) on tasolla 2 1312 tavun julkiset avaimet ja 2420 tavun allekirjoitukset. SQISign:n turvallisuus perustuu Deuringin vastaavuuteen: ongelma laskea määrätyn asteen isogenia kahden annetun supersingulaarisen käyrän välillä vastaa ideaalialkion löytämistä endomorfismirenkaan kvaternionialgebrasta. SQISign käyttää tämän vaikean ongelman päällä Fiat-Shamir-tunnistusjärjestelmää, joka tuottaa allekirjoituksen pakattuna esityksenä vastausisogeniasta.

SQISign:n kompaktiudesta joutuu maksamaan erittäin paljon suorituskyvyssä. Allekirjoittaminen edellyttää suuren asteen isogenian (noin p^{1/4}) laskemista käyttämällä ideaali–isogenia-muunnosta kvaternionialgebrassa. Tämä on laskennallisesti raskas operaatio, joka kestää pöytätietokoneen suorittimella parametrivalinnasta riippuen noin 60–600 sekuntia. Varmennus on nopeampaa (noin 200 ms), mutta silti paljon hitaampaa kuin ML-DSA:n varmennus (mikrosekunteja). SQISign 2.0 (2023) paransi suorituskykyä satakertaisesti algoritmiparannusten ansiosta ja lyhensi allekirjoittamisen 1–10 sekuntiin. SQISign HD (high degree) ja muut muunnelmat jatkavat optimointia. Tavoitteena ovat käyttökohteet, joissa kaistanleveys on erittäin rajallinen, kuten IoT-varmenteet, lohkoketjudata ja avaruusviestintä, ja joissa laskentanopeus on toissijainen.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) on KEM, joka on suunniteltu nimenomaisesti välttämään SIDH-tyyppinen torsio-pisteiden vuoto. Keskeinen suunnitteluidea on seuraava: sen sijaan, että julkaistaisiin SIDH:n tapaan phi_A(P_B) ja phi_A(Q_B), FESTA käyttää erilaista isogeniarakennetta, jossa salaajan julkinen avain on vain kuvakäyrä (ei torsio-pistekuvia). FESTA käyttää 2^n-isogenioita muokatulla tavalla, joka mahdollistaa salauksen purkamisen ilman toisen osapuolen torsio-kannan kuvapisteitä. Alustava analyysi viittaa siihen, että FESTA kestää Castryck-Decru-hyökkäyksen erilaisen ylimääräisen informaation rakenteensa ansiosta. FESTA on lupaava suunta, mutta se edellyttää laajempaa kryptanalyyttista tarkastelua — isogenia-ala suhtautuu varovaisesti SIKE:n yllättävän murtamisen jälkeen.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) pyrkii ratkaisemaan CSIDH:n kvanttiturvallisuuden heikkouden. CSIDH:n pieni 512-bittinen alkuluku p = 512 bits tarjoaa Kuperbergin alipolynomillisen algoritmin vuoksi vain noin 65 bitin kvanttiturvallisuuden. SCALLOP käyttää erilaista algebrallista rakennetta: käyriä, joilla on kompleksinen kertolasku suurten imaginaaristen kvadraattisten kertarenkaiden avulla ja joiden luokkaryhmä on suunniteltu erityisesti kestämään Kuperberg-tyyppisiä kvanttihyökkäyksiä. SCALLOP saavuttaa suuremman efektiivisen luokkaryhmän ja tarjoaa parametreilla 128-bittisen kvanttiturvallisuuden pienemmillä parametreilla kuin CSIDH-5000. Kompromissina SCALLOP:n algebrallinen rakenne on monimutkaisempi, ja sitä on analysoitu riippumattomasti vähemmän kuin CSIDH:ta.

Isogeniajärjestelmien ainutlaatuisen kompaktiuden (SQISign:n 177 tavun allekirjoitukset ja CSIDH:n 64 tavun avaimet) sekä niiden hilajärjestelmistä poikkeavien vaikeusoletusten vuoksi hybridikonstruktioissa yhdistetään isogenia- ja hilakomponentteja kerroksittaisen suojauksen saavuttamiseksi. Hybridikem: kapseloi avain sekä ML-KEM-512:lla ETTÄ CSIDH-512:lla ja hajauta molemmat salaisuudet yhdessä. Yhdistetyn avaimen murtaminen edellyttää sekä ML-KEM:n (LWE-vaikeus) että CSIDH:n (luokkaryhmätoiminta) murtamista samanaikaisesti. Jos jompikumpi niistä säilyy murtamattomana, hybridi on turvallinen. Tämä kryptografisen ketteryyden lähestymistapa on NIST:n ja NSA:n suosittelema organisaatioille, jotka haluavat yhden postkvanttiprimitiivin tarjoamaa lisävarmuutta, erityisesti silloin, kun kvanttitietokoneiden aikataulusta ei ole varmuutta.

Isogeniapohjaiset nollatietotodistukset ovat kehittyvä tutkimussuunta. Isogeniapolkuongelma (etsi phi: E -> E' kun molemmat käyrät tunnetaan) voi toimia tietämyksen osoitusjärjestelmien vaikeana ongelmana. Sigma-protokollat väitteen "Tiedän isogenian käyrästä E käyrään E'" todistamiseksi mahdollistavat tunnistautumisen ilman isogenian paljastamista. Vero (2022) havainnollistaa käytännöllistä isogeniapohjaista ZK-todistusjärjestelmää. Nämä ZK-todistukset ovat luonnostaan kompakteja, koska väite koostuu vain kahdesta j-invariantista, mutta ne ovat tällä hetkellä liian hitaita käytännön käyttöönottoon. Isogenioiden laskennan kehittyessä isogeniapohjaiset ZK-todistukset voivat tarjota vaihtoehtoja hila- tai hajautuspohjaisille todistuksille tilanteissa, joissa oletusten monipuolisuutta arvostetaan.

Isogeniatekniikat eivät liity ainoastaan postkvanttikryptografiaan, vaan niillä on sovelluksia myös klassisessa elliptisten käyrien kryptografiassa. Schoof-Elkies-Atkin (SEA) -algoritmi käyttää elliptisten käyrien pisteiden laskennassa isogenioita Frobeniuksen jäljen määrittämiseen, mikä mahdollistaa turvallisten elliptisten käyräparametrien tehokkaan tuottamisen. Isogenioita käytetään Pollardin rho-menetelmän parannuksissa ECDLP:n laskentaan. CM (Complex Multiplication) -menetelmä määrätyn kertaluvun käyrien muodostamiseen käyttää luokkien polynomeja, jotka ovat pohjimmiltaan isogeniaobjekteja. Isogeniapohjaisia kryptanalyysityökaluja (sileän asteen isogeniapolkujen etsimistä) käytetään ehdotettujen elliptisten käyräparametrien arviointiin piilotettujen takaovien varalta — tämä liittyy suoraan Dual EC DRBG:tä koskevaan huolenaiheeseen.

Vuonna 2024 NIST tai mikään muukaan keskeinen standardointiorganisaatio ei ole standardoinut isogeniapohjaista järjestelmää. NIST:n PQC-prosessissa standardoitiin ML-KEM, ML-DSA, SLH-DSA ja FN-DSA, jotka kaikki ovat hila- tai hajautuspohjaisia. NIST arvioi parhaillaan PQC-allekirjoitusten toisen kierroksen ehdotuksia; SQISign osallistuu arviointiin, mutta sen suorituskyky herättää huolta. Isogenia-yhteisö kehittää kypsempää SQISign 3.0 -versiota, jonka tavoitteena ovat käytännölliset allekirjoitusajat (alle sekunnin tavoite). ISO ja ETSI eivät ole standardoineet yhtäkään isogeniajärjestelmää. Todennäköisin lähiajan standardointipolku on SQISign:n käyttö erityisesti vähimmäiskokoisia allekirjoituksia vaativissa erikoissovelluksissa, mahdollisesti informatiivisena standardina pakollisen primitiivin sijaan. Laaja käyttöönotto edellyttää suuruusluokan parannuksia suorituskykyyn.

Isogeniapohjaisen kryptografian aktiivisia tutkimussuuntia vuonna 2024 ovat: (1) SQISign:n muunnelmat (SQISign 2.0, HD, Fast SQISign), joilla allekirjoittamisen suorituskykyä parannetaan kohti alle sekunnin suoritusaikaa. (2) CSIDH:n ja sen muunnelmien kvanttiturvallisuusanalyysi — Kuperberg-hyökkäyksen arvioiden tarkentaminen ja sille vastustuskykyisten algebrallisten rakenteiden tutkiminen. (3) Uudet vaikeusoletukset — supersingulaaristen endomorfismirenkaiden laskenta ja moduuliongelmat imaginaarisissa kvadraattisissa renkaissa. (4) Isogeniapohjaiset oblivious PRF:t ja niiden sovellukset yksityisyyttä säilyttävissä protokollissa. (5) Isogenia-aritmetiikan laitteistototeutukset — CSIDH:n luokkaryhmätoiminnan FPGA-rinnakkaisuuden hyödyntäminen. (6) Isogeniapohjaisten ryhmätoimintojen yhdistäminen yleisten ryhmätoimintojen kryptografian viitekehyksiin uusien funktionaalisen salauksen ja attribuuttipohjaisten järjestelmien kehittämiseksi.

SIKEn murtuminen saattaa antaa aiheen hylätä isogenioihin perustuva kryptografia kokonaan. Kryptografian yhteisö on kuitenkin päinvastaista mieltä: murtuminen oli arvokasta juuri siksi, että se osoitti, mitkä rakenteet eivät ole turvallisia (SIDH:n torsionipisteiden vuotaminen) ja mitkä ovat edelleen vaikeita (endomorfismirenkaat ja luokkaryhmien toiminta). Isogenioiden tutkiminen on edelleen tärkeää seuraavista syistä: (1) postkvanttinen monipuolisuus – hilojen lisäksi tarvittavat turvallisuusoletukset pienentävät järjestelmäriskiä, jos LWE murtuu; (2) SQISign tarjoaa poikkeuksellisen kompakteja allekirjoituksia, joille ei tällä hetkellä ole kilpailijoita; (3) isogeniatekniikat auttavat elliptisten käyrien kryptanalyysissä ja parametrien validoinnissa; (4) matematiikka on kaunista ja hedelmällistä – SIKEn murtamista varten kehitetyt työkalut paransivat suoraan ymmärrystä elliptisten käyrien endomorfismirenkaista, joita käytetään myös muissa yhteyksissä.

SIKEn vuonna 2022 tapahtuneen murtumisen jälkeen isogeniakryptografia jatkaa kehitystään erilaisten vaikeusolettamien pohjalta. SQISign tarjoaa 177 tavun postkvanttisignatuureja, jotka ovat pienimpiä tällä hetkellä tunnettuja, ja perustuu endomorfismirenkaiden vaikeuteen. Suorituskyky paranee jatkuvasti, ja tavoitteena on alle sekunnin suorituskyky. FESTA-ratkaisut kiertävät SIDH:n torsionipisteiden vuotamisen KEM-järjestelmissä. SCALLOP tavoittelee 128-bittistä kvanttiturvallisuutta orientoitujen käyrien avulla. Isogenia- ja hilamenetelmien hybridijärjestelmät tarjoavat monipuolisempia vaikeusolettamia. Yhtäkään isogeniapohjaista järjestelmää ei ole tällä hetkellä standardoitu. SQISignin standardointi on todennäköisin lähitulevaisuuden etenemisreitti. SIKEn murtuminen syvensi ymmärrystä siitä, mitä isogeniaprotokollissa on piilotettava, ja tuotti uusia matemaattisia työkaluja, joita käytetään laajasti elliptisten käyrien kryptografiassa.