De toekomst van isogenie-gebaseerde cryptografie

De kraak van SIKE door Castryck-Decru in juli 2022 heeft het veld van cryptografie op basis van isogenieën ingrijpend veranderd. Voor de kraak was cryptografie op basis van isogenieën een veelbelovende richting voor post-kwantumcryptografie, met kleine sleutelgroottes, actieve standaardisatie-inspanningen en een groeiende gemeenschap. Na de val van SIKE moest het veld zijn grondslagen opnieuw onderzoeken. De kernvraag is: welke aspecten van cryptografie op basis van isogenieën blijven moeilijk na de nieuwe technieken voor Richelot-isogenieën? Het antwoord lijkt te zijn: moeilijkheid op basis van endomorfismenringen (gebruikt in SQISign) en commutatieve klassengroepacties (CSIDH) blijven intact. De lekkage van SIDH-specifieke aanvullende torsiepunten is het gebroken onderdeel, niet isogenieën in het algemeen.

SQISign (Short Quaternion and Isogeny Signature, De Feo et al., 2020) is het meest compacte bekende post-kwantumhandtekeningsschema. Openbare sleutel: 64 bytes (een supersinguliere j-invariant). Handtekening: 177 bytes op niveau 1. Ter vergelijking: ML-DSA (Dilithium) heeft openbare sleutels van 1312 bytes en handtekeningen van 2420 bytes op niveau 2. De beveiliging van SQISign berust op de correspondentie van Deuring: het probleem van het berekenen van een isogenie met een voorgeschreven graad tussen twee gegeven supersinguliere krommen is gelijkwaardig aan het vinden van een ideaal in de quaternionenalgebra van de endomorfismenring. SQISign gebruikt een Fiat-Shamir-identificatieschema voor dit moeilijke probleem en produceert een handtekening als een gecomprimeerde weergave van de antwoordisogenie.

De compactheid van SQISign brengt hoge prestatiekosten met zich mee. Voor het ondertekenen moet een isogenie met een grote graad (ongeveer p^{1/4}) worden berekend met behulp van de vertaling van idealen naar isogenieën in de quaternionenalgebra — een rekenintensieve bewerking die op een desktop-CPU ongeveer 60-600 seconden duurt, afhankelijk van de parameterinstelling. Verificatie is sneller (ongeveer 200 ms), maar nog steeds veel langzamer dan verificatie van ML-DSA (microseconden). SQISign 2.0 (2023) verbeterde de prestaties honderdvoudig door algoritmische verbeteringen, waardoor ondertekenen 1-10 seconden duurt. SQISign HD (high degree) en andere varianten blijven optimaliseren. De beoogde toepassing bestaat uit gebruikssituaties waarin de bandbreedte sterk beperkt is (IoT-certificaten, blockchaingegevens en ruimtecommunicatie) en rekensnelheid van ondergeschikt belang is.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) is een KEM die expliciet is ontworpen om lekkage van torsiepunten zoals bij SIDH te voorkomen. Een belangrijk inzicht in het ontwerp is dat FESTA, in plaats van phi_A(P_B) en phi_A(Q_B) te publiceren zoals bij SIDH, een andere isogeniestructuur gebruikt waarbij de openbare sleutel van de versleutelaar alleen de beeldkromme bevat (zonder beelden van torsiepunten). FESTA gebruikt 2^n-isogenieën op aangepaste wijze, zodat ontsleuteling mogelijk is zonder de beelden van de torsiebasis van de andere partij. Vroege analyses suggereren dat FESTA bestand is tegen de aanval van Castryck-Decru dankzij de andere structuur van de aanvullende informatie. FESTA is een veelbelovende richting, maar vereist meer cryptanalytische bestudering — de isogeniegemeenschap is voorzichtig na de onverwachte kraak van SIKE.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) pakt de zwakke kwantumbeveiliging van CSIDH aan. Het kleine priemgetal p van CSIDH, met 512 bits, biedt dankzij het subexponentiële algoritme van Kuperberg slechts ongeveer 65 bits kwantumbeveiliging. SCALLOP gebruikt een andere algebraïsche structuur: krommen met complexe vermenigvuldiging door grote imaginaire kwadratische orden, waarbij de klassengroep specifiek is ontworpen om bestand te zijn tegen kwantumaanvallen in de stijl van Kuperberg. SCALLOP bereikt een grotere effectieve klassengroep met parameters die 128-bits kwantumbeveiliging bieden bij kleinere parameteromvang dan CSIDH-5000. De afweging is dat de algebraïsche opzet van SCALLOP complexer is en minder onafhankelijke analyse heeft gekregen dan CSIDH.

Vanwege de unieke compactheid van schema's op basis van isogenieën (handtekeningen van 177 bytes voor SQISign en sleutels van 64 bytes voor CSIDH) en hun andere hardheidsaannames dan schema's op basis van roosters, combineren hybride constructies isogenie- en roostercomponenten voor extra beveiligingslagen. Een hybride KEM: kapsel een geheim in met ML-KEM-512 en met CSIDH-512, en hash beide geheimen samen. Om de gecombineerde sleutel te kraken, moeten zowel ML-KEM (hardheid van LWE) als CSIDH (klassengroepactie) tegelijk worden gebroken. Zolang een van beide niet is gekraakt, is het hybride schema veilig. Deze aanpak van cryptografische wendbaarheid wordt aanbevolen door NIST en NSA voor organisaties die extra zekerheid willen bovenop één afzonderlijke post-kwantumprimitief, vooral wanneer het tijdspad voor kwantumcomputers onzeker is.

Op isogenieën gebaseerde nulkennisbewijzen vormen een opkomende onderzoeksrichting. Het isogeniepadprobleem (vind phi: E -> E' gegeven beide krommen) kan dienen als moeilijk probleem voor bewijs-van-kennis-schema's. Sigma-protocollen voor "Ik ken een isogenie van E naar E'" maken authenticatie mogelijk zonder de isogenie te onthullen. Vero (2022) demonstreert een praktisch nulkennisbewijssysteem op basis van isogenieën. Deze nulkennisbewijzen zijn van nature compact (de bewering bestaat slechts uit twee j-invarianten), maar momenteel te traag voor praktische toepassing. Naarmate het berekenen van isogenieën verbetert, kunnen op isogenieën gebaseerde nulkennisbewijzen alternatieven bieden voor bewijzen op basis van roosters of hashes, wanneer waarde wordt gehecht aan diversiteit van aannames.

Isogenietechnieken zijn niet alleen relevant voor post-kwantumcryptografie — ze worden ook toegepast in klassieke cryptografie met elliptische krommen. Het Schoof-Elkies-Atkin-algoritme (SEA) voor het tellen van punten op elliptische krommen gebruikt isogenieën om het Frobenius-spoor te berekenen, waardoor veilige parameters voor elliptische krommen efficiënt kunnen worden gegenereerd. Isogenieën komen voor in verbeteringen van Pollards rho-algoritme voor het berekenen van ECDLP. De CM-methode (complexe vermenigvuldiging) voor het construeren van krommen met een voorgeschreven orde gebruikt klassepolynomen die in wezen isogenieobjecten zijn. Hulpmiddelen voor cryptanalyse op basis van isogenieën (voor het vinden van isogeniepaden met een gladde graad) worden gebruikt om voorgestelde parameters voor elliptische krommen te beoordelen op verborgen achterdeurtjes — direct gerelateerd aan de zorgen rond Dual EC DRBG.

Per 2024 is geen schema op basis van isogenieën gestandaardiseerd door NIST of andere belangrijke instanties. Het NIST-PQC-proces heeft ML-KEM, ML-DSA, SLH-DSA en FN-DSA gestandaardiseerd — allemaal gebaseerd op roosters of hashfuncties. NIST voert een tweede ronde uit van de evaluatie van PQC-handtekeningen; SQISign is ingediend, maar heeft te maken met zorgen over de prestaties. De isogeniegemeenschap werkt aan een meer volwassen SQISign 3.0 met praktische ondertekentijden (doel: minder dan een seconde). ISO en ETSI hebben geen enkel schema op basis van isogenieën gestandaardiseerd. Het waarschijnlijkste pad voor standaardisatie op korte termijn is SQISign voor nichetoepassingen die minimale handtekeninggroottes vereisen, mogelijk als informatieve standaard in plaats van als verplichte primitief. Brede toepassing vereist prestatieverbeteringen met een orde van grootte.

Actieve onderzoeksrichtingen in cryptografie op basis van isogenieën per 2024: (1) SQISign-varianten (SQISign 2.0, HD, Fast SQISign) die de prestaties van het ondertekenen verbeteren richting bewerkingen van minder dan een seconde. (2) Analyse van de kwantumbeveiliging van CSIDH en varianten — de schattingen van de aanval van Kuperberg aanscherpen en algebraïsche structuren onderzoeken die daartegen bestand zijn. (3) Nieuwe hardheidsaannames — berekeningen van endomorfismenringen van supersinguliere krommen en moduleproblemen over imaginaire kwadratische ringen. (4) Oblivious PRF's op basis van isogenieën en toepassingen in privacybeschermende protocollen. (5) Hardware-implementaties van isogenierekenkunde — FPGA-parallelisme benutten voor de klassengroepactie van CSIDH. (6) Integratie van op isogenieën gebaseerde groepsacties met algemene cryptografische kaders voor groepsacties voor nieuwe schema's voor functionele versleuteling en op attributen gebaseerde schema's.

De kraak van SIKE kan de indruk wekken dat we op isogenieën gebaseerde cryptografie helemaal moeten opgeven. De cryptografische gemeenschap kiest juist voor het tegenovergestelde: de kraak was waardevol, juist omdat die aantoonde welke structuren onveilig zijn (het lekken van torsiepunten in SIDH) en welke moeilijk blijven (endomorfismeringen en acties van klassengroepen). Isogenieën blijven belangrijk om vier redenen: (1) post-kwantumdiversiteit — beveiligingsaannames naast roosters verkleinen het systeemrisico als LWE wordt gekraakt; (2) SQISign biedt uniek compacte handtekeningen waarvoor momenteel geen concurrent bestaat; (3) isogenietechnieken helpen bij de cryptanalyse en parametervalidatie van elliptische krommen; (4) de wiskunde is elegant en productief — de hulpmiddelen die voor het kraken van SIKE zijn ontwikkeld, hebben het begrip van endomorfismeringen van elliptische krommen direct verbeterd en worden in andere contexten gebruikt.

Na de kraak van SIKE in 2022 gaat isogeniecryptografie verder met andere hardheidsaannames. SQISign biedt post-kwantumhandtekeningen van 177 bytes — de kleinste bekende — op basis van de hardheid van endomorfismeringen; de prestaties verbeteren en het doel is een uitvoeringstijd van minder dan één seconde. FESTA is ontworpen rond het lekken van torsiepunten in SIDH voor KEM's. SCALLOP richt zich op 128-bits kwantumbeveiliging met georiënteerde krommen. Hybride schema's met isogenieën en roosters zorgen voor diversiteit in beveiligingsaannames. Momenteel is geen enkel isogenieschema gestandaardiseerd. Standaardisatie van SQISign is de waarschijnlijkste route op korte termijn. De kraak van SIKE heeft het begrip versterkt van wat verborgen moet blijven in isogenieprotocollen en heeft nieuwe wiskundige hulpmiddelen opgeleverd die in de hele cryptografie van elliptische krommen worden gebruikt.