Wie kann Bitcoin Quantencomputern widerstehen? Ein Vergleich dreier gitterbasierter Signaturverfahren

Originalautor: Blockstream-Team

Originalzusammenstellung: Saoirse, Foresight News

Blockstream Research hat einen umfassenden Forschungsbericht über gitterbasierte Signaturen für Bitcoin veröffentlicht. Dieser Artikel fasst den Forschungsinhalt, die wichtigsten Erkenntnisse und die entsprechenden Empfehlungen zusammen. Der vollständige Bericht ist hier zugänglich.

Digitale Signaturen sind der Kernmechanismus zur Autorisierung von Bitcoin-Transaktionen, und die derzeit dafür verwendeten Schnorr- und ECDSA-Signaturen sind äußerst kostengünstig. 1994 bewies Shor, dass ein ausreichend leistungsfähiger Quantencomputer beide Signaturtypen brechen könnte. Während weiterhin darüber diskutiert wird, wann solche Maschinen verfügbar sein werden, müssen wir einen tragfähigen Plan für die Einführung post-quantenresistenter Signaturen entwickeln, bevor das Problem tatsächlich eintritt.

Gitterbasierte Signaturverfahren sind ein beliebter Kandidat, um bestehende Signaturen zu ersetzen. Die Gitterkryptographie hat eine Forschungsgeschichte von über einem Jahrhundert, und ihre kryptographischen Anwendungen werden seit fast drei Jahrzehnten entwickelt. In der Post-Quanten-Kryptographie bieten gitterbasierte Signaturen mehrere Vorteile: Die Gesamtgröße von öffentlichen Schlüsseln und Signaturen kann unter 1,6 Kilobyte liegen, und ihre algebraische Struktur verspricht, in Zukunft Multisignaturen, Schwellenwertsignaturen und kompakte Beweise zu unterstützen.

Dieser Bericht untersucht drei Verfahren: Dilithium, Falcon und Hawk. Für Leser, die mit Gitterkryptographie nicht vertraut sind, erläutern wir die Designprinzipien jedes Verfahrens, geben eine vollständige Beschreibung des Algorithmusablaufs und analysieren sie unter Gesichtspunkten wie Sicherheit, Leistung und praktischer Einführung (z. B. Wallet-Schlüsselableitung). Welche der drei Verfahren können tatsächlich auf der Bitcoin-Blockchain eingesetzt werden?

Bewertungskriterien

Bitcoin hat seine eigenen Einschränkungen bei der Auswahl des Signaturverfahrens, und diese Bewertung konzentriert sich auf vier Kernkriterien:

• On-Chain-Kosten: Eine der wichtigsten Kennzahlen ist die Gesamtgröße von öffentlichen Schlüsseln und Signaturen. Wenn ein Output ausgegeben wird, werden sowohl der öffentliche Schlüssel als auch die Signatur on-chain aufgezeichnet, und Full Nodes müssen jedes Byte herunterladen und speichern. Der Verifikationsaufwand ist ebenso entscheidend: Jede Signatur wird von allen Knoten im Netzwerk verifiziert, und eine langsame Verifikation würde das gesamte Netzwerk belasten.
• Implementierungskomplexität: Ob das Verfahren sicher implementiert werden kann, ist entscheidend. Wenn das Design Gleitkommaarithmetik oder empfindliches Gaußsches Sampling erfordert, könnte ein Implementierungsfehler oder ein Seitenkanalangriff wie Timing-Analyse den Schlüssel preisgeben. Um eine reibungslose Migration zu erreichen, ist die Implementierungskomplexität ein nicht zu vernachlässigender Faktor.
• Einführungsrisiko: Bei der tatsächlichen Integration in Bitcoin gibt es verschiedene praktische Hindernisse: die Wahl der Hash-Funktion auf Konsensebene (die meisten Kandidaten verwenden SHAKE, während Bitcoin SHA-256 verwendet), die Reproduzierbarkeit von Signaturergebnissen über Plattformen hinweg und ob das Signierverfahren den Speicherbeschränkungen von Hardware-Wallets entspricht.
• Entwicklungspotenzial: Die überwiegende Mehrheit der Bitcoin-Wallets verwendet den hierarchisch-deterministischen Mechanismus BIP-32: Aus einem einzigen Master-Public-Key können unendlich viele Child-Public-Keys abgeleitet werden, ohne Zugriff auf den privaten Schlüssel. Derzeit unterstützt kein standardisiertes post-quantenresistentes Signaturverfahren diese Funktion nativ, daher untersuchen wir die Kosten für das Hinzufügen dieser Fähigkeit; wir untersuchen auch verschiedene nicht-standardisierte Verfahrensvarianten, die zusätzliche Vorteile bieten könnten.

Welches Sicherheitsniveau sollte gewählt werden?

Bevor wir Größen vergleichen, müssen wir zunächst das angestrebte Sicherheitsniveau bestimmen, und diese Wahl ist nicht so einfach, wie es scheint. NIST klassifiziert Sicherheitsniveaus von 1 bis 5; höhere Niveaus bieten stärkere Sicherheit, aber auch größere Schlüssel- und Signaturgrößen.

Wir sind der Ansicht, dass Bitcoin mindestens Sicherheitsniveau 3 übernehmen sollte. Bitcoin-Outputs können jahrzehntelang unausgegeben bleiben, und wenn Fortschritte in der Kryptoanalyse das tatsächliche Sicherheitsniveau des Verfahrens verringern, wären Vermögenswerte durch geschwächte Schlüssel gesperrt und einem langfristigen Risiko ausgesetzt. Gitterbasierte Annahmen haben bereits fast drei Jahrzehnte öffentlicher Kryptoanalyse standgehalten, länger als die Forschungsgrundlage, als Bitcoin elliptische Kurven übernahm. Die komplexe algebraische Struktur der Gitterkryptographie lässt jedoch noch viele Wege für zukünftige Angriffe offen, und wir sollten nicht unsere gesamte langfristige Sicherheit darauf setzen.

Wichtige Mainstream-Produkte haben dieselbe Einschätzung getroffen. Apples iMessage-Protokoll PQ3 verwirft direkt Gitterparameter der Stufe 1 und verwendet durchgehend Parameter der Stufen 3 und 5; Cloudflare verwendet ML-KEM-768 (Stufe 3) in seiner Post-Quanten-TLS-Bereitstellung und erklärt, dass Stufe 1 derzeit zwar sicher erscheint, es jedoch notwendig ist, eine Sicherheitsmarge für jahrzehntelange zukünftige Kryptoanalyse zu reservieren. Der Sicherheitszeithorizont von Bitcoin ist sogar noch länger als bei beiden.

Die Erhöhung des Sicherheitsniveaus hat ihren Preis. Beispielsweise erhöht der Wechsel von Dilithium von Stufe 2 auf Stufe 3 die Gesamtgröße um etwa 1,5 Kilobyte. Der Bericht vergleicht Parametersätze auf allen Sicherheitsniveaus, sodass die Leser die Kompromisse selbst abwägen können. Der Fall Hawk beweist, dass konservative Sicherheitsüberlegungen nicht nur theoretisch sind.

Detaillierte Analyse der Kandidatenverfahren

Dilithium: Ein einfaches Design

Dilithium, von NIST als ML-DSA in FIPS 204 standardisiert, überträgt das Commitment-Challenge-Response-Paradigma der Schnorr-Signaturen auf die Modulgitter-Arithmetik.

Sein größtes Merkmal ist die Einfachheit. Alle Operationen in Dilithium sind Ganzzahloperationen: Ringoperationen, Matrix-Vektor-Multiplikation, Hashing und Rundung. Es gibt keine Gleitkommaarithmetik und kein diskretes Gaußsches Sampling. Es ist einfacher, sichere Implementierungen mit konstanter Laufzeit zu schreiben. Es ist auch der am weitesten verbreitete Kandidat, bereits integriert in OpenSSL, BoringSSL, AWS-LC und Apple CryptoKit.

Der Kompromiss ist die größere Größe. Auf Sicherheitsniveau 3 hat ML-DSA-65 einen öffentlichen Schlüssel von 1952 Byte und eine Signatur von 3309 Byte, insgesamt 5261 Byte, etwa das 55-fache der Gesamtgröße von Bitcoins nativem öffentlichem/privatem Schlüssel plus Signatur, was es zum größten der drei Verfahren auf demselben Sicherheitsniveau macht.

Für Bitcoin ist der wertvollste Aspekt von Dilithium, dass es das einzige der drei ist, das einer BIP-32-artigen Schlüsselableitung nahekommt. Die re-randomisierbare Schlüsselkonstruktion DilithiumRK kann Child-Keys aus Parent-Keys nur mit öffentlichen Informationen erzeugen. Der Bericht analysiert drei Varianten, einschließlich unserer vorgeschlagenen DilithiumRKS, bei der die Ableitungslogik vollständig in der Wallet-Software liegt und die Chain nur einen Standard-Verifizierer benötigt, um gewöhnliche ML-DSA-Signaturen zu verarbeiten. Keine der drei ist jedoch produktionsreif: Zwei Varianten erfordern Änderungen am Verifizierer, und DilithiumRKS selbst fehlt ein vollständiger Unfälschbarkeitsbeweis; alle Verfahren stützen sich auf eine netzwerkweit gemeinsame Matrix, die unter der Module-LWE-Annahme formal sicher ist, aber die Sicherheit aller Schlüssel an eine einzige Instanz bindet. Wir sind der Ansicht, dass die auf Dilithium basierende Public-Key-Ableitung derzeit nur ein Proof of Concept ist und in der Praxis nicht eingesetzt werden kann.

Falcon: Ein kompaktes Verfahren

Falcon, von NIST ausgewählt und als FN-DSA standardisiert, ist das kompakteste der drei. Auf Sicherheitsniveau 1 hat Falcon-512 eine kombinierte Größe von öffentlichem Schlüssel und Signatur von 1563 Byte; auf Stufe 5 beträgt Falcon-1024 insgesamt 3073 Byte. Falcon-1024 mit einer höheren Sicherheitsmarge ist sogar kleiner als Dilithium der Stufe 3.

Falcon verfolgt einen anderen Ansatz als Dilithium: ein Hash-and-Sign-Paradigma auf Basis von NTRU-Gittern. Der private Schlüssel des Signierers ist eine kurze Basis des Gitters; die Nachricht wird auf einen Punkt im Raum gehasht, und der Signierer verwendet die kurze Basis, um einen Gittervektor in der Nähe dieses Punktes zu finden. Der Punkt und der nahegelegene Vektor bilden zusammen die Signatur; die Verifikation prüft nur, ob der Vektor zum Gitter gehört und ausreichend nahe liegt. Die Implementierungsherausforderung besteht darin, den Vektor zu finden, ohne Informationen über die Basis preiszugeben. Frühe Verfahren GGH und NTRUSign wählten direkt nahegelegene Gitterpunkte aus und gaben mit jeder Signatur einige geometrische Informationen preis. Falcon übernimmt das GPV-Framework und sampelt nahegelegene Vektoren aus einer Gaußverteilung, was nachweislich die gesampelte Ausgabe unabhängig von der Basis macht und das Leckagerisiko eliminiert, aber die Implementierungsschwierigkeit des Samplers steigt erheblich.

Der Sampler ist die technische Schwachstelle von Falcon. Er arbeitet im komplexen Fourier-Bereich und erfordert Gleitkommaberechnungen. Unterschiedliche Prozessoren, Compiler und Compiler-Optimierungsoptionen können zu inkonsistenten Gleitkommaergebnissen führen. Dies ist nicht nur ein Kompatibilitätsproblem, sondern auch ein Sicherheitsproblem: Der GPV-Sicherheitsbeweis erfordert, dass der Signierer niemals zwei verschiedene kurze Vektoren für denselben Digest ausgibt; wenn die Signatur deterministisch wird, würden plattformbedingte Gleitkomma-Rundungsunterschiede diese Bedingung verletzen. Es gibt eine praktikable Lösung: Deterministisches Falcon kann Hardware-Gleitkomma durch Ganzzahl-Emulation ersetzen und auf allen Plattformen identische Signaturen erzeugen. Die Kosten sind eine etwa 15-fache Verlangsamung der Signiergeschwindigkeit und eine etwa 2-fache Verlangsamung der Schlüsselerzeugung.

Wichtig ist, dass die Verifikation nicht betroffen ist: Die Falcon-Verifikation ist vollständig ganzzahlig, deterministisch und auch die schnellste unter den Kandidaten. Diese asymmetrische Eigenschaft ist für Bitcoin sehr freundlich: Das Signieren wird einmalig von der Wallet beim Ausgeben einer Transaktion durchgeführt, während jede Signatur von allen Full Nodes im Netzwerk verifiziert wird. Eine 15-fache Verlangsamung des Signierens ist ein Kostenfaktor mit geringer Häufigkeit, und im Gegenzug erhalten wir plattformübergreifende Reproduzierbarkeit und Ganzzahlarithmetik, was wir als vernünftigen Kompromiss betrachten. Daher ist das Gleitkommaproblem ein Hindernis, das durch technische Mittel gelöst werden kann, und kein fataler Fehler.

Zwei Punkte sind zu beachten: Aufgrund struktureller Einschränkungen hat Falcon keine Parameter der Stufe 3; man muss entweder Stufe 1 oder Stufe 5 wählen. Aufgrund der Sicherheitsmarge empfehlen wir Falcon-1024. Zweitens verbraucht das Signieren viel Speicher: Der Sampler für den 1024-Parametersatz stützt sich auf einen vorberechneten Baum, der etwa 90 Kilobyte Speicher belegt. Hardware-Wallets können den Baum dynamisch Zweig für Zweig neu aufbauen und so den Speicherverbrauch auf 16 Kilobyte reduzieren, aber die Signierzeit verdoppelt sich. Langsameres Signieren auf Hardware-Geräten ist ein realer Kostenfaktor, aber immer noch akzeptabel.

Hawk: Ein gescheitertes Verfahren

Hawk zielte darauf ab, die Vorteile der beiden anderen Verfahren zu kombinieren: Hawk-512-Signaturen sind nur 555 Byte groß, kleiner als Falcon; das Signieren ist vollständig ganzzahlig, mit einem minimalen Speicherbedarf von nur 6 Kilobyte. Es war auch der einzige verbleibende gitterbasierte Kandidat in der dritten Runde des zusätzlichen Signaturwettbewerbs von NIST, und der Bericht widmet diesem Verfahren beträchtlichen Raum.

Der Kompromiss liegt in den Sicherheitsannahmen. Es stützt sich nicht auf die NTRU- oder SIS-Probleme, die jahrzehntelanger Kryptoanalyse ausgesetzt waren, sondern auf das Gitterisomorphieproblem und die One-more-SVP-Annahme, die beide eine relativ kurze Forschungsgeschichte haben.

Kurz vor Fertigstellung des Berichts entdeckten Straznickas und Weis von Anthropic einen strukturellen Fehler in Hawks Gitterkonstruktion: Die Dimension des SVP-Problems, das tatsächlich für die Schlüsselwiederherstellung gelöst werden muss, beträgt nur die Hälfte dessen, was die Designer beabsichtigt hatten. Die Sicherheitsbits der Schlüsselwiederherstellung der Kandidatenparametersätze wurden erheblich geschwächt. Die Forscher führten einen vollständigen End-to-End-Schlüsselwiederherstellungsangriff auf den für die Kryptoanalyse verwendeten Challenge-Parameter HAWK-256 durch; selbst unter Angriff bleiben die formal vorgeschlagenen HAWK-512 und HAWK-1024 praktisch unknackbar. Das Hawk-Team bestätigte die Gültigkeit des Angriffs und zog das Verfahren aus dem NIST-Prozess zurück; das Team erklärte, dass bei einer Behebung der Schwachstelle durch Verdoppelung der Parameter Hawks ursprünglicher Größenvorteil vollständig verschwinden würde.

Der Bericht behält den Hawk-Abschnitt bei, weil der Angriff auf algebraische Eigenschaften eines bestimmten Zahlkörpers abzielt und das Designparadigma nicht vollständig negiert. Ob ein Redesign die Schwachstelle vermeiden kann, bleibt eine offene Frage. Der Hawk-Vorfall bestätigt auch anschaulich unser Beharren auf konservativen Sicherheitsmargen: Ein Verfahren mit ausgezeichneter Größe und Geschwindigkeit, das mehrere Standardisierungsrunden durchlaufen hat, kann durch ein einziges Papier sein geschätztes Sicherheitsniveau drastisch reduziert sehen.

Vergleichstabelle der Verfahren

Alle Verfahren in der obigen Tabelle (einschließlich SPHINCS+) sind zustandslose Signaturen: Der Signierer muss keine vergangenen Signaturen aufzeichnen. Zustandsbehaftete hashbasierte Signaturen wie XMSS können kleinere Signaturgrößen erreichen, erfordern jedoch die Verwaltung des Signaturzustands; siehe den Sonderbericht zu hashbasierten Signaturen für einen Vergleich.

Viele Hindernisse bleiben für die Einführung

Falcon fehlt ein brauchbares Schlüsselableitungsschema. Das einzige öffentlich verfügbare BIP-32-artige Falcon-Ableitungsschema re-randomisiert die Basis des privaten Schlüssels, wodurch die obere Grenze der Signaturnorm drastisch erhöht wird und On-Chain-Signaturen auf etwa 23,7 Kilobyte anwachsen. Darüber hinaus erfüllen die Parameter des Schemas nicht seine eigenen Sicherheitsbedingungen, und die Behebung dieses Problems würde die Größe weiter erhöhen. Derzeit gibt es keine praktikable Implementierung der Falcon-Public-Key-Ableitung, was auch das wertvollste offene Problem ist, das im Bericht identifiziert wurde.

Der Falcon-Standard ist noch nicht finalisiert. Obwohl NIST Falcon ausgewählt hat, wurde der FN-DSA-Entwurf noch nicht offiziell veröffentlicht. Erst nach Abschluss der Standardisierung werden wir geprüfte Implementierungen, Testvektoren und Hardware-Unterstützung haben. Eine breite Akzeptanz kann das Risiko und die Schwierigkeit der Integration in die Konsensschicht von Bitcoin verringern. Wir empfehlen, auf die offizielle Veröffentlichung von FN-DSA zu warten; bis dahin bleibt Falcon in einem unfertigen Zustand.

Falcon-WS-Variante: Diese Variante lockert interne Parameter und stützt sich auf Rejection Sampling zur Kompensation, wodurch die Gesamtgröße auf 1114 Byte auf Stufe 1 und 2387 Byte auf Stufe 5 komprimiert wird, was die Größe im Vergleich zum ursprünglichen Falcon weiter reduziert. Diese Richtung hat Forschungswert, wird aber nicht in den offiziellen Standard aufgenommen und erfordert mehr kryptoanalytische Validierung. Bestehende Forschung hat Schwächen in den Beweisen der starken Unfälschbarkeit ihrer abgeleiteten Schemata gefunden (die gewöhnliche Unfälschbarkeit ist nicht betroffen).

Werden in Zukunft bessere Verfahren entstehen? Abgesehen von den oben genannten Verfahren reicht die Fiat-Shamir-Familie bis zu BLISS im Jahr 2013 zurück. Das neueste Ergebnis von Gärtner auf der CRYPTO 2025, basierend auf ausgereiften Annahmen, hat Papiergrößen, die mit Falcon vergleichbar sind. Die Hauptursache für die Schwierigkeit bei der technischen Umsetzung dieser Familie liegt in der Implementierungssicherheit: BLISS wurde durch Seitenkanalangriffe aufgrund von nicht-konstantem Gaußschem Sampling gebrochen; nachfolgende Verfahren haben dieses Problem nicht vollständig gelöst, und das neueste Ergebnis deutet ebenfalls darauf hin, dass der Schutz des Samplingschritts noch schwieriger ist. Bis das Problem gelöst ist, sind solche Verfahren nur theoretisch attraktiv und nicht für den Einsatz geeignet.

Gitterbasierte und hashbasierte Signaturen können sich ergänzen. Gitterbasierte Signaturen können als Komponenten hybrider Schemata dienen. Beispielsweise verwendet der zustandslose Wiederherstellungspfad in SHRINCS derzeit SPHINCS+-Signaturen von mehreren Kilobyte; deren Ersetzung durch Falcon- (oder Falcon-WS-) Signaturen wäre kleiner und schneller zu verifizieren, was den Overhead des seltenen Wiederherstellungspfads erheblich reduziert, ohne den alltäglichen Nutzungspfad zu beeinträchtigen.

Forschungsergebnisse

Die Rangfolge der gitterbasierten Kandidaten ist klar: Hawk zog sich nach dem Angriff des Anthropic-Teams aus dem Wettbewerb zurück; Dilithium hat die geringste Implementierungsschwierigkeit und ist das einzige Verfahren mit einer Forschungsgrundlage für die Schlüsselableitung, aber seine Größe ist nicht freundlich zu Bitcoins On-Chain-Kosten; Falcon kombiniert kompakte Größe, schnelle Verifikation und ausgereifte Sicherheitsannahmen; seine Hauptschwäche – Gleitkommaarithmetik auf der Signierseite – hat bereits eine praktikable technische Lösung. Wenn wir heute ein gitterbasiertes Signaturverfahren für Bitcoin wählen müssten, würden wir Falcon-1024 wählen.

Vorerst stimmt unsere Ansicht mit dem Bericht zu hashbasierten Signaturen überein: Der konservative kurzfristige Weg bleiben hashbasierte Signaturen mit den ausgereiftesten Sicherheitsannahmen und dem geringsten Risiko, geeignet als Übergangslösung. Sobald FN-DSA offiziell finalisiert ist, mit stabilen Spezifikationen, geprüften Codebasen und Hardware-Wallet-Unterstützung, wird Falcon erhebliche Verbesserungen gegenüber rein hashbasierten Signaturen bringen; eine hybride Einführung kann ebenfalls übernommen werden, sodass sich die beiden Signatursysteme gegenseitig ergänzen.