FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

Dieses Papier stellt das erste FIPS-204-kompatible Schwellenwert-ML-DSA-Schema vor, das durch die Verwendung von Shamir-Nonce-DKG und paarweise ausgleichenden PRF-Masken die Privatsphäre der Nonce-Teile ohne zusätzliche kryptografische Annahmen gewährleistet und dabei standardkonforme Signaturen für beliebige Schwellenwerte erzeugt.

Das Wesentliche

Hier ist eine einfache Erklärung der Forschung von Leo Kao, die sich mit einer neuen Art von digitaler Unterschrift für die Zukunft befasst.

Das große Problem: Der "Schlüssel" ist zu schwer zu tragen

Stellen Sie sich vor, Sie haben einen Super-Schlüssel, der Ihr ganzes digitales Leben schützt (Bankkonten, Identität, geheime Daten). In der heutigen Welt wird dieser Schlüssel bald von Quantencomputern geknackt werden können. Die Wissenschaftler haben daher einen neuen, unknackbaren Schlüssel entwickelt (genannt ML-DSA oder FIPS 204).

Aber hier liegt das Problem: Wenn nur eine Person diesen Schlüssel besitzt, ist das riskant. Wenn sie stirbt, den Schlüssel verliert oder gehackt wird, ist alles weg.
Die Lösung? Schlüssel teilen. Statt einer Person besitzen viele Personen (z. B. 5) jeweils ein kleines Stück des Schlüssels. Um etwas zu unterschreiben, müssen mindestens 3 dieser Personen zusammenarbeiten. Das nennt man eine Schwellenwert-Unterschrift (Threshold Signature).

Das neue Hindernis: Warum das bei der neuen Technik so schwer ist

Bei alten digitalen Signaturen war das Teilen des Schlüssels wie ein gut geöltes Spiel. Bei der neuen, quantensicheren Technik (ML-DSA) gibt es jedoch einen Haken:
Um eine Unterschrift zu erstellen, muss man eine völlig zufällige Zahl (einen "Nonce") wählen. Wenn diese Zahl nicht perfekt zufällig ist, können Hacker den Schlüssel stehlen.

Bisherige Versuche, diesen Schlüssel zu teilen, hatten zwei große Nachteile:

1. Sie waren zu langsam: Es dauerte ewig, bis alle Parteien sich abstimmen konnten.
2. Sie waren zu groß: Die Unterschriften wurden so riesig (wie ein ganzer Brief statt einer Postkarte), dass alte Computer sie gar nicht lesen konnten. Das ist ein Problem, weil alle Banken und Behörden auf das alte Format angewiesen sind.

Die Lösung: Ein neues Rezept mit "Shamir" und "Tee"

Leo Kaos Papier präsentiert die erste Lösung, die alles gleichzeitig kann: Sie ist schnell, die Unterschriften sind klein (genau wie beim Standard) und sie funktioniert mit beliebigen Gruppen (z. B. 3 von 5, 16 von 32, etc.).

Hier sind die zwei genialen Tricks, die er benutzt hat:

1. Der "Schamir-Nonce-DKG" (Das Puzzle-Prinzip)

Stellen Sie sich vor, Sie müssen eine geheime Zahl (den "Nonce") finden.

• Die alte, schlechte Methode: Jeder Teilnehmer würfelt eine Zahl und schreit sie laut heraus. Ein Hacker könnte dann die Würfel der anderen hören und die geheime Zahl erraten.
• Die neue, clevere Methode (Shamir): Jeder Teilnehmer bekommt ein kleines Stück eines riesigen Puzzles. Niemand kennt die ganze Zahl. Aber wenn man die Puzzleteile von 3 Personen zusammenlegt, ergibt sich die perfekte, zufällige Zahl.
• Der Clou: Selbst wenn ein Hacker 2 der 5 Personen kontrolliert, kann er das Puzzle nicht lösen. Er sieht nur 2 Teile, aber das Puzzle hat 3 Teile. Es ist wie ein Schloss, bei dem man 2 Schlüssel hat, aber 3 braucht, um es zu öffnen. Die Sicherheit ist hier so stark, dass sie nicht einmal auf komplizierter Mathematik basiert, sondern rein auf Wahrscheinlichkeit (wie ein Lotterieschein, den man nicht erraten kann).

2. Die "Paarweise-Aufhebungs-Masken" (Die Tarnkappe)

Manchmal müssen die Teilnehmer Informationen austauschen, ohne dass der Hacker mitliest.

• Die Analogie: Stellen Sie sich vor, zwei Freunde wollen ein Geheimnis austauschen, aber ein Spion lauscht mit.
  • Freund A sagt: "Ich habe +5."
  • Freund B sagt: "Ich habe -5."
  • Zusammen ist das Ergebnis 0. Der Spion hört nur die lauten Zahlen, aber da sie sich aufheben, erfährt er nichts über das eigentliche Geheimnis.
• In diesem Papier nutzen die Teilnehmer solche "Masken", um sicherzustellen, dass niemand aus den Zwischenstufen der Berechnung den Schlüssel stehlen kann.

Die drei "Fahrpläne" für die Praxis

Der Autor bietet drei verschiedene Wege an, wie man dieses System in der echten Welt nutzen kann, je nachdem, wie sehr man den anderen vertraut:

1. Der "Sicherer-Box"-Modus (P1):

   • Wie es funktioniert: Es gibt einen speziellen, vertrauenswürdigen Computer (einen "TEE"), der wie ein Panzerschrank funktioniert. Er macht die rechenintensive Arbeit.
   • Vorteil: Extrem schnell (in Millisekunden).
   • Nachteil: Man muss dem Hersteller des Panzerschrankes vertrauen.

2. Der "Alles-Vertrauenslos"-Modus (P2):

   • Wie es funktioniert: Keine Panzerschrank. Alle Parteien rechnen gemeinsam (MPC), als würden sie ein riesiges Rätsel lösen, ohne dass jemand die Lösung sieht.
   • Vorteil: Man muss niemandem vertrauen, nicht einmal dem Computerhersteller.
   • Nachteil: Etwas langsamer, aber immer noch sehr schnell für moderne Standards.

3. Der "Mensch-in-der-Schleife"-Modus (P3+):

   • Wie es funktioniert: Perfekt für Situationen, wo Menschen zustimmen müssen (z. B. ein CEO und ein CFO müssen beide "Ja" sagen). Die Teilnehmer können ihre Teile vorbereiten, wenn sie Zeit haben, und müssen nicht alle gleichzeitig am Computer sitzen.
   • Vorteil: Sehr flexibel und benutzerfreundlich.

Warum ist das wichtig?

• Es passt in die Welt: Die Unterschriften sehen exakt so aus wie die alten, standardisierten. Banken und Regierungen müssen ihre Software nicht ändern, um sie zu akzeptieren.
• Es ist sicher: Selbst wenn ein Hacker viele Teilnehmer kontrolliert, kann er nicht fälschen.
• Es ist schnell: In Tests brauchte das System nur etwa 20 Millisekunden für eine Unterschrift – schneller als ein menschlicher Augenblinzeln.

Zusammenfassung in einem Satz

Leo Kao hat einen Weg gefunden, wie man einen quantensicheren digitalen Schlüssel sicher auf viele Personen verteilt, ohne dass die Unterschriften riesig werden oder die Geschwindigkeit leidet – ähnlich wie man ein Geheimnis in viele kleine, unknackbare Puzzleteile zerlegt, die nur zusammen ein perfektes Bild ergeben.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Threshold ML-DSA via Shamir Nonce DKG" von Leo Kao (Codebat Technologies Inc.) auf Deutsch.

1. Problemstellung und Motivation

Mit der Veröffentlichung von FIPS 204 durch das NIST wurde ML-DSA (Module-Lattice-Based Digital Signature Algorithm) als primärer Post-Quantum-Signaturalgorithmus standardisiert. Während effiziente Schwellenwert-Signaturverfahren (Threshold Signatures) für klassische Algorithmen wie ECDSA und Schnorr bereits weit verbreitet sind, stellt die Implementierung für ML-DSA erhebliche Herausforderungen dar.

Das Kernproblem liegt im Fiat-Shamir-with-Aborts-Paradigma von ML-DSA:

• Eine Signatur ist nur gültig, wenn der Antwortvektor $z = y + c \cdot s_1$ eine bestimmte Normgrenze ($\|z\|_\infty < \gamma_1 - \beta$) einhält.
• In einem Schwellenwert-Setting müssen mehrere Parteien ihre Beiträge zu $z$ kombinieren.
• Bestehende Ansätze scheitern an einem der folgenden Punkte:
  1. Eingeschränkte Schwellenwerte: Verfahren mit kurzen Rekonstruktionskoeffizienten (Short-coefficient LSSS) sind auf sehr kleine Schwellenwerte ($T \le 6$) beschränkt, da die Lagrange-Koeffizienten für größere $T$ den Modul $q$ übersteigen.
  2. Inkompatibilität: Ansätze mit „Noise Flooding" (Rauschen) ermöglichen beliebige Schwellenwerte, erzeugen aber Signaturen von ca. 17 KB, was die FIPS 204-Kompatibilität (Standardgröße ca. 3,3 KB) bricht.
  3. Sicherheitslücken: Bisherige Lösungen erforderten oft die Annahme von mindestens zwei ehrlichen Parteien ($|S| \ge T+1$) oder boten keine statistische Privatsphäre für die Nonce-Shares ohne rechnerische Annahmen.

Es bestand eine signifikante Lücke für Anwendungen, die Schwellenwerte im Bereich $T \in [9, 32]$ benötigen (z. B. 16-von-32), während sie gleichzeitig standardkonforme Signaturen und hohe Erfolgsraten garantieren müssen.

2. Methodik und Kerninnovationen

Das Paper stellt eine neue Schwellenwert-Signatur für ML-DSA vor, die zwei Haupttechniken kombiniert, um die oben genannten Probleme zu lösen:

A. Shamir Nonce DKG (Distributed Key Generation)

Dies ist die primäre Innovation. Anstatt den Signatur-Nonce $y$ einfach zu addieren oder zu maskieren, generieren die Parteien den Nonce gemeinsam über ein Shamir-Verfahren.

• Struktur: Der Nonce $y$ wird als Grad-$(T-1)$ Shamir-Polynom erzeugt, das strukturell dem langfristigen Geheimnis $s_1$ entspricht.
• Privatsphäre: Jeder ehrlichen Partei liegt ein Share $y_h$ vor. Ein Angreifer sieht nur $T-1$ Auswertungen des Polynoms einer ehrlichen Partei. Da der höchste Koeffizient des Polynoms gleichmäßig über $\mathbb{Z}_q$ gewählt wird, bleibt ein Freiheitsgrad erhalten.
• Ergebnis: Dies bietet eine bedingte Min-Entropie für den Nonce-Share, die das 5-fache der Entropie des Geheimschlüssels übersteigt (für $|S| \le 17$). Dies ist eine statistische Garantie ohne rechnerische Annahmen.
• Vorteil: In koordinierten Profilen (P1, P3+) reicht eine ehrliche Partei ($|S| = T$) aus, um die Privatsphäre zu gewährleisten (keine „Two-Honest"-Annahme nötig).

B. Pairwise-Canceling Masks (Paarweise auslöschende Masken)

Um die Integrität der Commitments ($W_i$) und der $r_0$-Check-Anteile ($V_i$) zu wahren, ohne diese preiszugeben, werden Masken verwendet, die sich in der Summe aufheben.

• Herausforderung: Im Gegensatz zu ECDSA muss hier die $r_0$-Prüfung (die $c \cdot s_2$ enthält) sicher durchgeführt werden, ohne dass $s_2$ rekonstruiert wird (da $c$ oft invertierbar ist und $s_2$ sonst offenbart würde).
• Lösung: Die Masken werden über paarweise geteilte Seeds (via PRF) generiert. In der Summe heben sie sich auf, sodass der Kombinator (oder TEE/MPC) nur den korrekten aggregierten Wert erhält, nicht aber die individuellen Beiträge.

C. Irwin-Hall-Verteilung und Sicherheitsanalyse

Die aggregierte Nonce-Verteilung folgt einer Irwin-Hall-Verteilung (Summe von $|S|$ gleichverteilten Variablen) statt einer reinen Gleichverteilung.

• Sicherheitsverlust: Dies führt zu einem kleinen Sicherheitsverlust in der EUF-CMA-Sicherheit.
• Analyse: Das Paper führt eine direkte Shift-Invarianz-Analyse durch (im Gegensatz zu konservativen Raccoon-artigen Schranken).
• Ergebnis: Der Sicherheitsverlust pro Sitzung ist extrem gering ($< 0,007$ Bits für $|S| \le 17$ und $< 0,013$ Bits für $|S| \le 33$). Dies eliminiert das Skalierbarkeitsproblem früherer Arbeiten, bei denen der Verlust mit der Anzahl der Sitzungen schnell die Sicherheit aufhob.

3. Drei Bereitstellungsprofile (Deployment Profiles)

Das Paper definiert drei Profile mit unterschiedlichen Vertrauensannahmen, alle mit vollständigen UC-Beweisen (Universal Composability):

1. Profil P1 (TEE-gestützt):

   • Ein Koordinator in einem Trusted Execution Environment (TEE/HSM) führt den $r_0$-Check und die Hint-Generierung durch.
   • Vorteile: Optimaler Durchsatz (3 Online-Runden), niedrige Latenz (~5,8 ms für 3-von-5).
   • Annahme: Integrität des TEE.

2. Profil P2 (Vollständig verteilt / MPC):

   • Keine Hardware-Vertrauensannahme. Der $r_0$-Check wird mittels Secure Multi-Party Computation (MPC) mit SPDZ und edaBits berechnet.
   • Vorteile: Bietet Unforgeability auch bei einer Mehrheit böswilliger Parteien (Dishonest-Majority).
   • Nachteil: Höhere Latenz (~21,5 ms für 3-von-5) und 5 Online-Runden.

3. Profil P3+ (Semi-asynchrones 2PC):

   • Zwei Computation Parties (CPs) führen den Check via 2PC durch. Signatoren können Nonces offline vorbereiten und antworten innerhalb eines Zeitfensters (z. B. 5 Minuten).
   • Vorteile: Ideal für „Human-in-the-Loop"-Szenarien. Nur 2 logische Runden, sehr niedrige Latenz (~22 ms).
   • Annahme: Mindestens eine der beiden CPs ist ehrlich (1-of-2).

4. Ergebnisse und Benchmarks

Die Implementierung in Rust wurde umfassend getestet:

• Kompatibilität: Die generierten Signaturen sind byte-identisch mit Standard-ML-DSA-Signaturen (3,3 KB für ML-DSA-65) und können von unveränderten FIPS 204-Verifizierern geprüft werden.
• Performance:
  • P1 (TEE): 5,8 ms (3-von-5).
  • P2 (MPC): 21,5 ms (3-von-5).
  • P3+ (2PC): 22,1 ms (3-von-5).
  • Skalierbarkeit: Das System skaliert bis zu 32-von-45 Schwellenwerten mit Latenzen unter 100 ms (für P1 und P3+).
• Erfolgsrate: Die Erfolgsrate liegt bei ca. 21–45% pro Versuch. Dies ist vergleichbar mit oder sogar besser als die einzelne Signatur-Basislinie (~20–25%), da die Irwin-Hall-Verteilung mehr Nonces in den akzeptierten Bereich bringt.
• Skalierbarkeit: Im Gegensatz zu früheren Arbeiten, die bei höheren Schwellenwerten versagten oder massive Overheads hatten, bleibt der Sicherheitsverlust auch bei großen $T$ vernachlässigbar.

5. Bedeutung und Beitrag

Dieses Paper schließt eine kritische Lücke in der Post-Quantum-Kryptographie:

1. Erste FIPS 204-kompatible Lösung: Es ist das erste Schwellenwert-Schema für ML-DSA, das beliebige Schwellenwerte ($T$) mit standardkonformen Signaturen unterstützt.
2. Statistische Privatsphäre: Es erreicht eine starke Privatsphäre für Nonce-Shares ohne rechnerische Annahmen (nur auf Min-Entropie basierend), was eine neue Sicherheitsstufe darstellt.
3. Praktische Einsetzbarkeit: Durch die Bereitstellung von drei Profilen (TEE, MPC, Semi-Async) deckt es verschiedene Anwendungsfälle ab, von hochperformanten HSM-Umgebungen bis hin zu dezentralen, hardware-unabhängigen Systemen.
4. Sicherheitsbeweise: Die Arbeit liefert vollständige UC-Beweise und eine präzise Analyse der Sicherheitsverluste durch die Irwin-Hall-Verteilung, die zeigt, dass der Verlust für praktische Szenarien vernachlässigbar ist.

Zusammenfassend ermöglicht diese Arbeit die sichere und effiziente Verteilung von ML-DSA-Signaturrechten in kritischen Infrastrukturen (wie Krypto-Custody, PKI und staatlichen Anwendungen), ohne Kompromisse bei der Standardkonformität oder der Sicherheit einzugehen.