💻 computer science

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

Dit artikel introduceert TALUS, de eerste threshold ML-DSA-constructie die een-ronde online ondertekening bereikt met meer dan 99% succes door de niet-lineaire afrondingsbarrière van het schema te overwinnen via een Boundary Clearance Condition en een Carry Elimination Framework, terwijl de standaard signatuurcompatibiliteit en beveiliging behouden blijven.

Oorspronkelijke auteurs: Leo Kao

Gepubliceerd 2026-07-09

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Leo Kao

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Het "Digitale Kluis"-probleem

Stel je voor dat je een digitale kluis hebt (een private key) die zo waardevol is dat je niet wilt dat slechts één persoon de sleutel vasthoudt. Als die persoon gehackt wordt, is de kluis verloren. Daarom splits je de sleutel op in stukjes en geef je ze aan een groep mensen (een comité). Om de kluis te openen (een document ondertekenen), moeten een bepa \text{aant certain aantal} van hen (bijvoorbeeld 3 van de 5) samenwerken.

Dit wordt Threshold Signing genoemd. Het is als een bankkluis die drie sleutels tegelijkertijd moet draaien.

Lama lang was het uitvoeren hiervan met de nieuwe, "quantum-bestendige" digitale handtekeningen (genaamd ML-DSA of FIPS 204) een nachtmerrie. Het was traag, vereiste veel rondes van heen-en-weer sturen van berichten (zoals een spelletje "telefoontje spelen" dat eeuwig duurt), of vereiste een vertrouwde "super-user" die een deel van de sleutel vasthield, wat het doel van het delen van het risico tenietdoet.

TALUS is een nieuwe methode die dit oplost. Het stelt het comité in staat om een document te ondertekenen in één enkele ronde van communicatie, waardoor het net zo snel is als een enkele persoon die ondertekent, terwijl de beveiliging van een gedeelde sleutel behouden blijft.

De Twee Belangrijkste Hindernissen (en hoe TALUS ze overwint)

Het paper identificeert twee specifieke "bottlenecks" die eerdere pogingen deden falen. TALUS gebruikt twee slimme trucs om deze te omzeilen.

1. Het "Afrondingsgrensprobleem" (De Boundary Clearance Condition)

De Analogie: Stel je voor dat je blokken probeert te stapelen om een specifieke hoogte te bereiken. De regels zeggen: "Als je stapel te dicht bij de rand van de tafel staat, moet je controleren of een zwaar gewicht (een geheim deel van de sleutel) de stapel omver zal stoten." In eerdere systemen moest het comité stoppen, samen de zware massa berekenen en controleren of de stapel veilig was. Dit kostte tijd en extra stappen.

De TALUS-truc: De auteurs realiseerden zich dat als je je blokken (de "nonce") zorgvuldig kiest, je ervoor kunt zorgen dat ze ver van de rand van de tafel liggen.

De "Veilige Zone": Als de blokken in het midden van de tafel staan, kan het zware gewicht de blokken niet omver stoten, hoe zwaar het ook is.
Het Resultaat: Als de blokken in deze "Veilige Zone" staan, hoef je het zware gewicht helemaal niet te berekenen! Je kunt ze gewoon stapelen en doorgaan.
De Haken en Oor: Deze "Veilige Zone" komt slechts ongeveer 31,7% van de tijd voor (ongeveer 1 op de 3 pogingen).
De Oplossing: TALUS doet het "controleren" offline (voordat de echte ondertekening plaatsvindt). Het probeert op de achtergrond een "Veilige Zone"-blokopstelling te vinden. Zodra het er een heeft gevonden, slaat het deze op. Wanneer de echte ondertekeningstijd aanbreekt, pakt het simpelweg de vooraf goedgekeurde "Veilige Zone"-blokken. Dit elimineert de noodzaak voor de trage, zware berekening tijdens de eigenlijke ondertekening.

2. Het "Carry"-probleem (Het Carry Elimination Framework)

De Analogie: Stel je voor dat het comité probeert hun getallen op te tellen om tot een totaalbedrag te komen. In gewone wiskunde, als je 7 + 8 optelt, krijg je 15. De "1" wordt doorgegeven naar de volgende kolom. In deze wereld van digitale handtekeningen is de wiskunde vreemd: wanneer de stukjes worden opgeteld, raakt de "carry" (het extra beetje) verloren of verstoord omdat de getallen ronddraaien (wrap around).

De Oude Manier: Om de verloren "carry" te herstellen, moest het comité een complexe, meerstaps conversatie voeren om precies uit te zoeken waar de carry naartoe ging. Dit nam vele rondes van berichten in beslag.
De TALUS-truc: De auteurs vonden een wiskundige "shortcut" (een specifieke identiteit met betrekking tot het getal 16 en de modulus). Ze realiseerden zich dat ze het eindtotaal konden berekenen zonder ooit eerst de volledige, rommelige som te hoeven reconstrueren.
Het Resultaat: In plaats van een lange conversatie om de "carry" te herstellen, gebruiken ze een slimme maskeringstechniek. Iedere persoon stuurt een licht "verstoorde" versie van hun getal. De coördinator (de persoon die de handtekening samenstelt) kan het totaal ontcijferen met een eenvoudige formule, waardoor de noodzaak voor de complexe conversatie om de "carry" te herstellen effectief wordt geëlimineerd.

De Twee Versies van TALUS

Het paper presenteert twee manieren om dit systeem te gebruiken, afhankelijk van hoeveel je je hardware vertrouwt:

TALUS-TEE (De "Vertrouwde Hardware" Versie):
- Hoe het werkt: Eén persoon (de Coördinator) heeft een speciale, onbreekbare digitale kluis (een Trusted Execution Environment of TEE). Deze kluis bevat het "zware gewicht"-deel van de sleutel.
- Het Voordeel: Omdat de kluis vertrouwd is, kan de Coördinator de "Veilige Zone"-controle en de "Carry"-wiskunde allemaal zelf doen. De andere leden van het comité sturen alleen hun deel van de puzzel.
- Het Resultaat: Extreem snel, werkt zelfs als het comité klein is (geen noodzaak voor een meerderheid van eerlijke mensen) en vereist slechts één ronde van berichten.
TALUS-MPC (De "Volledig Gedistribueerde" Versie):
- Hoe het werkt: Niemand vertrouwt iemand anders. Iedereen is gelijk. Ze gebruiken de "Carry Elimination"-truc om samen de wiskunde te doen zonder hun geheimen te onthullen.
- De Haken en Oor: Om de wiskunde te laten werken zonder een vertrouwde kluis, hebben ze wat meer voorbereidingstijd nodig voordat de ondertekening begint (offline rondes) om de "verstoorde" getallen te genereren. Ook voor grotere groepen hebben ze een "eerlijke meerderheid" nodig (meer dan de helft van de mensen moet de goede kant op staan) om te voorkomen dat er gesjoemeld wordt.
- Het Resultaat: Vereist nog steeds slechts één ronde van berichten tijdens de eigenlijke ondertekening, maar vereist wat meer voorbereiding vooraf.

Waarom Dit Er Toe Doet (Het "One-Round" Wonder)

In de wereld van digitale handtekeningen is tijd geld. Elke keer dat het comité berichten heen en weer moet sturen, zorgt dat voor vertraging.

Oude methoden: Kunnen 3 tot 29 rondes van berichten vereisen. Als je een transactie over de oceaan tekent, kan dit seconden of zelfs minuten duren.
TALUS: Vereist exact één ronde. Het comité stuurt hun deel, en de handtekening is klaar.
De Analogie: Stel je een estafette voor. Oude methoden waren als het 10 keer doorgeven van de stok voordat de finishlijn werd bereikt. TALUS is alsoren dat iedereen zijn deel gelijktijdig rent en samen de finishlijn passeert.

De "Noot" Bovenaan (De Realiteitscheck)

Het paper bevat een zeer eerlijke noot aan het begin (gedateerd juli 2026). Het geeft toe dat een onderzoeker genaamd Guilhem Niot enkele beveiligingsgebreken vond in het oorspronkelijke ontwerp:

De "Commitment" Fout: In de gedistribueerde versie (MPC) was de manier waarop ze beloofden geheimen te bewaren, een beetje lek. Een waarnemer kon de geheime sleutels wiskundig terugberekenen.
De "Check" Fout: Ze beweerden dat ze een specifieke beveiligingsconditie (de $s_2$ check) niet nodig hadden vanwege hun "Veilige Zone"-truc, maar ze zaten ernaast; die check is nog steeds nodig voor volledige beveiliging.

De Reactie van het Paper: Ze verbergen dit niet. Ze geven toe dat de aanvallen correct zijn. Ze stellen dat de "Veilige Zone"-truc (BCC) nog steeds werkt, maar dat ze de manier moeten aanpassen waarop ze de geheimen vergrendelen (door een ander type slot te gebruiken, een "hiding commitment"). Ze werken aan een herziene versie.

Samenvatting

TALUS is een doorbraak in het werkbaar maken van "quantum-bestendige" digitale handtekeningen voor groepen mensen. Het gebruikt een "Veilige Zone"-truc om trage berekeningen over te slaan en een "Carry Elimination"-truc om lange gesprekken te vermijden. Dit stelt een groep in staat om een document te ondertekenen in één stap, net zo snel als een enkele persoon. Hoewel de auteurs toegeven dat ze een paar beveiligingslekken in de gedistribueerde versie moeten patchen, is het kernidee om threshold signing snel en efficiënt te maken een grote stap vooruit.

Technische Samenvatting: TALUS – Threshold ML-DSA met One-Round Online Signing

1. Probleemstelling

Het implementeren van ML-DSA (FIPS 204, gebaseerd op CRYSTALS-Dilithium) in een threshold-setting is een openstaand probleem gebleven vanwege de inherente niet-lineaire afrondingsstap van het schema. In tegenstelling tot klassieke threshold-signaturen (bijv. FROST voor Schnorr/ECDSA), die vertrouwen op additieve homomorfie, vereist ML-DSA een controle op een secundaire residu $r_0 - cs_2$ om te waarborgen dat de signature hint binnen de grenzen blijft. In een threshold-setting wordt het geheime sleutelcomponent $s_2$ gedeeld onder partijen. Eerdere benaderingen om deze $r_0$ -controle aan te pakken, vereisten:

Dure MPC: Multi-party computation om $cs_2$ online te evalueren.
Vertrouwde Coördinatoren: Het vasthouden van $s_2$ in een Trusted Execution Environment (TEE) of bij een enkele vertrouwde partij.

Noise Flooding: Het degraderen van parameters om de controle te maskeren.

Deze methoden verhogen ofwel de online latentie (meerdere rondes), beperken het trust-model, of degraderen de beveiligingsparameters. Bovendien bestaat er een fundamentele "Lattice Threshold Trilemma": geen groepshomomorfisme vanuit de nonce-ruimte kan tegelijkertijd verborgen (hiding) en bindend (binding) zijn, wat de standaard homomorfe commitment-schema's die gebruikt worden in discrete-log settings uitsluit.

2. Methodologie en Kerninnovaties

TALUS (Threshold Agile Lattice Unified Signatures) overwint deze barrières door de $r_0$ -controle los te koppelen van de online signer-fase en het gedistribueerde commitment-probleem op te lossen via een nieuw algebraïsch framework.

2.1 Boundary Clearance Condition (BCC)

Het paper identificeert een geometrische eigenschap van de ML-DSA commitment-ruimte. Het signer-proces omvat een residu $r_0 = \text{LowBits}(Ay)$ . De geheim-afhankelijke verschuiving $cs_2$ kan alleen een afrondingsgrens overschrijden als $r_0$ dicht bij de modulaire grenzen ( $\pm \gamma_2$ ) ligt.

Observatie: Als elke coëfficiënt van $r_0$ verder van de grenzen verwijderd is dan $\beta = \tau\eta$ (waarbij $\tau$ het challenge-gewicht is en $\eta$ de geheim-bound), dan kan de verschuiving $cs_2$ geen enkele grens overschrijden.
Implicatie: Onder deze Boundary Clearance Condition (BCC) blijft het hoog-orde deel van de commitment ( $w_1$ ) onveranderd door $s_2$ , en wordt de hint $h$ volledig berekenbaar vanuit publieke waarden ( $r = Az - ct_1 \cdot 2^d$ en $w_1$ ).
Waarschijnlijkheid: BCC is waar met een waarschijnlijkheid $p_{BCC} \approx 31,7\%$ per nonce-poging.
Strategie: TALUS voert offline preprocessing uit om nonces te genereren die voldoen aan de BCC. Dit filtert "slechte" nonces uit vóór de online fase, waardoor de noodzaak om $cs_2$ te berekenen of $r_0$ te controleren tijdens het signeren wordt geëlimineerd.

2.2 Carry Elimination Framework (CEF)

Zelfs met BCC moeten partijen de commitment hash input $w_1 = \text{HighBits}(Ay)$ gedistribueerd berekenen. Omdat $\text{HighBits}$ geen groepshomomorfisme is, introduceert het sommeren van individuele shares van $w_{1,i}$ "carries" (overdrachten) die opgelost moeten worden zonder de volledige nonce te reconstrueren.

Kernidentiteit: Het paper maakt gebruik van de modulaire identiteit $\alpha^{-1} \equiv -16 \pmod q$ (waarbij $\alpha = 2\gamma_2$ ).
Protocol:
- TALUS-TEE: Een vertrouwde coördinator houdt de geaggregeerde nonce vast en berekent $w_1$ direct.
- TALUS-MPC: Partijen gebruiken een Carry-Safe Comparison Protocol (CSCP). Zij broadcast gemaskeerde decomposities van hun additieve nonce-stukken. Gebruikmakend van Beaver triples en een prefix-tree comparison circuit, berekenen de partijen een enkele carry bit $c$ en een FIPS correctie bit $\delta$ . Dit stelt de coördinator in staat de exacte $w_1$ te reconstrueren zonder de individuele low-bits van de nonce te leren.
Efficiëntie: Voor $T=2$ degradeert dit naar een Distributed Comparison Function (DCF), wat de communicatie aanzienlijk vermindert. Voor $T \ge 3$ vereist het $O(\log N)$ offline rondes, maar blijft het onafhankelijk van de online fase.

3. Protocol Instantiaties

Het paper presenteert twee deployment profielen:

TALUS-TEE (Trusted Execution Environment)

Model: Een coördinator houdt $s_2$ en $t_0$ vast in een TEE. Signers houden shares van $s_1$ vast.
Proces: De TEE voert offline preprocessing uit om een BCC-conforme nonce te vinden. Het broadcast $w_1$ . Signers reageren met $z_i = y_i + c \cdot s_{1,i}$ . De TEE assembleert de signature.
Vertrouwen: Vereist een semi-honest TEE coördinator; signers kunnen kwaadwillend zijn (identifiable abort).
Constraints: Geen honest-majority requirement ( $N \ge T$ ).

TALUS-MPC (Volledig Gedistribueerd)

Model: Volledig gedistribueerd; geen partij houdt $s_2$ of de geaggregeerde nonce vast.
Proces: Partijen berekenen gezamenlijk $w_1$ via de CEF tijdens de offline preprocessing. De online signing is identiek aan de TEE (één ronde).
Vertrouwen: Malicious security met Identifiable Abort (IA) voor $T \ge 2$ .
Constraints: Voor $T \ge 3$ is een honest majority vereist ( $N \ge 2T - 1$ ) om te voorkomen dat een rushing adversary de low-bits van de nonce leert (De "Dishonest Majority Barrier"). Voor $T=2$ is geen honest majority vereist.

4. Belangrijkste Bijdragen

Lattice Threshold Trilemma: Een bewijs dat geen enkel groepshomomorfisme vanuit de lattice nonce-ruimte tegelijkertijd verborgen (hiding) en bindend (binding) kan zijn. Dit vestigt dat carry-resolutie een wiskundige noodzaak is voor FIPS-compatibele lattice threshold-schema's, en geen protocol-artefact.
Boundary Clearance Condition: Een formeel bewijs dat de $r_0$ -controle kan worden omzeild voor $\approx 31,7\%$ van de nonces, wat de eliminatie van de $s_2$ berekening in de online fase mogelijk maakt.
Carry Elimination Framework: Een gedistribueerd protocol om $\text{HighBits}(Ay)$ te berekenen zonder de volledige $y$ te reconstrueren, gebruikmakend van de specifieke modulaire rekenkundige eigenschappen van ML-DSA.
One-Round Online Signing: Beide varianten bereiken een enkele broadcast ronde voor online signing, wat overeenkomt met de latentie van single-party signing en de eerdere FIPS-compatibele voorstellen (bijv. Mithril, Quorus) die 2–3 rondes vereisen overtreft.
Implementatie: Een Rust reference implementatie over alle drie de FIPS 204 security levels (ML-DSA-44, 65, 87).

5. Resultaten en Prestaties

Succespercentage: Het verwachte aantal preprocessing pogingen per succesvolle signature is $\approx 3,15$ (vanwege de $31,7\%$ BCC pass rate).
Latentie (ML-DSA-65, $T=3$ ):
- TALUS-TEE: Online signing duurt 0,29 ms; geamortiseerde totaal (inclusief offline prep) is 1,52 ms.
- TALUS-MPC: Online signing duurt 0,68 ms; geamortiseerde totaal is 4,09 ms.
- Vergelijking: TALUS-TEE is 2,4x sneller dan Mithril (3,6 ms) in online latentie. TALUS-MPC is competitief met Mithril maar bereikt dit met één online ronde versus Mithril's 3 rondes.
Communicatie:
- T=2: Offline kosten zijn $\approx 5$ KB per batch (DCF).
- T $\ge$ 3: Offline kosten zijn $\approx 350$ KB per batch (gedomineerd door CarryCompare).
- Online: Constant op $\approx 3,6$ KB per signer, onafhankelijk van $T$ en $N$ .
Netwerk Latentie: In gedistribueerde experimenten (GCP) schaalt de end-to-end latentie lineair met de netwerk RTT (bijv. $\approx 350$ ms voor US-Europa), wat het voordeel van de enkele ronde bevestigt.

6. Betekenis en Claims

Het paper claimt dat TALUS de eerste threshold ML-DSA constructie is die simultaan bereikt:

Volledige FIPS 204 Compatibiliteit: Signaturen zijn verifieerbaar door ongewijzigde standaard verifieerders.
Arbitraire Threshold: Ondersteunt $T$ -van- $N$ voor elke $1 \le T \le N$ (met specifieke honest-majority restricties voor MPC $T \ge 3$ ).
One-Round Online Signing: Komt overeen met de latentie van single-party signing, een significante verbetering ten opzichte van eerdere werken die meerdere online rondes vereisen.

De auteurs benadrukken dat de "carry cost" een inherente algebraïsche prijs is van de lattice setting, maar dat TALUS deze kosten minimaliseert door deze volledig naar de offline fase te verplaatsen. Het werk demonstreert dat FIPS 204 compatibiliteit geen prestatie-penalty noodzakelijk maakt in threshold-settings.

Opmerking over Cryptanalyse: Het paper bevat een notitie (gedateerd 2026-07-09) die een cryptanalyse door G. Niot erkent. De aanvallen bevestigen dat het commitment-schema in TALUS-MPC niet verborgen (hiding) is (het herstellen van $x$ uit $Ax$) en dat het verwijderen van de $s_2$ controle statistische lekkage introduceert. De auteurs geven deze punten toe, trekken specifieke claims terug met betrekking tot het verborgen (hiding) van $As_{1,i}$ en de redundantie van de $s_2$ controle voor geheimhouding, en stellen dat een herziene constructie met echt verborgen (hiding) commitments in voorbereiding is. Zij merken op dat TALUS-TEE niet wordt beïnvloed door de commitment-aanvallen.