ECDSA à seuil : signature multipartite

Les signatures ECDSA nécessitent le calcul d’un nonce aléatoire k, du point de courbe R = k*G et de la signature s = k^{-1}(h + r*x) mod n où x est la clé privée et r est l’abscisse de R. L’inversion de k et la multiplication par la clé privée rendent ECDSA intrinsèquement non linéaire, contrairement aux signatures de Schnorr, dont la réponse est une simple combinaison linéaire. Cette non-linéarité rend extrêmement difficile la répartition du calcul entre plusieurs parties.

Le protocole GG18 de Gennaro et Goldfeder (2018) a été la première construction pratique de signature ECDSA à deux parties et à seuil sécurisée sans distributeur de confiance. L’idée fondamentale consiste à utiliser le chiffrement homomorphe de Paillier pour effectuer la conversion multiplicative-additive (MtA) nécessaire au calcul ECDSA non linéaire. GG18 offre une sécurité fondée sur la simulation contre des adversaires statiques semi-honnêtes.

GG20 (Gennaro et Goldfeder, 2020) a amélioré GG18 en démontrant sa sécurité contre des adversaires malveillants sans configuration de confiance. GG20 a ajouté des preuves à connaissance nulle pour garantir que chaque partie respecte correctement le protocole. Ces preuves empêchent une partie malveillante de biaiser le nonce ou la signature afin d’extraire des informations sur les parts de clé des autres parties. GG20 est devenu la base de nombreuses implémentations de portefeuilles MPC utilisées en production.

CGGMP21 (Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021) est actuellement le protocole ECDSA à seuil le plus avancé. Il permet un abandon identifiable : si le protocole de signature échoue en raison d'un comportement malveillant, il peut identifier la partie responsable. Cette propriété est essentielle pour les déploiements en entreprise, où la responsabilité est importante. CGGMP21 est implémenté dans des bibliothèques MPC populaires, notamment tss-lib et multi-party-sig.

Le principal défi de l'ECDSA à seuil consiste à calculer le produit des parts secrètes sans les révéler. La conversion MtA (multiplicative-additive) transforme le produit a*b des parts de deux parties en parts additives : la partie 1 obtient alpha et la partie 2 obtient beta, de sorte que alpha + beta = a*b. Cette opération s'effectue au moyen du chiffrement de Paillier : la partie 1 chiffre a, la partie 2 effectue une multiplication homomorphe par b et ajoute de l'aléa, puis la partie 1 déchiffre le résultat pour obtenir les parts additives.

Le chiffrement de Paillier est un schéma de chiffrement homomorphe partiel qui prend en charge à la fois l'addition et la multiplication par une valeur en clair. À partir d'un chiffrement Enc(a), il est possible de calculer Enc(a*b) pour une valeur b connue, sans déchiffrer. Cette propriété permet le protocole MtA : la partie 1 génère une paire de clés Paillier et envoie Enc(k1) et Enc(x1), qui sont les parts de la valeur unique et de la clé privée. La partie 2 utilise des opérations homomorphes pour calculer sa contribution sans connaître k1 ni x1.

La signature ECDSA à seuil comporte généralement plusieurs tours de communication. Dans GG20, une phase de prétraitement de 2 tours calcule des engagements sur la valeur unique et les valeurs aléatoires de masquage, puis une phase de signature en ligne d'un tour combine les signatures partielles. Le prétraitement peut être effectué avant que le message soit connu, ce qui réduit la latence en ligne à un seul tour. CGGMP21 optimise encore ce processus.

Un abandon identifiable signifie que si le protocole de signature à seuil échoue, parce qu'une partie a envoyé un message malformé ou n'a pas respecté le protocole, les parties honnêtes peuvent déterminer cryptographiquement quelle partie s'est mal comportée. Cela nécessite des preuves à divulgation nulle de connaissance du calcul correct à chaque étape. Sans abandon identifiable, une partie malveillante pourrait provoquer un déni de service, en refusant d'achever le protocole, sans être identifiée.

EdDSA (signatures fondées sur Schnorr sur Ed25519) est beaucoup plus facile à adapter au seuil que l'ECDSA, car les signatures de Schnorr sont linéaires : la réponse z = r + c*x est une somme de parts additives. FROST (Flexible Round-Optimized Schnorr Threshold) de Komlo et Goldberg (2020) permet d'obtenir une signature Schnorr à seuil en deux tours, sans configuration de confiance. FROST fait actuellement l'objet d'une normalisation par l'IETF (projet de RFC) pour être utilisé dans des protocoles préservant la confidentialité et des portefeuilles de cryptomonnaies.

L'ECDSA à seuil est plus coûteux en calcul que l'ECDSA utilisé par une seule partie, en raison du protocole MtA et des preuves à divulgation nulle de connaissance. La signature à deux parties de GG20 prend environ 1 à 2 secondes sur du matériel moderne ; un seuil avec une valeur de n plus grande prend plus de temps en raison d'un plus grand nombre d'exécutions MtA par paire. Les optimisations de CGGMP21 réduisent ce délai à quelques centaines de millisecondes. Pour les transactions de cryptomonnaie où la latence de signature est importante, ces performances restent acceptables, mais ne sont pas négligeables.

L'ECDSA à seuil est déployé à grande échelle dans le secteur financier institutionnel. Fireblocks utilise un ECDSA à seuil fondé sur GG20, qui sécurise un volume de transactions supérieur à 4 000 milliards de dollars. Coinbase Prime utilise une conservation MPC fondée sur les signatures à seuil. Qredo et Copper.co proposent un ECDSA à seuil pour la gestion d'actifs institutionnels. La bibliothèque Go tss-lib, utilisée par Binance, et multi-party-sig, utilisée par Coinbase, sont deux implémentations majeures à code source ouvert.

Quel rôle le chiffrement homomorphe de Paillier joue-t-il dans l'ECDSA à seuil ?

L'ECDSA à seuil permet à t parties de signer sans qu'aucune partie ne connaisse la clé complète. La structure non linéaire de l'ECDSA nécessite une conversion MtA au moyen du chiffrement homomorphe de Paillier. GG18 a été à l'origine de cette approche, GG20 y a ajouté la sécurité contre les parties malveillantes, et CGGMP21 y a ajouté l'abandon identifiable. EdDSA/Schnorr est plus facile à adapter au seuil grâce à FROST, qui fonctionne en 2 tours sans configuration de confiance. Les déploiements de Fireblocks et Coinbase sécurisent des milliers de milliards de dollars d'actifs.