The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

Die Arbeit stellt einen allgemeinen Rahmen vor, der das SQIsign-Signaturschema durch die Einbeziehung von Level-Strukturen verallgemeinert, und liefert dabei eine neue explizite Deuring-Korrespondenz für supersinguläre elliptische Kurven mit Level-Strukturen sowie Lösungen für neue eingeschränkte Normgleichungen.

Das Wesentliche

Der SQInstructor: Ein neuer Schlüssel für die Post-Quanten-Welt

Stellen Sie sich vor, Sie wollen eine Nachricht verschicken, die so sicher ist, dass selbst ein Computer der Zukunft (ein „Quantencomputer") sie nicht knacken kann. Kryptografen nutzen dafür oft eine spezielle Art von Mathematik, die auf elliptischen Kurven basiert. Man kann sich diese Kurven wie komplizierte, geschwungene Schlangen vorstellen.

Das Problem: Wie beweist man, dass man ein Geheimnis kennt, ohne es zu verraten? Dafür gibt es das SQIsign-Verfahren. Es ist wie ein sehr cleveres Schloss, das nur mit einem speziellen Schlüssel (einem „Isogenie"-Pfad) geöffnet werden kann. SQIsign ist aktuell einer der besten Kandidaten für den neuen weltweiten Sicherheitsstandard.

Aber SQIsign hat einen Haken: Der Prozess, um den Schlüssel zu erstellen (das „Signieren"), ist sehr langsam und kompliziert. Die Autoren dieses Papers wollen das ändern. Sie stellen SQInstructor vor.

1. Die Idee: Nicht nur den Weg, sondern auch die Wegpunkte kennen

Stellen Sie sich vor, Sie müssen von Punkt A (Ihr öffentlicher Schlüssel) nach Punkt B (eine Herausforderung) reisen.

• Bei SQIsign (der alte Weg): Sie müssen einen Pfad finden, der genau durch einen bestimmten Punkt führt und dort „stoppt". Das ist wie ein Rätsel, bei dem Sie einen Weg finden müssen, der an einer bestimmten Stelle eine Mauer berührt und dort verschwindet. Das ist mathematisch sehr schwer zu berechnen.
• Bei SQInstructor (der neue Weg): Die Autoren sagen: „Warum nicht einfach verlangen, dass Sie einen bestimmten Wegpunkt (eine Gruppe von Punkten auf der Kurve) zu einem anderen Wegpunkt führen?"

Sie nutzen etwas, das sie Level-Strukturen nennen.

• Die Analogie: Stellen Sie sich die elliptische Kurve als ein riesiges, unsichtbares Labyrinth vor. Die „Level-Struktur" sind wie Schilder oder Markierungen an bestimmten Stellen im Labyrinth.
• Bei SQIsign mussten Sie einen Weg finden, der an einer Markierung endet.
• Bei SQInstructor sagen Sie: „Ich will einen Weg, der die Markierung A genau auf die Markierung B abbildet."

Das klingt vielleicht komplizierter, aber es ist eigentlich flexibler. Es ist wie der Unterschied zwischen „Finde einen Weg, der bei der roten Ampel stoppt" und „Finde einen Weg, der die rote Ampel in eine blaue Ampel verwandelt". Letzteres gibt dem Mathematiker mehr Freiheit, einen schnelleren Weg zu finden.

2. Die Brücke: Die Deuring-Korrespondenz

Um diese neuen Wege zu finden, nutzen die Autoren eine magische Brücke, die Deuring-Korrespondenz.

• Die Welt der Kurven: Hier sind die Berechnungen extrem schwer (wie das Lösen eines Sudoku in 4D).
• Die Welt der Quaternionen: Das ist eine abstrakte mathematische Welt (eine Art „Zahlen-Universum"), in der dieselben Probleme plötzlich sehr einfach sind (wie einfaches Kopfrechnen).

Die Autoren haben diese Brücke erweitert. Früher konnte man nur einfache Kurven über die Brücke transportieren. SQInstructor erlaubt es, auch die Kurven mit ihren Schildern (Level-Strukturen) über die Brücke zu bringen.

• Der Trick: Sie lösen das schwierige Problem im einfachen „Quaternionen-Universum", finden dort die perfekte Lösung und bringen sie dann zurück in die Welt der Kurven. Da sie die Schilder mitgenommen haben, passt die Lösung perfekt auf die neuen Anforderungen.

3. Zwei Arten, den Schlüssel zu bauen

Die Autoren zeigen zwei Wege, wie man SQInstructor praktisch anwendet:

• Der einfache Weg (1-dimensionale Isogenien):
  Dies ist wie ein Spaziergang auf einem schmalen Pfad. Es ist sehr sicher und gut für spezielle Anwendungen (wie Ring-Signaturen, bei denen man anonym bleiben will), aber es ist etwas langsamer. Die Autoren haben neue Algorithmen entwickelt, um diesen Pfad effizienter zu begehen, indem sie alte mathematische Werkzeuge (KLPT) neu组合ieren.

• Der schnelle Weg (2-dimensionale Isogenien):
  Dies ist wie ein Hochgeschwindigkeitszug. Hier nutzen sie eine modernere Technik, bei der sie nicht nur eine Kurve, sondern zwei gleichzeitig betrachten. Das ist viel schneller und führt zu sehr kompakten Signaturen.

  • Das Ergebnis: In ihren Tests war SQInstructor fast genauso schnell wie das aktuelle Top-Verfahren SQIsign, aber mit dem Vorteil, dass es theoretisch sicherer und flexibler ist.

4. Warum ist das wichtig?

• Schnelligkeit: Das Signieren von Nachrichten wird effizienter.
• Sicherheit: Das Verfahren basiert auf den gleichen harten mathematischen Problemen wie SQIsign, bietet aber mehr Optionen für zukünftige Anwendungen.
• Flexibilität: Durch die Nutzung von „Level-Strukturen" (den Schildern) können Kryptografen das System leichter an verschiedene Bedürfnisse anpassen, ohne die Sicherheit zu gefährden.

Zusammenfassung in einem Satz

Die Autoren haben ein neues, cleveres Schloss (SQInstructor) entwickelt, das die alten, langsamen Wege des Verschlüsselns durch eine neue Methode ersetzt: Statt einen Weg zu suchen, der an einer Stelle endet, suchen sie einen Weg, der bestimmte Markierungen auf der Karte von A nach B verschiebt – und das geht dank einer magischen mathematischen Brücke viel schneller und flexibler.

Fazit: SQInstructor ist wie ein Upgrade für die digitale Sicherheit der Zukunft: Es ist schneller, schlauer und hält den Quantencomputern stand.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures" auf Deutsch:

1. Problemstellung und Motivation

Die isogeniebasierte Kryptographie gilt als vielversprechender Kandidat für die Post-Quanten-Kryptographie. Das derzeit kompakteste Signaturverfahren in diesem Bereich ist SQIsign, das auf der Deuring-Korrespondenz basiert – einer Äquivalenz zwischen supersingulären elliptischen Kurven und Ordnungen einer Quaternionenalgebra.

Das ursprüngliche SQIsign-Verfahren leidet jedoch unter zwei Hauptproblemen:

1. Der Signierprozess ist komplex und langsam, da er das Lösen von quadratischen Gleichungen in der Quaternionenalgebra mittels des KLPT-Algorithmus erfordert.
2. Die Sicherheitsbeweise (insbesondere EUF-CMA) sind aufgrund der Einschränkungen des KLPT-Algorithmus schwierig zu führen.

Zwar haben neuere Ansätze mit höherdimensionalen Isogenien (HD-Isogenien) die Effizienz und die beweisbare Sicherheit verbessert, doch fehlt ein allgemeiner Rahmen, der die Rolle von Level-Strukturen (Basen von Torsionsuntergruppen elliptischer Kurven) systematisch in das Signatur-Schema integriert. Level-Strukturen wurden bisher oft nur implizit verwendet (z. B. in SIKE oder FESTA), aber nicht als explizites Designelement für generische Protokolle genutzt.

2. Methodik und Kernkonzept

Die Autoren führen SQInstructor ein, ein allgemeines Framework, das das SQIsign-Protokoll verallgemeinert, indem es Level-Strukturen explizit in die Herausforderungs- und Antwortphase integriert.

• Das Grundprinzip: Im Gegensatz zum klassischen SQIsign, bei dem die Antwort eine Isogenie ist, die einen bestimmten Punkt (Kern) auf Null abbildet, verlangt SQInstructor, dass die Antwort-Isogenie eine gewählte Level-Struktur (z. B. eine zyklische Untergruppe oder eine Basis der Torsionsgruppe) auf eine andere Level-Struktur abbildet.
• Verallgemeinerung der Deuring-Korrespondenz: Ein zentraler theoretischer Beitrag ist die explizite Erweiterung der Deuring-Korrespondenz auf supersinguläre elliptische Kurven mit Level-Strukturen. Die Autoren zeigen, wie Isogenien, die Level-Strukturen erhalten, mit links-idealen in Unterringen (Ordnungen) der Quaternionenalgebra korrespondieren. Dies ermöglicht die Konstruktion von Ordnungen $O(E, S)$, die von der gewählten Level-Struktur $S$ abhängen.
• Zwei Instantiierungen: Das Framework wird in zwei Varianten demonstriert:
  1. 1-dimensionale Isogenien: Basierend auf dem klassischen SQIsign-Ansatz unter Verwendung des KLPT-Algorithmus. Dies erfordert das Lösen von eingeschränkten Norm-Gleichungen in der Quaternionenalgebra.
  2. 2-dimensionale Isogenien: Ein moderner Ansatz, der effizientere Algorithmen (ähnlich wie im aktuellen NIST-Kandidaten SQIsign v2) nutzt, um Isogenien höheren Grades darzustellen.

3. Wichtige Beiträge

• Theoretische Verallgemeinerung: Die Autoren stellen eine explizite Deuring-Korrespondenz für Kurven mit Level-Strukturen bereit. Sie definieren, wie Ideale in den Ordnungen $O(E, S)$ konstruiert werden und wie diese mit Isogenien korrespondieren, die Level-Strukturen abbilden. Dies gilt auch für nicht-glätte Leveln (large non-smooth levels).
• Algorithmische Innovation (KLPT für Level-Strukturen): Für die 1-dimensionale Variante entwickeln sie modifizierte Versionen des KLPT-Algorithmus (namens ScalarSigningKLPT und BorelSigningKLPT). Diese Algorithmen lösen Norm-Gleichungen unter der Nebenbedingung, dass die resultierenden Ideale die Level-Struktur respektieren. Sie kombinieren bestehende Techniken (wie IdealSuborderEichlerNorm) mit neuen Rerandomisierungsschritten, um eine gleichverteilte Ausgabe zu gewährleisten.
• Sicherheitsanalyse:
  • Das Protokoll wird als Sigma-Protokoll analysiert. Es wird bewiesen, dass es 2-special sound ist, was bedeutet, dass zwei gültige Antworten auf unterschiedliche Herausforderungen die Berechnung eines nicht-trivialen Endomorphismus erlauben (was dem Problem des Endomorphismenrings entspricht).
  • Für die 2-dimensionale Variante wird die EUF-CMA-Sicherheit (Existential Unforgeability under Chosen Message Attack) im Modell mit Orakeln für Isogenien (Isogeny Oracles) bewiesen.
• Implementierung: Die Autoren liefern Proof-of-Concept-Implementierungen für beide Varianten (1D und 2D) und vergleichen diese mit dem Referenz-SQIsign.

4. Ergebnisse und Leistung

• 1-dimensionale Variante:
  • Ermöglicht die Konstruktion fortgeschrittener primitiver Signaturen wie Ring-Signaturen und Chameleon-Hashes, für die 2D-Isogenien derzeit weniger geeignet sind.
  • Eine Implementierung für NIST-I-Sicherheit ergibt einen öffentlichen Schlüssel von 186 Bytes und eine Signatur von 300 Bytes.
• 2-dimensionale Variante (State-of-the-Art):
  • Die Leistung ist mit dem aktuellen SQIsign-Kandidaten vergleichbar.
  • Benchmark-Ergebnisse: Auf einem AMD Ryzen 7000 Prozessor zeigen die Messungen nur geringfügige Unterschiede:
    • Schlüsselgenerierung: SQInstructor ist minimal langsamer (z. B. 102,9 vs. 101,3 Mcycles für NIST III).
    • Signieren: Ähnliche Zeiten (240,1 vs. 237,7 Mcycles).
    • Verifizieren: SQInstructor ist leicht langsamer (20,8 vs. 14,4 Mcycles), was auf die längeren (2,2)-Isogenie-Ketten zurückzuführen ist.
    • Größe: Die Signaturen sind etwas größer (272 vs. 224 Bytes für NIST III), da zusätzliche Daten für die Level-Struktur und die Isogenie-Darstellung benötigt werden.

5. Bedeutung und Ausblick

Das Paper SQInstructor ist ein wichtiger Schritt zur Generalisierung isogeniebasierter Kryptographie.

• Flexibilität: Es bietet einen einheitlichen Rahmen, der es erlaubt, verschiedene Level-Strukturen (Borel, Split-Cartan, Skalar) und Darstellungsformen (1D vs. HD) frei zu wählen.
• Brücke zwischen Theorie und Praxis: Durch die explizite Behandlung der Deuring-Korrespondenz für Level-Strukturen wird die theoretische Grundlage für zukünftige Protokolle gestärkt, die auf Torsionspunkten basieren.
• Praktische Relevanz: Die Demonstration, dass SQInstructor mit SQIsign konkurrierbare Leistung bietet, zeigt, dass die Integration von Level-Strukturen keine signifikanten Effizienzverluste verursacht, aber neue Möglichkeiten für komplexe kryptographische Primitive (wie Ring-Signaturen) eröffnet, die mit reinen HD-Isogenien schwer zu realisieren sind.

Zusammenfassend stellt SQInstructor eine robuste, sichere und effiziente Erweiterung des SQIsign-Paradigmas dar, das die mathematische Tiefe der Deuring-Korrespondenz nutzt, um neue kryptographische Anwendungen zu ermöglichen.