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

Each language version is independently generated for its own context, not a direct translation.

Deelgeheimen van de Toekomst: Hoe we digitaal veilig blijven in het tijdperk van quantumcomputers

Stel je voor dat je een supergeheime sleutel hebt die je gebruikt om je digitale identiteit te beschermen. In de toekomst zullen krachtige "quantumcomputers" bestaan die deze oude sleutels kunnen kraken. De overheid (NIST) heeft daarom een nieuwe, onbreekbare sleutel ontworpen: ML-DSA.

Maar hier is het probleem: in de echte wereld wil je niet dat één persoon deze geheime sleutel vasthoudt. Als die persoon wordt opgepakt, verliest iedereen zijn toegang. Als die persoon zijn sleutel kwijtraakt, is alles weg. De oplossing? Deelgeheimen (Threshold Signatures). Je verdeelt de sleutel over een groep mensen (bijvoorbeeld 5 mensen), en je hebt er minimaal 3 nodig om iets te ondertekenen.

Het probleem is echter: hoe doe je dit veilig met deze nieuwe, complexe wiskundige sleutels zonder dat de beveiliging instort? Dat is wat deze paper oplost.

Hier is de uitleg in simpele taal, met wat creatieve vergelijkingen.

1. Het Probleem: De "Grote Getallen" Valstrik

Bij de nieuwe digitale sleutels (ML-DSA) moet je een heel groot, willekeurig getal kiezen (een "nonce") elke keer dat je tekent.

Hoe het normaal werkt: Eén persoon kiest een getal, tekent, en klaar.
Hoe het in een groep werkt: Als 3 mensen samenwerken, moeten ze elk een stukje van dat getal kiezen en die optellen.

Het probleem is dat als je deze stukjes simpel optelt, de wiskunde "uit elkaar valt". De getallen worden te groot, de beveiliging breekt, en je moet je hele systeem aanpassen (wat duur en onpraktisch is). Eerdere oplossingen maakten de digitale handtekening zo groot als een heel boek (17 KB in plaats van 3 KB), waardoor oude systemen ze niet meer konden lezen.

2. De Oplossing: De "Shamir Nonce DKG" (Het Muzikale Orkest)

De auteurs van deze paper hebben een slimme truc bedacht, gebaseerd op een oude wiskundige methode van Shamir.

De Analogie: Het Muzikale Orkest
Stel je voor dat je een symfonie wilt componeren (de geheime sleutel).

De oude manier: Iedereen speelt een noot, en de dirigent telt ze op. Soms klinkt het als een oorverdovend lawaai (te grote getallen).
De nieuwe manier (Shamir): Iedereen krijgt een stuk van een liedje (een wiskundige formule). Ze spelen niet alleen een noot, maar een heel stuk van de melodie.
- Als je 2 mensen hebt, hoor je maar een fluitje.
- Maar zodra je 3 mensen hebt (de drempel), kunnen ze samen het volledige liedje reconstrueren.

Het geniale hieraan is dat elke persoon zijn eigen stukje van het liedje (het getal) geheim houdt. Zelfs als de slechte jongens 2 van de 3 mensen hebben gevangen, kunnen ze het liedje niet horen. Ze horen alleen ruis. Dit betekent dat de geheime "nonce" (het getal) statistisch onkraakbaar blijft, zonder dat je hoeft te vertrouwen op rekenkracht.

3. De Tweede Truc: De "Verdwijnende Maskers"

Er is nog een probleem: tijdens het proces moeten de mensen onderling communiceren. Als ze hun stukjes openbaar maken, kunnen hackers zien wat ze doen.

De Analogie: De Geheime Brief
Stel je voor dat je een brief wilt versturen, maar je wilt niet dat de postbode (of de hackers) de inhoud ziet.

Je schrijft je boodschap op.
Je plakt er een verdwijnend masker overheen.
Je vriend doet hetzelfde.
Als jullie de maskers bij elkaar optellen, verdwijnen ze. De maskers zijn zo ontworpen dat ze elkaar precies opheffen (plus en min).
Het resultaat? De postbode ziet alleen de gecombineerde boodschap, maar ziet nooit wat er onder het masker zat.

Dit zorgt ervoor dat de groep veilig kan samenwerken zonder dat individuele bijdragen lekken.

4. De Drie Manieren om het te Gebruiken (De Profielen)

De paper beschrijft drie manieren om dit in de praktijk te brengen, afhankelijk van hoeveel je vertrouwt op hardware of software:

Profiel P1 (De "Vrije Kamer"):
Je gebruikt een speciale, beveiligde computerchip (een TEE/HSM) als vertrouwde dirigent. Deze chip doet de zware rekenwerkzaamheden in een "glazen kast" waar niemand bij kan. Dit is supersnel (5,8 milliseconden!) en veilig, maar je moet vertrouwen op de chipfabrikant.
- Vergelijking: Een bankkluis met een bewaker die alleen de sleutel heeft.
Profiel P2 (De "Volledige Chaos"):
Geen enkele vertrouwde chip. Alles gebeurt via complexe wiskundige protocollen tussen de mensen zelf. Dit is het veiligst (je vertrouwt niemand), maar het is wat langzamer (21 ms) en complexer.
- Vergelijking: Een vergadering waar iedereen blinddoeken draagt en alleen via een codeerapparaat communiceert.
Profiel P3+ (De "Half-Asynchrone" Manier):
Dit is ideaal voor mensen die niet 24/7 online hoeven te zijn (zoals bestuurders die een transactie moeten goedkeuren). De mensen bereiden hun stukjes alvast voor (offline). Zodra er een verzoek komt, sturen ze hun antwoord binnen een tijdvenster (bijv. 5 minuten).
- Vergelijking: Je vult een formulier in op je telefoon, en stuurt het pas op als je een e-mail krijgt. Je hoeft niet in een vergaderzaal te wachten tot iedereen er is.

5. Waarom is dit Geweldig?

Het past in bestaande systemen: De handtekening die hieruit komt, is precies hetzelfde formaat (3,3 KB) als de standaard. Oude systemen zien geen verschil. Het is een "plug-and-play" oplossing.
Het is snel: Het duurt slechts een fractie van een seconde.
Het is veilig: Zelfs als hackers een groot deel van de groep hebben gevangen, kunnen ze de sleutel niet stelen.
Het werkt voor grote groepen: Of je nu 3 van de 5 mensen nodig hebt, of 32 van de 45, het werkt allemaal even goed.

Conclusie

Deze paper lost een groot gat op in de beveiliging voor de toekomst. Het maakt het mogelijk om de nieuwe, quantum-proof digitale sleutels veilig te verdelen over een groep mensen, zonder dat de handtekening groter wordt of dat je vertrouwde hardware nodig hebt (hoewel dat een optie blijft).

Het is alsof je een onbreekbare schat hebt, en je de sleutel verdeelt over je vrienden. Zelfs als de helft van je vrienden wordt opgepakt, blijft de schat veilig, en kunnen de overgebleven vrienden de schat toch openen. En het beste van alles? De schatkist ziet er precies hetzelfde uit als voorheen, dus niemand merkt dat er iets veranderd is.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het paper "Threshold ML-DSA via Shamir Nonce DKG" van Leo Kao, vertaald en samengevat in het Nederlands.

1. Het Probleem: De "Threshold Gap" bij Post-Quantum Cryptografie

Met de komst van kwantumcomputers wordt de standaardisatie van post-kwantum algoritmen door NIST (FIPS 204) urgent. ML-DSA (Module-Lattice-Based Digital Signature Algorithm) is de nieuwe standaard. Echter, het implementeren van drempelondertekening (waarbij een groep van $N$ partijen een handtekening kan genereren met slechts $T$ deelnemers) voor ML-DSA is extreem moeilijk vanwege de specifieke structuur van het algoritme:

Fiat-Shamir met Abort: ML-DSA gebruikt een "rejection sampling" mechanisme. Een handtekening is alleen geldig als de responsvector $z = y + c \cdot s_1$ een bepaalde normgrens ( $\|z\|_\infty < \gamma_1 - \beta$ ) respecteert.
De Uitdaging: In een traditionele drempelsetting (zoals bij ECDSA) moeten de deeltjes van de geheime sleutel worden gecombineerd met Lagrange-coëfficiënten. Bij ML-DSA zijn deze coëfficiënten vaak erg groot (groter dan de modulus $q$ voor $T \ge 26$ ). Als men deze direct toepast, explodeert de grootte van de deeltjes, waardoor ze de rejectie-grens overschrijden en elke poging tot ondertekening faalt.
Bestaande Oplossingen en Hun Tekortkomingen:
- Korte coëfficiënten: Beperkt tot zeer lage drempels ( $T \le 6$ ).
- Noise Flooding: Maakt willekeurige drempels mogelijk, maar vergroot de handtekening met 5x (naar ~17 KB), wat in strijd is met het FIPS 204 formaat (3,3 KB).
- Gespecialiseerde constructies: Produceren handtekeningen die niet compatibel zijn met bestaande verifiers.

Er ontbreekt dus een oplossing die willekeurige drempels ( $T$ ), standaard handtekeninggrootte (FIPS 204 compatibel) en hoge succespercentages combineert.

2. Methodologie: Shamir Nonce DKG en Pairwise-Canceling Masks

De auteur presenteert een nieuw protocol dat twee kerntechnieken combineert om de bovengenoemde problemen op te lossen:

A. Shamir Nonce DKG (Distributed Key Generation)

Dit is de primaire innovatie. In plaats van de nonce (het willekeurige getal $y$ ) lokaal te genereren en te maskeren, genereren de partijen gezamenlijk de nonce via een Shamir Secret Sharing-protocol.

Structuur: De lange-termijn geheime sleutel $s_1$ is al verdeeld als een Shamir-polynoom van graad $T-1$ . Het protocol genereert de nonce $y$ ook als een Shamir-verdeling van graad $T-1$ .
Berekening: Elke partij $i$ berekent een deelrespons $z_i = y_i + c \cdot s_{1,i}$ zonder de Lagrange-coëfficiënt toe te passen.
Aggregatie: De combiner (of coordinator) past de Lagrange-coëfficiënten toe tijdens het samenvoegen: $z = \sum \lambda_i z_i = y + c \cdot s_1$ .
Voordeel: Omdat de Lagrange-vermenigvuldiging pas aan het einde gebeurt, blijven de individuele deeltjes $z_i$ klein genoeg om de rejectie-grens te halen.
Privacy: Omdat de aanvallers slechts $T-1$ evaluaties van een polynoom van graad $T-1$ zien, blijft er voldoende entropie over in de honest party's nonce-deel. Dit biedt statistische nonce-share privacy (geen computationele aannames nodig) zelfs als er maar één honest party is (in coordinator-gebaseerde profielen).

B. Pairwise-Canceling Masks

Om de privacy van andere waarden (zoals de commitment $W_i$ en de $r_0$ -check delen $V_i$ ) te waarborgen, worden maskers gebruikt die opgeteld nul worden.

Deze maskers zijn afgeleid van PRF's (Pseudorandom Functions) op basis van gedeelde zaden tussen paren partijen.
Ze verbergen individuele bijdragen aan de $r_0$ -check (die nodig is om de hint te genereren) zonder de correctheid van de som te beïnvloeden.

C. Drie Implementatieprofielen

Het paper definieert drie deployment-profielen met verschillende vertrouwensmodellen:

Profiel P1 (TEE-geassisteerd): Gebruikt een Trusted Execution Environment (TEE) als coordinator. De $r_0$ -check en hint-generatie gebeuren veilig binnen de enclave. Dit vereist 3 online rondes.
Profiel P2 (Volledig Gedistribueerd): Geen hardware-vertrouwen; gebruikt Secure Multi-Party Computation (MPC) met SPDZ en edaBits. Dit vereist 5 online rondes maar biedt "dishonest-majority" veiligheid (tot $N-1$ corrupties).
Profiel P3+ (Semi-Asynchroon 2PC): Ontworpen voor mens-in-de-lus autorisatie. Twee "Computation Parties" (CP's) voeren de $r_0$ -check uit via 2PC. Ondertekenaars pre-computeren nonces offline en reageren binnen een tijdsvenster. Dit vereist slechts 2 logische rondes.

3. Belangrijkste Bijdragen

Eerste FIPS 204-compatibele Threshold ML-DSA: Het is het eerste schema dat willekeurige drempels ondersteunt terwijl het exact dezelfde handtekeningformaat (3,3 KB) produceert als een enkele ondertekenaar, waardoor het direct door bestaande verifiers kan worden geverifieerd.
Statistische Nonce-Privacy: In tegenstelling tot eerdere werken die computationele aannames nodig hebben of een "twee-honest" vereiste ( $|S| \ge T+1$ ) hebben, biedt dit schema privacy met $|S| \ge T$ in coordinator-profielen, gebaseerd op conditionele min-entropy (statistisch bewezen).
Oplossing voor de Schaalbaarheidskloof: Het oplost het probleem van de Irwin-Hall verdeling (de som van uniforme nonces is niet uniform, maar gekleurd rond nul). De auteur toont aan dat de veiligheidsverlies hierdoor verwaarloosbaar is (< 0,013 bits per sessie voor $T \le 33$ ), in tegenstelling tot eerdere conservatieve schattingen die de beveiliging als "vacuous" (nietig) beschouwden bij hogere aantallen sessies.
Complexe UC-Bewijzen: Het paper levert volledige Universal Composability (UC) bewijzen voor alle drie de profielen.

4. Resultaten en Prestaties

De auteurs hebben een Rust-implementatie ontwikkeld en uitgebreid getest:

Succespercentages: De drempel-ondertekening behaalt een succespercentage van 21% tot 45% per poging. Dit is vergelijkbaar met (en soms zelfs beter dan) de enkele-ondertekenaar baseline (~20-25%) vanwege de concentratie van de Irwin-Hall verdeling rond nul.
Latentie:
- P1 (TEE): ~5,8 ms voor een 3-of-5 configuratie.
- P2 (MPC): ~21,5 ms voor 3-of-5.
- P3+ (Semi-Async): ~22,1 ms voor 3-of-5.
- De schaalbaarheid is indrukwekkend: tot 32-of-45 drempels blijven de latenties onder de 100 ms (voor P1 en P3+).
Veiligheid: De bewezen veiligheidsverlies door de Irwin-Hall verdeling is extreem klein (< 0,007 bits per sessie voor $T \le 17$ ). Zelfs bij 1.600 sessies blijft het totale verlies onder de 10 bits, wat de totale beveiliging (gebaseerd op Module-SIS) ruim voldoende laat blijven.
FIPS 204 Compliance: Alle gegenereerde handtekeningen zijn byte-identiek aan standaard ML-DSA handtekeningen en passeren verificatie zonder aanpassingen.

5. Betekenis en Impact

Dit werk is van fundamenteel belang voor de overgang naar post-kwantum cryptografie in enterprise-omgevingen:

Praktische Toepasbaarheid: Het maakt het mogelijk om ML-DSA te gebruiken in scenario's die hoge beveiliging vereisen, zoals cryptocurrency-custody, gedistribueerde Certificate Authorities (CA's) en multi-party authorisatie in financiële systemen, zonder in te leveren op compatibiliteit of prestaties.
Overbrugging van de Kloof: Het vult de kritieke kloof voor drempels tussen 9 en 32, waar veel real-world toepassingen vallen, en lost het probleem van de "two-honest" vereiste op.
Veiligheidsstandaard: Het biedt een rigoureuze theoretische basis (UC-bewijzen) voor drempelondertekening op lattices, wat een stap is naar de standaardisatie van veilige post-kwantum infrastructuur.
Flexibiliteit: Door drie verschillende profielen (TEE, MPC, Semi-Async) aan te bieden, kunnen organisaties kiezen voor een balans tussen hardware-vertrouwen, cryptografische zuiverheid en gebruiksgemak (bijv. menselijke autorisatie).

Kortom, dit paper levert de eerste volledig werkende, schaalbare en FIPS 204-compatibele oplossing voor drempelondertekening van ML-DSA, met bewezen statistische privacy en praktische prestaties die dicht bij single-signer oplossingen liggen.