Wiki du cours

Rédacteur: [A remplir]

A traiter [تحرير]

• Quelques mots sur le partage de secret de Shamir [2].
• Signatures à seuil (threshold signatures / m-of-n multi-signatures) .
• Signatures à sous-groupe responsable (accountable-subgroup multi-signatures).
• Implémentation dans le cadre des signatures BLS.

Partage de secret de Shamir [تحرير]

Fonctionnement

On souhaite partager un secret \(D\) en n parties \(D_{1},D_{2},...,D_{n}\) de telles manières que :
1) k parties de \(D\) (i.e \(D_{i_1},...,D_{i_k}\)) distinctes ou plus nous permettent de retrouver \(D\)
2) k-1 parties ou moins ne nous permettent pas de déterminer\( D\)

Pour ce faire on choisit aléatoirement \(a_1,a_2,...,a_{k-1}\) des coefficient et on pose \(a_0=D\) dans un corps fini. On choisit aléatoirement \(x_i,i=1,...,n\) puis on définit \(y_i:= \sum_{j=0}^{k-1} a_j*x_i^j\) et on crée les points \((x_i,y_i) ,i=1,...,n\) qu'on attribue aux différents participants. Ainsi k points sont suffisants pour reconstruire la courbe (par interpolation polynomial) et à la fin on retrouve notre secret \(a_0=D\)

Propriétés

1)La taille de chaque pièces n'excede pas la taille des données d'origine.
2)Pour un \(k\) fixé, on peut aisément ajouter ou retirer de nouvelles parties sana en affecter les autres.
3)On peut facilement changer les pièces \(D_i\) sans changer \(D\).Pour cela on prend des nouveaux coefficients \(a_j,j=1,...,k-1\) choisis aléatoirement tout en conservant \(a_0=D\), on construit le polynome et on distribue les nouveaux points.
4)On peut instaurer une hiérarchie grâce aux parties.En effet on peut adjoindre un nombre différent de pièce à chaque personne.Cela peut s'avérer utile dans les organisation où la hiérarchie est importante.

Signatures à seuil (threshold signatures/m of n signatures) [تحرير]

Nous avons déjà vu le fonctionnement d’une signature. Le but de cette courte section est d’introduire le concept de signature à seuil. Si une organisation de personne souhaite transmettre un message à une personne \(P\) mais que le message à besoin d’être signé par \(t\) personnes de l’organisation ou plus, on va mettre au point un algorithme afin que \(P\) puisse vérifier que le seuil de \(t\) signataire ou plus de l’organisation est bien respecté. Dans ce exposé nous allons montrer un cas appliqué à BLS, plus loin. Une autre construction liée au partage de secret de Shamir est détaillé dans le polycopié « A Directed-Threshold Multi-Signature Scheme ».

Signature à sous-groupe responsable (accountable-subgroup multi-signatures) [تحرير]

Une signature à sous-groupe responsable (ASM) est un ensemble d’algorithme \(Pg,Kg,GSetup,Sign,KAg,Vf\) avec \(Pg\) le générateur de paramètre, \(Kg\) le générateur de clé, \(GSetup\) la clé d’adhésion,\(KAg\) la clé d’aggrégation,\(Sign\) et \(Vf\) respectivement les protocoles de signature et de vérification où:

-\(par\) \(\leftarrow Pg\)
-Tous les signataires génèrent une paire de clés \((pk,sk)\leftarrow Kg(par)\)
-Pour participer à un groupe de signataire \(PK={pk_1,…,pk_n}\),où les \(pk_i\) sont les clés publique personnelles des membres, tous les signataire doivent utiliser \(GSetup(sk,PK)\) afin d’avoir une clé d’adhésion \(mk\)
-N’importe quel sous ensemble \(S\) de l’ensemble des signataire peut collectivement signer un même message \(m\) grâce à l’algorithme \(Sign(par,PK,S,sk,mk,m)\) avec \(mk\) la clé d’adhésion liée à \(S\) (en fait on utilise l’opération d’avant en remplaçant \(PK\) par \(S\)) et on obtient une signature \(\sigma\).

On obtient enfin une clé d’aggrégation grâce à \(KAg\) qu’on note \(apk\). La signature est vérifié grâce à \(Vf(par,apk,S,m,\sigma\)] qui renvoie soit 0 ou 1.

Implémentation dans le cadre des signatures BLS [تحرير]

Dans le cas général on considère \(\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_t \) trois groupes d’ordre \(q\) avec \(q\) premier.Pour notre implémentation on va considérer
On consière aussi \(e:\mathbb{G}_1\times \mathbb{G}_2 \rightarrow \mathbb{G}_t\) un couplage non dégénéré.
On considère enfin 3 fonctions de hachage \(H_0:\{0,1\}^{*} \rightarrow \mathbb{G}_2\) ,\(H_1:\{0,1\}^{*} \rightarrow \mathbb{Z}_q\) et \(H_2:\{0,1\}^* \rightarrow \mathbb{G}_1\).

On définit \(G\) comme le générateur de groupe bilinéaire qui prends un paramètre de sécurité \(k\) et renvoie un ensemble de groupe multiplicatif \((q,\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_t,e,g_1,g_2)\) avec \(g_i\) le générateur de \(\mathbb{G}_i\) pour \(i=1,2\).

Dans notre cas spécifique pour l’implémentation BLS on va considéree que \(\mathbb{G}_1=\mathbb{G}_2=\mathbb{G}\). \(g_1,g_2\) sont 2 générateurs du même groupe.

L’implémentation se passe comme suit:

-Générateur de paramètre :\(Pg(k)\) est construit grâce à \((q,\mathbb{G},\mathbb{G},\mathbb{G}_t,e,g_1,g_2)\leftarrow G(k)\) et ensuite \(par\leftarrow (q,\mathbb{G},\mathbb{G},\mathbb{G}_t,e,g_1,g_2)\).

Générateur de clé : L’algorithme \(Kg\) choisit aléatoirement \(sk\leftarrow \mathbb{Z}_q\) et ensuite calcule \(pk\leftarrow g_2^{sk}\). Enfin il renvoie le couple \((pk,sk)\).

-Clé d’aggrégation : \(KAg(\{pk1,…,pkn\}\) nous renvoie \(apk\leftarrow\prod_{i=1}^{n} {pk_i} ^{H_1(pk_i,\{pk_,…,pk_n\})}\).

-Group Setup: Afin d’avoir une clé d’adhésion \(GSetup(sk_i,PK=\{pk_1,…,pk_n)\}\) vérifie que chaque \(pk_i\in PK\) et que \(i\) est bien l’indice de \(pk_i\) dans \(PK\). Chaque signataire \(i\) calcule la clé d’agrégation \(apk\leftarrow KAg(PK)\) ainsi que \(a_i\leftarrow H_1(pk_i,PK)\). On définit \(\mu_{i,j}= H_2(apk,j)^{a_i*sk_i}\) pour un signataire \(j=1,…,n\) et cela retourne la clé d’adhésion \(mk_i\leftarrow \prod_{j=1}^{n} \mu_{i,j}\).

-Signature: l’algorithme \(Sign(par,PK,S,sk_i,mk_i,m)\) calcule les \(s_i\leftarrow H_0(apk,m)^{sk_i} *mk_i\) qu’il envoie à un membre désigné (c’est une personne d’un sous-ensemble S de l’ensemble des signataires). Ce membre calcule \(pk\leftarrow \prod_{j\in S} pk_j\), \(s\leftarrow \prod_{j\in S} s_j\) ce qui nous donne une mulltisignature \(\sigma := (pk,s)\).

Vérification:\(Vf(par,apk,S,m,\sigma)\) calcule \(e(H_0(apk,m),pk)*e(\prod_{j\in S} H_2(apk,j) ,apk)\). Si ce dernier est égal à \(e(s,g_2)\) \(Vf\) renvoie 1 sinon il renvoie 0.

On peut vérifier en sachant que \(pk=g_2^{\sum_{i\in S} sk_i}\),
\(apk=g_2^{\sum_{i\in \{1,…n\}} a_i*pk_i}\)
et que \(s=H_0(apk,m)^{\sum_{i\in S} sk_i}*\prod_{i\in S }H_2 (apk,i)^{\sum_{j\in \{1,…n\}} a_j*sk_j} \) que on a alors


\(e(s,g_2)= (H_0(apk,m)^{\sum_{i\in S} sk_i}*\prod_{i\in S }H_2 (apk,i)^{\sum_{j\in \{1,…n\}} a_j*sk_j},g_2) \)

\(=e(H_0(apk,m),pk)*e(\prod_{i\in S }H_2 (apk,i),g_2^{\sum_{i\in \{1,…n\}} a_i*pk_i})\)

\(=e(H_0(apk,m),pk)*e(\prod_{i\in S }H_2 (apk,i),apk))\).

Références [تحرير]

[1] Dan Boneh, Manu Drijvers, Gregory Neven, Compact multi-signatures for smaller blockchains, Sections 1.1, 1.2, 3.1, 4.1, 4.2
[2] Adi Shamir, How to share a secret
[3] BLS signatures: better than Schnorr
[4] Sunder Lal and Manoj Kumar «A directed threshold multi-signature scheme  » https://arxiv.org/pdf/cs/0409049