FROST : signatures de seuil de Schnorr flexibles et optimisées pour l'arrondi


GEL est un protocole de signature Schnorr à seuil optimal.

Pourquoi FROST ?

Afin d'améliorer l'efficacité des systèmes de signature de seuil de Coinbase. qui présente les avantages suivants par rapport aux autres protocoles de signature de seuil basés sur Schnorr [GJKR03, SS01] :

Faible complexité ronde dans les phases de génération de clés distribuées et de signature. La phase de génération de clés distribuées peut être complétée en 2 tours. La phase de signature peut être complétée en 3 tours ou moins selon que l'on utilise un rôle d'agrégateur de signature et une étape de prétraitement. C'est-à-dire,

  • Signature en un tour avec un agrégateur de signatures de confiance et une étape de prétraitement
  • Signature en 2 tours avec un agrégateur de signatures de confiance, mais pas d'étape de prétraitement
  • Signature en 3 tours sans agrégateur de signatures de confiance et sans étape de prétraitement

Sécurité simultanée. La phase de signature est sécurisée lorsqu'elle est effectuée simultanément. C'est-à-dire qu'un nombre illimité d'opérations de signature peut être effectué en parallèle. Contrairement aux autres protocoles de signature à seuil Schnorr, il existe des protocoles de signature à seuil basés sur Schnorr, tels que [GJKR03, SS01], qui ont la même complexité ronde, mais ils souffrent d'une concurrence limitée pour se protéger contre l'attaque de Drijvers et al. [DEF19]. Cette attaque a été initialement proposée dans un paramètre Schnorr multi-signature n-sur-n, mais elle s'applique également de la même manière dans un paramètre seuil t-sur-n avec les mêmes paramètres pour un adversaire qui contrôle jusqu'à t-1 participantes.6 du projet FROST pour plus de détails. Pour empêcher cette attaque sans limiter la concurrence, FROST lie la réponse de chaque participant à un message spécifique ainsi qu'à l'ensemble des participants et à leur ensemble de points de courbe elliptique (EC) utilisés pour cette opération de signature particulière. Ce faisant, la combinaison des réponses sur différents messages ou paires de points EC entraîne une signature invalide, contrecarrant les attaques telles que celles de Drijvers, et al.

Sécurisé contre la majorité malhonnête. FROST est sécurisé contre les adversaires qui contrôlent jusqu'à t-1 signataires dans la phase de signature.

Blocs de construction et hypothèses cryptographiques simples. FROST est construit sur les schémas de partage de secret Shamir à seuil et de partage de secret vérifiable Feldman et repose uniquement sur l'hypothèse du logarithme discret.

Comment fonctionne FROST  ?

Avant de présenter le fonctionnement de FROST, rappelons d'abord comment fonctionne la signature autonome Schnorr.

Un algorithme de signature numérique Schnorr est un triplet d'algorithmes  : (KeyGen, Sign, Verify).

Soit G un générateur de groupe d'un groupe cyclique d'ordre premier p, et soit H une fonction de hachage cryptographique appliquée au champ Zₚ* . Une signature Schnorr est générée sur un message m par les étapes suivantes  :

KeyGen -> (sk, vk)

  • Échantillonnez au hasard la clé secrète sk  sig
    • Échantillonnez au hasard un nonce secret k vrai/faux
      • Parse sig = (z', c')
      • R' = z * G -c * vk
      • c’ = H(m, R’)
      • Renvoie true si c = c', sinon renvoie false

      On appelle (sk, vk) respectivement les clés secrète et de vérification.

      FROST est un protocole de signature à seuil de Schnorr qui contient deux composants importants. Premièrement, n participants exécutent un génération de clé distribuée (DKG) protocole pour générer une clé de vérification commune ; à la fin, chaque participant obtient un partage de clé secrète privée et un partage de clé de vérification publique. Par la suite, tous les participants t sur n peuvent exécuter un signature de seuil protocole pour générer de manière collaborative une signature Schnorr valide. La figure ci-dessous donne une esquisse de haut niveau du fonctionnement de FROST dans le cas de t = 3 et n = 5.

      (3.

      La clé secrète de signature dans la signature Schnorr est un élément du champ Z'. L'objectif de cette phase est de générer des partages de clés secrètes à longue durée de vie et une clé de vérification conjointe. Cette phase est animée par n participants. FROST construit sa propre phase de génération de clés sur le DKG de Pedersen [GJKR03], dans lequel il utilise à la fois le partage de secrets de Shamir et les schémas de partage de secrets vérifiables de Feldman comme sous-programmes. En outre, FROST exige également que chaque participant démontre la connaissance de son propre secret en envoyant aux autres participants une preuve de connaissance zéro, qui est elle-même une signature Schnorr. Cette étape supplémentaire protège contre les attaques par clé non autorisée dans le cadre où t ≥ n/2.

      A la fin du protocole DKG, une clé de vérification conjointe vk est générée. De plus, chaque participant Pᵢ détient une valeur (i, skᵢ) qui est sa part de secret de longue durée et une part de clé de vérification vkᵢ = skᵢ*G. Le partage de clé de vérification vkᵢ du participant Pᵢ est utilisé par d'autres participants pour vérifier l'exactitude des partages de signature de Pᵢ lors de la phase de signature, tandis que la clé de vérification vk est utilisée par des parties externes pour vérifier les signatures émises par le groupe.

      Cette phase s'appuie sur des techniques connues qui emploient un partage de secret additif et une conversion de partage pour générer de manière non interactive le nonce pour chaque signature. Cette phase tire également parti des techniques de liaison pour éviter les attaques de falsification connues sans limiter la concurrence.

      Notre mise en œuvre est légèrement adaptée du projet FROST. Dans notre implémentation. Au lieu de cela, chaque participant est un agrégateur de signatures. Cette conception est plus sécurisée : tous les participants au protocole vérifient ce que les autres ont calculé pour atteindre un niveau de sécurité plus élevé et réduire les risques. à notre connaissance. De plus. Dans l'étape de prétraitement, chaque participant prépare un nombre fixe de paires de points EC pour une utilisation ultérieure, qui est exécuté une seule fois pour plusieurs phases de signature de seuil. Cependant. Plus en détail, il existe deux différences majeures entre notre mise en œuvre et le projet d'origine.

      Tout d'abord, l'agrégateur de signatures, tel que décrit dans le brouillon, valide les messages diffusés par les cosignataires et calcule la signature finale. Dans notre mise en œuvre. Au lieu de cela, chaque participant effectue simplement une diffusion à la place d'un agrégateur de signatures assurant la coordination. Notez que FROST peut être instancié sans un agrégateur de signatures tel que souligné dans le projet. De plus, sa mise en œuvre de manière décentralisée est plus appropriée à l'approche de calcul multipartite de Coinbase.

      Deuxièmement, le protocole du projet utilise une étape de prétraitement avant la signature, où chaque participant Pᵢ échantillonne un numéro de séquence, disons Q, de nonces à usage unique (dᵢⱼ, eᵢⱼ), calcule et diffuse des paires de points publics (Dᵢⱼ = dᵢⱼ* G, Eᵢⱼ = eᵢⱼ*G) pour une utilisation ultérieure dans les rondes de signature suivantes, où j = 1….Q. Cette étape de prétraitement est une étape unique. C'est-à-dire que chaque participant peut préparer un nombre fixe de paires de points EC, disons Q, et les diffuser à l'agrégateur de signatures, puis l'agrégateur de signatures distribue ces paires de points EC à tous les participants pour une utilisation ultérieure. Une fois ces paires de points EC épuisées, ces participants doivent exécuter une autre étape de prétraitement., Eᵢ). Par conséquent, il y a pas d'étape de prétraitement dans notre implémentation et donc il y a 3 tours dans notre phase de signature de seuil au lieu de 2. Notez également que si notre implémentation contient l'étape de prétraitement ou non dépend simplement du nombre de paires de points EC générés dans le tour de signature 1. Si chaque participant génère un Q nombre de paires de points EC dans le tour de signature 1, alors ce tour peut être considéré comme l'étape de prétraitement et notre implémentation devient un protocole de signature à 2 tours.

      1er tour de signature. Chaque participant Pᵢ commence par générer une seule paire de nonce privée (dᵢ, eᵢ) et une paire correspondante de points EC (Dᵢ, Eᵢ) et diffuse cette paire de points à tous les autres participants. Chaque participant stocke ces paires de points EC reçus pour une utilisation ultérieure. Les rondes de signature 2 et 3 sont les opérations réelles dans lesquelles t participants sur n coopèrent pour créer une signature Schnorr valide.

      Signature du deuxième tour. Pour créer une signature Schnorr valide, tous les participants t travaillent ensemble pour exécuter ce tour. La technique de base derrière ce tour est partage de secret additif t-sur-t. Cette technique crée le nonce secret k = SUM(kᵢ), qui est la même valeur générée dans l'algorithme de signature de Schnorr à partie unique, et chaque kᵢ est la part calculée par le participant Pᵢ. Pour ce faire, chaque participant prépare l'ensemble des couples de points EC B = (D₁, E₁)……(Dₜ, Eₜ) reçus au tour 1, puis calcule kᵢ = dᵢ+eᵢ*rᵢ , où rᵢ=H(i, m, B) et H est une fonction de hachage dont les sorties sont dans le champ Z'. Le calcul de rᵢ est important car il fonctionne comme une valeur contraignante pour chaque participant afin d'empêcher l'attaque de contrefaçon. Ensuite, chaque participant calcule l'engagement Rᵢ=Dᵢ+Eᵢ*rᵢ de telle sorte qu'il lie le message m, l'ensemble des participants signataires et les points EC de chaque participant à chaque partage de signature, de sorte que les partages de signature pour un message ne puissent pas être utilisés pour un autre. Cela empêche l'attaque de falsification car les attaquants ne peuvent pas combiner des partages de signature entre des opérations de signature distinctes ou permuter l'ensemble de signataires ou de points publiés pour chaque signataire. L'engagement pour l'ensemble des signataires est alors simplement R = SUM(Rᵢ). Comme dans les signatures de Schnorr à un seul parti, chaque participant calcule le défi c = H(m, R).

      Après avoir calculé le défi c, chaque participant est capable de calculer la réponse zᵢ au défi en utilisant les nonces à usage unique (dᵢ, eᵢ) et les parts secrètes à long terme skᵢ, qui sont t-sur-n (degré t -1) Shamir partage le secret de la clé de longue durée du groupe. Une observation principale que FROST exploite est que si kᵢ sont des parts additives de k, alors chaque kᵢ/Lᵢ sont des parts de Shamir t-sur-n de k, où Lᵢ est le coefficient de Lagrange pour le participant Pᵢ. C'est-à-dire Lᵢ = prod(i/(j-i)), où j = 1,…,t, j ≠i. Cette observation est due aux travaux de Benaloh et Leichter [BL88] et le travail de Cramer, Damgaard et Ishai [CDI05]. Ils présentent un mécanisme non interactif permettant aux participants de convertir localement les partages additifs générés via la construction de partage de secrets t-sur-n de Benaloh et Leichter en forme polynomiale de Shamir. FROST utilise le cas t-sur-t le plus simple de cette transformation. Ainsi kᵢ/Lᵢ+skᵢ*c sont les parts secrètes de Shamir de degré t-1 de la réponse correcte z = k+sk*c pour une signature de Schnorr simple (à partie unique). En utilisant à nouveau la conversion des parts et la valeur que chaque participant a calculée (à savoir, kᵢ = dᵢ+eᵢ*rᵢ). À la fin du deuxième tour de signature, chaque participant diffuse zᵢ aux autres participants.

      3e ronde de signature. Après avoir reçu zᵢ de tous les autres participants, chaque participant vérifie la cohérence de ces zᵢ rapportés, avec leur paire de points EC (Dᵢ, Eᵢ) et leur partage de clé de vérification vkᵢ. Cela peut être fait en vérifiant l'équation zᵢ*G = Rᵢ+c*Lᵢ*vkᵢ. Une fois que tous les zᵢ sont valides, chaque participant calcule z = SUM(zᵢ) et produit (z, c) comme signature de Schnorr finale. Cette signature vérifiera correctement pour toute partie ignorant que FROST a été utilisé pour générer la signature, et peut la vérifier avec l'équation de vérification standard de Schnorr à partie unique avec vk comme clé de vérification. Ainsi, chaque participant fonctionne comme un agrégateur de signatures. Par conséquent.

      Défis de mise en œuvre

      . Une implémentation Golang provient du groupe Taurus, mais malheureusement, cette implémentation Go n'est pas prête pour une utilisation en production et n'a pas été auditée en externe. En conséquence.

      Une caractéristique de la signature FROST est que chaque participant doit connaître les coefficients de Lagrange pour chaque participant afin de calculer zᵢ. Ceci est rare dans d'autres protocoles de signature à seuil qui utilisent le partage de secret vérifiable Feldman comme sous-protocole, il existe donc peu de bibliothèques Go pour prendre en charge CECI. La plupart des bibliothèques existantes prennent en charge la génération de partages secrets, de polynômes et leur interpolation, mais ne prennent pas en charge le calcul du coefficient de Lagrange. Pour combler cette lacune technique. Avant d'exécuter le protocole de signature de seuil, il prend les identifiants d'entrée des t participants et génère tous les coefficients de Lagrange. Comme le suggère le projet FROST.

      Sommaire

      FROST est un schéma de signature de seuil Schnorr flexible et optimisé pour les rondes qui minimise la surcharge du réseau liée à la production de signatures Schnorr dans un paramètre de seuil tout en permettant un parallélisme illimité des opérations de signature et un nombre seuil de participants signataires. soulignons ses fonctionnalités et le décrivons dans une approche entièrement décentralisée (c'est-à-dire sans agrégateur de signatures tiers).

      Si vous êtes intéressé par la cryptographie de pointe, Coinbase recrute.

      FROST : Les signatures de seuil Schnorr optimisées pour les rondes flexibles ont été initialement publiées dans le blog Coinbase sur Medium, où les gens poursuivent la conversation en mettant en évidence et en répondant à cette histoire.

    • Service de signature de seuil de production
    • Dernières nouvelles de l'industrie de l'eau : Birdz félicité par Frost & Sullivan pour ses solutions et services d'eau intelligents axés sur la ville intelligente, @birdz_iot
    • Concours de dépassement de la course de Crypto.com  !
    • Concours de dépassement de la course de Crypto.com  !