💻 computer science

TALUS: Threshold ML-DSA with One-Round Online Signing via Boundary Clearance and Carry Elimination

Dieses Paper stellt TALUS vor, die erste Threshold-ML-DSA-Konstruktion, die durch die Überwindung der nichtlinearen Rundungsschranke des Schemas mittels einer Boundary Clearance Condition und eines Carry Elimination Frameworks eine einstufige Online-Signierung mit über 99 % Erfolg erreicht und dabei die Standard-Signaturkompatibilität sowie Sicherheit beibehält.

Ursprüngliche Autoren: Leo Kao

Veröffentlicht 2026-07-09

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Leo Kao

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Das Problem mit dem „Digitalen Tresor“

Stellen Sie sich vor, Sie haben einen digitalen Tresor (einen privaten Schlüssel), der so wertvoll ist, dass Sie nicht möchten, dass nur eine einzige Person den Schlüssel hält. Wenn diese Person gehackt wird, ist der Tresor verloren. Deshalb teilen Sie den Schlüssel in Stücke auf und geben sie einer Gruppe von Menschen (einem Komitee). Um den Tresor zu öffnen (ein Dokument zu signieren), müssen eine bestimmte Anzahl von ihnen (sagen wir 3 von 5) zusammenarbeiten.

Dies nennt man Threshold Signing (Schwellenwert-Signatur). Es ist wie ein Banktresor, bei dem drei Schlüssel gleichzeitig gedreht werden müssen.

Lange Zeit war die Umsetzung mit den neuen, „quantensicheren“ digitalen Signaturen (genannt ML-DSA oder FIPS 204) ein Albtraum. Es war langsam, erforderte viele Runden des Hin- und Herschickens von Nachrichten (wie ein Spielchen „Stille Post“, das ewig dauert), oder es benötigte einen vertrauenswürdigen „Super-User“, der ein Stück des Schlüssels hielt, was den Zweck der Risikoverteilung zunichtemachte.

TALUS ist eine neue Methode, die dies löst. Sie ermöglicht es dem Komitee, ein Dokument in einer einzigen Runde zu signieren, was es so schnell macht wie die Signatur durch eine einzelne Person, während gleichzeitig die Sicherheit eines gemeinsamen Schlüssels gewahrt bleibt.

Die zwei Hauptprobleme (und wie TALUS sie überwindet)

Die Arbeit identifiziert zwei spezifische „Engpässe“, die bisherige Versuche scheitern ließen. TALUS nutzt zwei clevere Tricks, um diese zu umgehen.

1. Das Problem der „Rundungsgrenze“ (Die Boundary Clearance Condition)

Die Analogie: Stellen Sie sich vor, Sie versuchen, Blöcke zu stapeln, um eine bestimmte Höhe zu erreichen. Die Regeln besagen: „Wenn Ihr Stapel zu nah am Rand des Tisches steht, müssen Sie prüfen, ob ein schweres Gewicht (ein geheimer Teil des Schlüssels) ihn umwerfen wird.“ In früheren Systemen musste das Komitee stoppen, dieses schwere Gewicht gemeinsam berechnen und prüfen, ob der Stapel sicher ist. Das kostete Zeit und zusätzliche Schritte.

Der TALUS-Trick: Die Autoren erkannten, dass man die Blöcke (den „Nonce“) sorgfältig auswählen kann, um sicherzustellen, dass sie weit weg vom Rand des Tisches sind.

Die „Sicherheitszone“: Wenn die Blöcke in der Mitte des Tisches stehen, kann das schwere Gewicht sie nicht umwerfen, egal wie schwer es ist.
Das Ergebnis: Wenn die Blöcke in dieser „Sicherheitszone“ sind, müssen Sie das schwere Gewicht überhaupt nicht berechnen! Sie können die Blöcke einfach stapeln und weitermachen.
Der Haken: Diese „Sicherheitszone“ tritt nur etwa 31,7 % der Zeit auf (ungefähr bei jedem dritten Versuch).
Die Lösung: TALUS führt die „Prüfung“ offline durch (bevor die eigentliche Signatur stattfindet). Es versucht im Hintergrund, eine Block-Konfiguration für die „Sicherheitszone“ zu finden. Sobald es eine gefunden hat, speichert es diese. Wenn die echte Signaturzeit kommt, greift es einfach auf die vorab genehmigten „Sicherheitszonen-Blöcke“ zu. Dies eliminiert die Notwendigkeit der langsamen, schweren Berechnung während der eigentlichen Signatur.

2. Das „Übertrag“-Problem (Das Carry Elimination Framework)

Die Analogie: Stellen Sie sich vor, das Komitee versucht, ihre Zahlen aufzusummieren, um eine Gesamtsumme zu erhalten. In der normalen Mathematik, wenn man 7 + 8 rechnet, erhält man 15. Die „1“ wird in die nächste Spalte übertragen (der Übertrag). In dieser Welt der digitalen Signaturen ist die Mathematik seltsam: Wenn die Teile zusammengefügt werden, geht der „Übertrag“ (das zusätzliche Bit) verloren oder wird durcheinandergebracht, weil sich die Zahlen im Modulo-Verfahren „umschlagen“.

Der alte Weg: Um den verlorenen „Übertrag“ zu korrigieren, musste das Komitee ein komplexes, mehrstufiges Gespräch führen, um genau zu klären, wohin der Übertrag gelangt ist. Dies erforderte viele Nachrichtenrunden.
Der TALUS-Trick: Die Autoren fanden eine mathematische „Abkürzung“ (eine spezifische Identität unter Verwendung der Zahl 16 und des Modulus). Sie erkannten, dass sie die Gesamtsumme berechnen können, ohne jemals die vollständige, unordentliche Summe zuerst rekonstruieren zu müssen.
Das Ergebnis: Anstatt ein langes Gespräch zur Korrektur des Übertrags zu führen, verwenden sie eine clevere Maskierungstechnik. Jede Person sendt eine leicht „verschlüsselte“ Version ihrer Zahl. Der Koordinator (die Person, die die Signatur zusammenstellt) kann die Gesamtsumme mit einer einfachen Formel entschlüsseln, was den Bedarf an dem komplexen Gespräch zur Korrektur des Übertrags effektiv eliminiert.

Die zwei Versionen von TALUS

Das Paper präsentiert zwei Möglichkeiten, dieses System zu nutzen, abhängig davon, wie sehr Sie Ihrer Hardware vertrauen:

TALUS-TEE (Die Version mit „vertrauenswürdiger Hardware“):
- Funktionsweise: Eine Person (der Koordinator) besitzt einen speziellen, unknackbaren digitalen Tresor (eine Trusted Execution Environment oder TEE). Dieser Tresor hält den Teil des Schlüssels, der das „schwere Gewicht“ darstellt.
- Der Vorteil: Da der Tresor vertrauenswürdig ist, kann der Koordinator die „Sicherheitszonen“-Prüfung und die „Übertrag“-Mathematik ganz allein durchführen. Die anderen Komiteemitglieder senden lediglich ihr Puzzleteil.
- Das Ergebnis: Extrem schnell, funktioniert auch bei einem kleinen Komitee (keine Mehrheit an ehrlichen Teilnehmern nötig) und erfordert nur eine Runde an Nachrichtenübermittlung.
TALUS-MPC (Die „vollständig verteilte“ Version):
- Funktionsweise: Niemand vertraut jemandem. Alle sind gleichgestellt. Sie nutzen den „Übertrag-Eliminierungs“-Trick, um die Mathematik gemeinsam durchzuführen, ohne ihre Geheimnisse preiszugeben.
- Der Haken: Damit die Mathematik ohne einen vertrauenswürdigen Tresor funktioniert, benötigen sie etwas mehr Vorbereitungszeit (Offline-Runden), bevor die Signatur beginnt, um die „verschlüsselten“ Zahlen zu generieren. Außerdem benötigen sie bei größeren Gruppen eine „ehrliche Mehrheit“ (mehr als die Hälfte der Leute müssen „gute Typen“ sein), um Betrug zu verhindern.
- Das Ergebnis: Dennoch bleibt die Nachrichtenübermittlung während der eigentlichen Signatur auf eine Runde beschränkt, aber es ist eine etwas intensivere Vorbereitung erforderlich.

Warum das wichtig ist (Das „Ein-Runden“-Wunder)

In der Welt der digitalen Signaturen ist Zeit Geld. Jedes Mal, wenn das Komitee Nachrichten hin- und herschicken muss, entsteht eine Verzögerung.

Alte Methoden: Könnten 3 bis 29 Nachrichtenrunden benötigen. Wenn das Komitee eine Transaktion über den Ozean hinweg signiert, kann dies Sekunden oder sogar Minuten dauern.
TALUS: Benötigt exakt eine Runde. Das Komitee sendet seinen Teil, und die Signatur ist fertig.
Die Analogie: Stellen Sie sich ein Staffellauf vor. Alte Methoden waren wie ein Staffelstab, den man 10 Mal weiterreicht, bevor man die Ziellinie erreicht. TALUS ist, als ob alle ihre Teilstrecke gleichzeitig laufen und gemeinsam die Linie überqueren.

Die „Anmerkung“ am Anfang (Der Realitätscheck)

Das Paper enthält eine sehr ehrliche Anmerkung ganz am Anfang (datiert auf Juli 2026). Es gibt zu, dass ein Forscher namens Guilhem Niot einige Sicherheitslücken im ursprünglichen Design gefunden hat:

Der „Commitment“-Fehler: In der verteilten Version (MPC) war die Art und Weise, wie sie versuchten, Geheimnisse zu bewahren, leicht undicht. Ein Beobachter konnte die geheimen Schlüssel mathematisch zurückentwickeln.
Der „Check“-Fehler: Sie behaupteten, sie bräuchten keine Prüfung einer bestimmten Sicherheitsbedingung (die $s_2$ -Prüfung), weil ihr „Sicherheitszonen“-Trick funktionierte, aber sie lagen falsch; diese Prüfung ist für die volle Sicherheit dennoch notwendig.

Die Antwort des Papers: Die Autoren verheimlichen dies nicht. Sie geben zu, dass die Angriffe korrekt sind. Sie stellen fest, dass der „Sicherheitszonen“-Trick (BCC) weiterhin funktioniert, sie aber die Art und Weise ändern müssen, wie sie die Geheimnisse sperren (unter Verwendung einer anderen Art von Schloss, einem sogenannten „Hiding Commitment“). Sie arbeiten an einer überarbeiteten Version.

Zusammenfassung

TALUS ist ein Durchbruch bei der effizienten Gestaltung von „quantensicheren“ digitalen Signaturen für Gruppen von Menschen. Es nutzt einen „Sicherheitszonen“-Trick, um langsame Berechnungen zu überspringen, und einen „Übertrag-Eliminierungs“-Trick, um lange Gespräche zu vermeiden. Dies ermöglicht es einer Gruppe, ein Dokument in einem einzigen Schritt zu signieren – so schnell wie eine einzelne Person. Obwohl die Autoren zugeben, dass sie einige Sicherheitslücken in der verteilten Version schließen müssen, ist die Kernidee, das Threshold-Signing schnell und effizient zu machen, ein bedeutender Fortschritt.

Technisches Resümee: TALUS – Schwellenwert-ML-DSA mit One-Round Online-Signierung

1. Problemstellung

Die Implementierung von ML-DSA (FIPS 204, basierend auf CRYSTALS-Dilithium) in einem Schwellenwert-Szenario (Threshold Setting) blieb aufgrund des inhärenten nicht-linearen Rundungsschritts des Schemas ein offenes Problem. Im Gegensatz zu klassischen Schwellenwert-Signaturen (z. B. FROST für Schnorr/ECDSA), die auf additiver Homomorphie beruhen, erfordert ML-DSA eine Prüfung eines sekundären Residuums $r_0 - cs_2$ , um sicherzustellen, dass der Signature-Hint innerhalb der Grenzen bleibt. In einem Schwellenwert-Setting wird die Komponente des geheimen Schlüssels $s_2$ unter den Parteien aufgeteilt. Vorangegangene Ansätze zur Handhabung dieser $r_0$ -Prüfung erforderten:

Teure MPC: Multi-Party-Computation zur Online-Auswertung von $cs_2$ .
Vertrauenswürdige Koordinatoren: Halten $s_2$ in einer Trusted Execution Environment (TEE) oder einer einzelnen vertrauenswürdigen Partei vor.
Rauschüberflutung (Noise Flooding): Verschlechterung der Parameter, um die Prüfung zu maskieren.

Diese Methoden erhöhen entweder die Online-Latenz (mehrere Runden), schränken das Vertrauensmodell ein oder verschlechtern die Sicherheitsparameter. Darüber hinaus existiert ein fundamentales „Lattice Threshold Trilemma“: Kein Gruppenhomomorphismus aus dem Nonce-Raum kann gleichzeitig verborgen (hiding) und bindend (binding) sein, was die Verwendung von Standard-homomorphen Commitment-Schemata, wie sie im diskreten Logarithmus-Setting verwendet werden, ausschließt.

2. Methodik und Kerninnovationen

TALUS (Threshold Agile Lattice Unified Signatures) überwindet diese Barrieren, indem es die $r_0$ -Prüfung von der Online-Signierungsphase entkoppelt und das verteilte Commitment-Problem über einen neuen algebraischen Rahmen löst.

2.1 Boundary Clearance Condition (BCC)

Das Paper identifiziert eine geometrische Eigenschaft des ML-DSA-Commitment-Raums. Der Signierungsprozess beinhaltet ein Residuum $r_0 = \text{LowBits}(Ay)$ . Der geheimnisabhängige Shift $cs_2$ kann nur dann eine Grenzüberschreitung der Rundung verursachen, wenn $r_0$ nahe an den modularen Grenzen ( $\pm \gamma_2$ ) liegt.

Beobachtung: Wenn jede Koeffizient von $r_0$ um mehr als $\beta = \tau\eta$ (wobei $\tau$ das Challenge-Gewicht und $\eta$ die Geheimnis-Grenze ist) von den Grenzen entfernt ist, kann der Shift $cs_2$ keine Grenze überschreiten.
Implikation: Unter dieser Boundary Clearance Condition (BCC) bleibt der Hochordnungsanteil des Commitments ( $w_1$ ) unverändert durch $s_2$ , und der Hint $h$ ist vollständig aus öffentlichen Werten ( $r = Az - ct_1 \cdot 2^d$ und $w_1$ ) berechenbar.
Wahrscheinlichkeit: Die BCC ist mit einer Wahrscheinlichkeit von $p_{BCC} \approx 31,7 \%$ pro Nonce-Versuch erfüllt.
Strategie: TALUS führt eine Offline-Preprocessing-Phase durch, um Nonces zu generieren, die die BCC erfüllen. Dies filtert „schlechte“ Nonces vor der Online-Phase heraus, wodurch die Notwendigkeit entfällt, $cs_2$ während der Signierung zu berechnen oder $r_0$ zu prüfen.

2.2 Carry Elimination Framework (CEF)

Selbst mit BCC müssen die Parteien den Commitment-Hash-Input $w_1 = \text{HighBits}(Ay)$ verteilt berechnen. Da $\text{HighBits}$ kein Gruppenhomomorphismus ist, führt die Summation einzelner Anteile von $w_{1,i}$ zu „Carries“ (Überträgen), die aufgelöst werden müssen, ohne das vollständige Nonce zu rekonstruieren.

Schlüssige Identität: Das Paper nutzt die modulare Identität $\alpha^{-1} \equiv -16 \pmod q$ (wobei $\alpha = 2\gamma_2$ ).
Protokoll:
- TALUS-TEE: Ein vertrauenswürdiger Koordinator hält das aggregierte Nonce und berechnet $w_1$ direkt.
- TALUS-MPC: Die Parteien verwenden ein Carry-Safe Comparison Protocol (CSCP). Sie senden maskierte Dekompositionen ihrer additiven Nonce-Anteile aus. Unter Verwendung von Beaver-Triples und einem Präfixbaum-Vergleichsschaltkreis berechnen die Parteien ein einzelnes Carry-Bit $c$ und ein FIPS-Korrektur-Bit $\delta$ . Dies ermöglicht es dem Koordinator, das exakte $w_1$ zu rekonstruieren, ohne die individuellen Low-Bits des Nonce zu erfahren.
Effizienz: Für $T=2$ degeneriert dies zu einer Distributed Comparison Function (DCF), was die Kommunikation erheblich reduziert. Für $T \ge 3$ sind $O(\log N)$ Offline-Runden erforderlich, die jedoch unabhängig von der Online-Phase bleiben.

3. Protokoll-Instanziierungen

Das Paper präsentiert zwei Deployment-Profile:

TALUS-TEE (Trusted Execution Environment)

Modell: Ein Koordinator hält $s_2$ und $t_0$ innerhalb einer TEE. Signierer halten Anteile von $s_1$ .
Prozess: Die TEE führt das Offline-Preprocessing durch, um ein BCC-konformes Nonce zu finden. Sie überträgt $w_1$ . Signierer antworten mit $z_i = y_i + c \cdot s_{1,i}$ . Die TEE setzt die Signatur zusammen.
Vertrauen: Erfordert einen semi-ehrlichen TEE-Koordinator; Signierer können bösartig sein (identifizierbarer Abbruch/Identifiable Abort).
Einschränkungen: Keine Honest-Majority-Anforderung ( $N \ge T$ ).

TALUS-MPC (Vollständig verteilt)

Modell: Vollständig verteilt; keine Partei hält $s_2$ oder das aggregierte Nonce.
Prozess: Parteien berechnen gemeinsam $w_1$ via CEF während des Offline-Preprocessings. Die Online-Signierung ist identisch mit der TEE (eine Runde).
Vertrauen: Maliziöse Sicherheit mit Identifiable Abort (IA) für $T \ge 2$ .
Einschränkungen: Für $T \ge 3$ ist eine ehrliche Mehrheit erforderlich ( $N \ge 2T - 1$ ), um zu verhindern, dass ein Rushing-Adversary die Low-Bits des Nonce erfährt (Die „Dishonest Majority Barrier“). Für $T=2$ ist keine ehrliche Mehrheit erforderlich.

4. Wichtigste Beiträge

Lattice Threshold Trilemma: Ein Beweis, dass kein Gruppenhomomorphismus aus dem Lattice-Nonce-Raum gleichzeitig verborgen (hiding) und bindend (binding) sein kann. Dies etabliert, dass die Carry-Auflösung eine mathematische Notwendigkeit für FIPS-kompatible Lattice-Schwellenwert-Schemata ist und kein Protokollartefakt.
Boundary Clearance Condition: Ein formaler Beweis, dass die $r_0$ -Prüfung für $\approx 31,7 \%$ der Nonces umgangen werden kann, was die Eliminierung der $s_2$ -Berechnung in der Online-Phase ermöglicht.
Carry Elimination Framework: Ein verteiltes Protokoll zur Berechnung von $\text{HighBits}(Ay)$ ohne Rekonstruktion von $y$ , unter Nutzung der spezifischen modularen Arithmetik-Eigenschaften von ML-DSA.
One-Round Online Signing: Beide Varianten erreichen eine einzige Broadcast-Runde für die Online-Signierung, was die Latenz der Single-Party-Signierung erreicht und vorangegangene FIPS-kompatible Vorschläge (z. B. Mithril), die 2–3 Runden benötigen, übertrifft.
Implementierung: Eine Rust-Referenzimplementierung über alle drei FIPS 204 Sicherheitsstufen (ML-DSA-44, 65, 87).

5. Ergebnisse und Performance

Erfolgsrate: Die erwartete Anzahl der Preprocessing-Versuche pro erfolgreicher Signatur beträgt $\approx 3,15$ (aufgrund der $31,7 \%$ BCC-Passrate).
Latenz (ML-DSA-65, $T=3$ ):
- TALUS-TEE: Die Online-Signierung dauert 0,29 ms; die amortisierte Gesamtdauer (inkl. Offline-Prep) beträgt 1,52 ms.
- TALUS-MPC: Die Online-Signierung dauert 0,68 ms; die amortisierte Gesamtdauer beträgt 4,09 ms.
- Vergleich: TALUS-TEE ist 2,4-mal schneller als Mithril (3,6 ms) in der Online-Latenz. TALUS-MPC ist wettbewerbsfähig mit Mithril, erreicht dies jedoch mit einer einzigen Online-Runde gegenüber Mithrils 3 Runden.
Kommunikation:
- T=2: Offline-Kosten sind $\approx 5$ KB pro Batch (DCF).
- T $\ge$ 3: Offline-Kosten sind $\approx 350$ KB pro Batch (dominiert durch CarryCompare).
- Online: Konstant bei $\approx 3,6$ KB pro Signierer, unabhängig von $T$ und $N$ .
Netzwerklatenz: In verteilten Experimenten (GCP) skaliert die End-to-End-Latenz linear mit der Netzwerk-RTT (z. B. $\approx 350$ ms für US-Europa), was den Vorteil der Single-Round-Lösung bestätigt.

6. Bedeutung und Ansprüche

Das Paper behauptet, dass TALUS das erste Schwellenwert-ML-DSA-Konstrukt ist, das gleichzeitig folgende Eigenschaften vereint:

Volle FIPS 204 Kompatibilität: Signaturen sind durch unveränderte Standard-Verifizierer verifizierbar.
Beliebiger Schwellenwert: Unterstützt $T$ -von- $N$ für beliebiges $1 \le T \le N$ (mit spezifischen Honest-Majority-Beschränkungen für MPC $T \ge 3$ ).
One-Round Online Signing: Entsprt der Latenz einer Single-Party-Signierung, was eine signifikante Verbesserung gegenüber früheren Arbeiten darstellt, die mehrere Online-Runden erfordern.

Die Autoren betonen, dass die „Carry-Kosten“ ein inhärenter algebraischer Preis des Lattice-Settings sind, aber TALUS diese Kosten minimiert, indem es sie vollständig in die Offline-Phase verschiebt. Die Arbeit zeigt, dass FIPS 204-Kompatibilität keine Performance-Einbußen in Schwellenwert-Settings erzwingt.

Hinweis zur Kryptanalyse: Das Paper enthält eine Anmerkung (datiert auf 2026-07-09), die eine Kryptanalyse durch G. Niot berücksichtigt. Die Angriffe bestätigen, dass das Commitment-Schema in TALUS-MPC nicht verborgen (hiding) ist (Rekonstruktion von $x$ aus $Ax$ möglich) und dass die Entfernung der $s_2$ -Prüfung eine statistische Leakage einführt. Die Autoren räumen dies ein, ziehen spezifische Behauptungen bezüglich des Verbergens von $As_{1,i}$ und der Redundanz der $s_2$ -Prüfung für die Geheimhaltung zurück und geben an, dass ein revidiertes Konstrukt unter Verwendung genuin verborgener Commitments in Vorbereitung ist. Sie merken an, dass TALUS-TEE von den Commitment-Angriffen nicht betroffen ist.