ECDSA a soglia: firma multiparte

Le firme ECDSA richiedono il calcolo di un nonce casuale k, del punto della curva R = k*G e della firma s = k^{-1}(h + r*x) mod n, dove x è la chiave privata e r è la coordinata x di R. L'inversione di k e la moltiplicazione per la chiave privata rendono ECDSA intrinsecamente non lineare, a differenza delle firme Schnorr, in cui la risposta è una semplice combinazione lineare. Questa non linearità rende estremamente complessa la distribuzione del calcolo tra più parti.

Il protocollo GG18 di Gennaro e Goldfeder (2018) è stata la prima costruzione pratica di ECDSA a due parti e a soglia sicura senza un distributore fidato. L'idea fondamentale consiste nell'utilizzare la cifratura omomorfica di Paillier per eseguire la conversione da moltiplicativa ad additiva (MtA) necessaria per il calcolo non lineare di ECDSA. GG18 offre sicurezza basata sulla simulazione contro avversari statici semi-onesti.

GG20 (Gennaro e Goldfeder 2020) ha migliorato GG18 dimostrando la sicurezza contro avversari malevoli senza una configurazione fidata. GG20 ha aggiunto prove a conoscenza zero per garantire che ogni parte segua correttamente il protocollo. Queste prove impediscono a una parte malevola di alterare il nonce o la firma per estrarre informazioni sulle quote delle chiavi delle altre parti. GG20 è diventato la base di molte implementazioni di wallet MPC in produzione.

CGGMP21 (Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021) è l'attuale protocollo ECDSA a soglia allo stato dell'arte. Consente un'interruzione identificabile: se il protocollo di firma non riesce a causa di un comportamento malevolo, il protocollo può identificare il partecipante responsabile. Questo è fondamentale nelle implementazioni aziendali, dove la responsabilità è importante. CGGMP21 è implementato in librerie MPC diffuse, tra cui tss-lib e multi-party-sig.

La sfida fondamentale nell'ECDSA a soglia consiste nel calcolare il prodotto di quote segrete senza rivelarle. La conversione MtA (da moltiplicativa ad additiva) trasforma il prodotto a*b delle quote di due partecipanti in quote additive: il partecipante 1 ottiene alpha e il partecipante 2 ottiene beta, in modo che alpha + beta = a*b. Questo risultato si ottiene usando la crittografia Paillier: il partecipante 1 cifra a, il partecipante 2 moltiplica omomorficamente per b e aggiunge casualità, quindi il partecipante 1 decifra il risultato per ottenere le quote additive.

La crittografia Paillier è uno schema di crittografia omomorfica parziale che supporta sia l'addizione sia la moltiplicazione per un valore in chiaro. Data una cifratura Enc(a), chiunque può calcolare Enc(a*b) per un valore b noto senza decifrare. Questa proprietà rende possibile il protocollo MtA: il partecipante 1 genera una coppia di chiavi Paillier e invia Enc(k1) e Enc(x1), che sono le quote del nonce e della chiave privata. Il partecipante 2 usa operazioni omomorfiche per calcolare il proprio contributo senza conoscere k1 o x1.

La firma ECDSA a soglia prevede in genere diversi round di comunicazione. In GG20, esiste una fase di preelaborazione (2 round) che calcola gli impegni relativi al nonce e ai valori casuali di mascheramento, e una fase di firma online (1 round) che combina le firme parziali. La preelaborazione può essere eseguita prima che il messaggio sia noto, riducendo la latenza online a un solo round. CGGMP21 ottimizza ulteriormente questo processo.

Un'interruzione identificabile significa che, se il protocollo di firma a soglia non riesce perché un partecipante ha inviato un messaggio malformato o non ha seguito il protocollo, i partecipanti onesti possono determinare crittograficamente quale partecipante si è comportato scorrettamente. A questo scopo servono prove a conoscenza zero del corretto calcolo a ogni passaggio. Senza un'interruzione identificabile, un partecipante malevolo potrebbe causare una negazione del servizio, rifiutandosi di completare il protocollo senza essere identificato.

EdDSA (firme basate su Schnorr su Ed25519) è molto più semplice da trasformare in uno schema a soglia rispetto a ECDSA, perché le firme Schnorr sono lineari: la risposta z = r + c*x è una somma di quote additive. FROST (Flexible Round-Optimized Schnorr Threshold) di Komlo e Goldberg (2020) consente di eseguire firme Schnorr a soglia in due round, senza una configurazione fidata. FROST è in fase di standardizzazione da parte dell'IETF (bozza RFC) per l'uso in protocolli che tutelano la privacy e nei wallet di criptovalute.

L'ECDSA a soglia è più costoso dal punto di vista computazionale rispetto all'ECDSA eseguito da un singolo partecipante, a causa del protocollo MtA e delle prove a conoscenza zero. La firma a due partecipanti in GG20 richiede circa 1–2 secondi su hardware moderno; con un valore maggiore di n, la firma a soglia richiede più tempo a causa dell'aumento delle esecuzioni MtA tra coppie di partecipanti. Le ottimizzazioni di CGGMP21 riducono questo tempo a poche centinaia di millisecondi. Per le transazioni di criptovalute, in cui la latenza della firma è importante, queste prestazioni sono accettabili, ma non trascurabili.

L'ECDSA a soglia è implementato su larga scala nella finanza istituzionale. Fireblocks usa l'ECDSA a soglia basato su GG20 per proteggere un volume di transazioni superiore a 4.000 miliardi di dollari. Coinbase Prime usa una custodia MPC basata su firme a soglia. Qredo e Copper.co offrono l'ECDSA a soglia per la gestione istituzionale degli asset. La libreria Go tss-lib (usata da Binance) e multi-party-sig (usata da Coinbase) sono importanti implementazioni open source.

Quale ruolo svolge la crittografia omomorfica Paillier nell'ECDSA a soglia?

L'ECDSA a soglia consente a t partecipanti di firmare senza che alcun partecipante conosca la chiave completa. La struttura non lineare di ECDSA richiede la conversione MtA tramite la crittografia omomorfica Paillier. GG18 ha introdotto questo approccio, GG20 ha aggiunto la sicurezza contro partecipanti malevoli e CGGMP21 ha aggiunto l'interruzione identificabile. EdDSA/Schnorr è più semplice da trasformare in uno schema a soglia tramite FROST (2 round, senza configurazione fidata). Le implementazioni in produzione presso Fireblocks e Coinbase proteggono asset per migliaia di miliardi.