Die Zukunft isogeniebasierter Kryptografie

Der Bruch von SIKE durch Castryck und Decru im Juli 2022 hat das Gebiet der isogeniebasierten Kryptografie grundlegend verändert. Vor dem Bruch galt die isogeniebasierte Kryptografie mit kleinen Schlüsselgrößen, aktiven Standardisierungsbemühungen und einer wachsenden Community als vielversprechende Richtung für die Post-Quanten-Kryptografie. Nach dem Fall von SIKE musste das Gebiet seine Grundlagen neu bewerten. Die zentrale Frage lautet: Welche Aspekte der isogeniebasierten Kryptografie bleiben nach den neuen Richelot-Isogenie-Techniken schwierig? Die bisherige Antwort scheint zu sein: Die auf Endomorphismenringen basierende Schwierigkeit (verwendet in SQISign) und kommutative Gruppenwirkungen von Klassengruppen (CSIDH) bleiben intakt. Die undichte Stelle bei SIDH-spezifischen zusätzlichen Torsionspunkten ist der gebrochene Bestandteil, nicht Isogenien im Allgemeinen.

SQISign (Short Quaternion and Isogeny Signature, De Feo et al., 2020) ist das derzeit bekannteste Post-Quanten-Signaturverfahren mit der kleinsten Größe. Öffentlicher Schlüssel: 64 Byte (eine supersinguläre j-Invariante). Signatur: 177 Byte auf Level 1. Zum Vergleich: ML-DSA (Dilithium) hat auf Level 2 öffentliche Schlüssel mit 1312 Byte und Signaturen mit 2420 Byte. Die Sicherheit von SQISign beruht auf der Deuring-Korrespondenz: Das Problem, eine Isogenie mit vorgegebenem Grad zwischen zwei gegebenen supersingulären Kurven zu berechnen, ist äquivalent dazu, ein Ideal in der Quaternionenalgebra des Endomorphismenrings zu finden. SQISign verwendet über diesem schwierigen Problem ein Fiat-Shamir-Identifikationsverfahren und erzeugt eine Signatur als komprimierte Darstellung der Antwortisogenie.

Die Kompaktheit von SQISign ist mit erheblichen Leistungseinbußen verbunden. Für das Signieren muss eine Isogenie großen Grades (etwa p^{1/4}) berechnet werden, indem im Quaternionenring ein Ideal in eine Isogenie übersetzt wird – eine rechenintensive Operation, die je nach Parametersatz auf einer Desktop-CPU ungefähr 60–600 Sekunden dauert. Die Verifikation ist schneller (etwa 200 ms), aber immer noch deutlich langsamer als die Verifikation von ML-DSA (Mikrosekunden). SQISign 2.0 (2023) verbesserte die Leistung durch algorithmische Verbesserungen um den Faktor 100 und verkürzte die Signierzeit auf 1–10 Sekunden. SQISign HD (high degree) und andere Varianten werden weiter optimiert. Die Zielanwendungen sind Szenarien mit äußerst begrenzter Bandbreite (IoT-Zertifikate, Blockchain-Daten, Weltraumkommunikation), bei denen die Rechengeschwindigkeit zweitrangig ist.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) ist ein KEM, das ausdrücklich so entwickelt wurde, dass es keine Torsionspunkt-Leaks wie bei SIDH aufweist. Die zentrale Designidee besteht darin, dass FESTA statt phi_A(P_B) und phi_A(Q_B) wie bei SIDH eine andere Isogeniestruktur verwendet, bei der der öffentliche Schlüssel des Verschlüsselnden nur aus der Bildkurve besteht (ohne Torsionsbilder). FESTA verwendet 2^n-Isogenien auf modifizierte Weise, sodass die Entschlüsselung ohne die Bilder der Torsionsbasis der Gegenpartei möglich ist. Erste Analysen deuten darauf hin, dass FESTA aufgrund seiner andersartigen Struktur der Zusatzinformationen dem Angriff von Castryck und Decru widersteht. FESTA ist eine vielversprechende Richtung, erfordert aber noch eine eingehendere kryptanalytische Untersuchung – nach dem überraschenden Bruch von SIKE ist die Isogenie-Community vorsichtig.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) befasst sich mit der Schwäche der Quantensicherheit von CSIDH. Die kleine Primzahl p = 512 Bit von CSIDH bietet aufgrund von Kuperbergs subexponentiellem Algorithmus nur etwa 65 Bit Quantensicherheit. SCALLOP verwendet eine andere algebraische Struktur: Kurven mit komplexer Multiplikation durch große imaginär-quadratische Ordnungen, deren Klassengruppe gezielt so gestaltet ist, dass sie Kuperberg-ähnlichen Quantenangriffen widersteht. SCALLOP erreicht eine größere effektive Klassengruppe und bietet mit kleineren Parametern als CSIDH-5000 eine 128-Bit-Quantensicherheit. Der Nachteil: Der algebraische Aufbau von SCALLOP ist komplexer, und das Verfahren wurde unabhängigerweise weniger intensiv analysiert als CSIDH.

Angesichts der besonderen Kompaktheit isogeniebasierter Verfahren (Signaturen von SQISign mit 177 Byte, Schlüssel von CSIDH mit 64 Byte) und ihrer von Gitterverfahren verschiedenen Sicherheitsannahmen kombinieren hybride Konstruktionen isogenie- und gitterbasierte Komponenten zur gestaffelten Absicherung. Ein hybrides KEM kapselt mit ML-KEM-512 UND mit CSIDH-512 und hasht anschließend beide Geheimnisse zusammen. Um den kombinierten Schlüssel zu brechen, müssten sowohl ML-KEM (Schwierigkeit von LWE) als auch CSIDH (Gruppenwirkung der Klassengruppe) gleichzeitig gebrochen werden. Solange eines der beiden Verfahren ungebrochen bleibt, ist das hybride Verfahren sicher. Dieser Ansatz der kryptografischen Agilität wird von NIST und NSA für Organisationen empfohlen, die über ein einzelnes Post-Quanten-Verfahren hinaus zusätzliche Sicherheit wünschen – insbesondere wenn die Zeitpläne für Quantencomputer ungewiss sind.

Isogeniebasierte Zero-Knowledge-Beweise sind eine aufstrebende Forschungsrichtung. Das Isogeniepfadproblem (finde phi: E -> E' bei gegebenen beiden Kurven) kann als schwieriges Problem für Beweise der Kenntnis dienen. Sigma-Protokolle für „Ich kenne eine Isogenie von E nach E'“ ermöglichen eine Authentifizierung, ohne die Isogenie offenzulegen. Vero (2022) demonstriert ein praxisnahes isogeniebasiertes ZK-Beweissystem. Diese ZK-Beweise sind von Natur aus kompakt (die Aussage besteht nur aus zwei j-Invarianten), derzeit aber noch zu langsam für den praktischen Einsatz. Mit Verbesserungen bei der Isogenieberechnung könnten isogeniebasierte ZK-Beweise Alternativen zu gitter- oder hashbasierten Beweisen bieten, wenn eine Vielfalt von Sicherheitsannahmen wünschenswert ist.

Isogenie-Techniken sind nicht nur für die Post-Quanten-Kryptografie relevant, sondern finden auch in der klassischen Kryptografie mit elliptischen Kurven Anwendung. Der Schoof-Elkies-Atkin-Algorithmus (SEA) zur Punktzählung auf elliptischen Kurven verwendet Isogenien zur Berechnung der Frobenius-Spur und ermöglicht dadurch die effiziente Erzeugung sicherer Parameter für elliptische Kurven. Isogenien kommen bei Verbesserungen von Pollards Rho-Verfahren zur Berechnung des ECDLP zum Einsatz. Die CM-Methode (Complex Multiplication) zur Konstruktion von Kurven mit vorgegebener Ordnung verwendet Klassenpolynome, die im Kern Isogenieobjekte sind. Isogeniebasierte kryptanalytische Werkzeuge (zum Finden von Isogeniepfaden mit glattem Grad) werden eingesetzt, um vorgeschlagene Parameter elliptischer Kurven auf versteckte Hintertüren zu prüfen – ein direkter Zusammenhang mit der Problematik des Dual EC DRBG.

Stand 2024 ist kein isogeniebasiertes Verfahren von NIST oder anderen großen Standardisierungsgremien standardisiert. Im NIST-PQC-Prozess wurden ML-KEM, ML-DSA, SLH-DSA und FN-DSA standardisiert – allesamt gitter- oder hashbasierte Verfahren. NIST führt derzeit eine zweite Runde zur Bewertung von PQC-Signaturen durch; SQISign wurde eingereicht, steht jedoch vor Bedenken hinsichtlich der Leistung. Die Isogenie-Community arbeitet an einem ausgereifteren SQISign 3.0 mit praxisnahen Signierzeiten (Ziel: unter einer Sekunde). ISO und ETSI haben bisher kein isogeniebasiertes Verfahren standardisiert. Der wahrscheinlichste Weg zur kurzfristigen Standardisierung ist SQISign für Nischenanwendungen, die minimale Signaturgrößen benötigen, möglicherweise als informativer Standard statt als verpflichtendes Verfahren. Eine breite Einführung erfordert eine Verbesserung der Leistung um Größenordnungen.

Aktive Forschungsrichtungen in der isogeniebasierten Kryptografie im Jahr 2024: (1) SQISign-Varianten (SQISign 2.0, HD, Fast SQISign), die die Signierleistung in Richtung einer Ausführung unter einer Sekunde verbessern. (2) Analyse der Quantensicherheit von CSIDH und seinen Varianten – genauere Schätzungen für den Kuperberg-Angriff und die Erforschung algebraischer Strukturen, die ihm widerstehen. (3) Neue Sicherheitsannahmen – Berechnungen von Endomorphismenringen supersingulärer Kurven und Modulprobleme über imaginär-quadratischen Ringen. (4) Isogeniebasierte oblivious PRFs und Anwendungen in datenschutzfreundlichen Protokollen. (5) Hardwareimplementierungen isogeniebasierter Arithmetik – Nutzung der FPGA-Parallelität für die Gruppenwirkung der Klassengruppe von CSIDH. (6) Integration isogeniebasierter Gruppenwirkungen in Frameworks für allgemeine Gruppenwirkungen, um neue Verfahren für funktionale Verschlüsselung und attributbasierte Verfahren zu entwickeln.

Das Brechen von SIKE könnte nahelegen, die isogenienbasierte Kryptografie vollständig aufzugeben. Die kryptografische Gemeinschaft sieht das anders: Der Angriff war gerade deshalb wertvoll, weil er gezeigt hat, welche Strukturen unsicher sind (das Torsionspunkt-Leck von SIDH) und welche weiterhin schwer zu lösen sind (Endomorphismenringe, Aktionen von Klassengruppen). Die Erforschung von Isogenien bleibt aus mehreren Gründen wichtig: (1) Diversifizierung für die Postquantenkryptografie – Sicherheitsannahmen jenseits von Gittern verringern das systemische Risiko, falls LWE gebrochen wird; (2) SQISign bietet einzigartig kompakte Signaturen, für die es derzeit keine vergleichbare Alternative gibt; (3) Isogenientechniken liefern Erkenntnisse für die Kryptoanalyse elliptischer Kurven und die Validierung von Parametern; (4) die Mathematik ist elegant und produktiv – die für den Angriff auf SIKE entwickelten Werkzeuge haben das Verständnis von Endomorphismenringen elliptischer Kurven, die in anderen Zusammenhängen verwendet werden, direkt verbessert.

Nach dem Brechen von SIKE im Jahr 2022 wird die Isogenienkryptografie mit anderen Härteannahmen weiterentwickelt. SQISign bietet 177 Byte große Postquanten-Signaturen (die derzeit kleinsten bekannten), die auf der Schwierigkeit des Endomorphismenring-Problems beruhen; die Performance verbessert sich (Ziel: unter einer Sekunde). FESTA entwickelt KEMs, die das Torsionspunkt-Leck von SIDH umgehen. SCALLOP zielt mit orientierten Kurven auf 128-Bit-Quanten-Sicherheit. Hybride Verfahren aus Isogenien und Gittern bieten eine Vielfalt an Sicherheitsannahmen. Derzeit ist kein Isogenienverfahren standardisiert. Die Standardisierung von SQISign ist der wahrscheinlichste Weg in naher Zukunft. Das Brechen von SIKE hat das Verständnis dafür vertieft, was in Isogenienprotokollen verborgen bleiben muss, und neue mathematische Werkzeuge hervorgebracht, die in der gesamten Kryptografie elliptischer Kurven eingesetzt werden.