Wiki du cours

Rédacteur: Vassiliki Beris

A traiter [Modifier]

• Rappel: Problème de Diffie-Hellman décisionel/calculatoire.
• Groupes "Gap Diffie-Hellman". Quel type de courbes elliptiques satisfont cette propriété?
• Schéma de signature GDH (création de clé, algorithme de signature, algorithme de vérification).
• Agrégation de signatures (voir [3]).

I. Rappel: Problèmes de Diffie-Hellman [Modifier]

I.1 Problème de Diffie-Hellman décisionnel

Etant donnés \(P\), \(aP\) et \(bP\) dans \(E(\mathbb{F}_{q})\) et donné un point \(Q \in E(\mathbb{F}_{q}) \); est-il possible de déterminer si \(Q = abP\) ?

I.2 Problème de Diffie-Hellman calculatoire

Etant donnés \(P\), \(aP\) et \(bP\) dans \( E(\mathbb{F}_{q}) \) peut-on obtenir \(abP\)?

II. Groupes "Gap Diffie-Hellman". [Modifier]

II.1 Groupes GDH

On considère un groupe cyclique multiplicatif \(G =<g>\) avec \(p = |G| \) un premier. On va s'intéresser à 3 problèmes sur \(G\):

1. Action de groupe: Données \(u, v \in G\), trouver \(uv\).
2. Diffie-Hellman décisionnel (DDH): Pour \(a,b,c \in {Z}_{p}^*\), donnés (\(g, g^a, g^b ,g^c\)), déterminer si \(c = ab\)
3. Diffie-Hellman calculatoire (CDH): Pour \(a,b \in {Z}_{p}^*\), donnés (\(g, g^a, g^b\)), calculer \(g^{ab}\)

On définit un GDH-groupe par étapes:

• Définition 1: \(G\) est un groupe \(\tau\)-décision pour Diffie-Hellman si le calcul de l'action de groupe prend une unité de temps et DDH peut être effectué sur \(G\) en un temps maximal \(\tau\).
  
• Définition 2: L'avantage d'un algorithme \(A\) utilisé pour résoudre CDH dans un groupe \(G\) est : \(AdvCDH_{A} = Pr [A(g,g^a, g^b) = g^{ab} : a,b \leftarrow {Z}_{p}^* ]\); où la probabilité repose sur choix de \(a\) et \(b\) ainsi que sur l'algorithme \(A\).
  On dit qu'un algorithme \(A\) \((t,\epsilon)\)-casse CDH dans \(G\) si \(A\) fonctionne en un temps maximal \(t\) et \(AdvCDH_{A} \geqslant\ \epsilon\)
  
• Définition 3: Un groupe d'ordre premier \(G\) est un \( (\tau, t, \epsilon)\)-GDH groupe si c'est un groupe \(\tau\)-décision pour Diffie-Hellman et qu'aucun algorithme \((t,\epsilon)\)-casse CDH sur \(G\)

II.2 Courbes elliptiques comme GDH

On veut présenter un schéma de signature qui fonctionne sur n'importe quel groupe GDH; et on remarque qu'en utilisant le couplage de Weil, certaines courbes elliptiques pourront être utilisées comme des groupes GDH, afin de permettre des GDH-signatures beaucoup plus courtes.

En particulier, on va s'intéresser à des courbes du type : \(y^2 = x^3 + 2x ± 1\) sur \(\mathbb{F}_{3^l}\). On peut choisir une courbe elliptique pour le schéma de signature GDH si elle peut être utilisée pour construire un groupe \(G\) (avec \(p = |G| \) un grand premier), sur lequel CDH est difficile mais DDH est facile.

Pour pouvoir obtenir un tel résultat pour les algorithmes de Diffie-Hellman, on va introduire la notion de multiplicateur de sécurité:

Définition: Soient \(p\) un premier, \(l\) un exposant positif et \(E\) une courbe elliptique sur \(\mathbb{F}_{p^l}\) possédant \(m\) points; et soit \(P \in E\) un point d'ordre \(q\) (où \(q\) est premier) avec \(q^2 \nmid m\). On dit qu'un sous-groupe \(<P>\) possède un multiplicateur de sécurité \(\alpha\) (où \(\alpha > 0\) est un entier) si l'ordre de \(p^l\) dans \(\mathbb{F}^*_{q}\) est \(\alpha\).
En d'autres termes:

• \(q | p^{l\alpha} - 1 \) et
• \( q \nmid p^{lk} - 1\), \( \forall k = 1, 2, ..., \alpha - 1\)

Remarques: Comme on va le voir,

• Pour que CDH soit difficile à résoudre dans \(<P>\), le multiplicateur de sécurité \(\alpha\) ne doit pas être trop petit.
• Pour que l'algorithme DDH soit efficace dans \(<P>\) , \(\alpha\) ne doit pas être trop grand.

Pour obtenir un tel \(\alpha\) qui soit suffisamment grand pour la sécurité et suffisamment petit pour l'efficacité on utilise une famille de courbes elliptiques dont certains membres ont \(\alpha = 6\) (Suffisant pour obtenir des signatures courtes). On n'arrive pas pour l'instant, à créer des courbes elliptiques possédant un \(\alpha\) plus grand (par exemple \(\alpha = 10\) ).

II.3 Propriétés de ce type de courbes elliptiques

A. Problème du logarithme discret sur ces courbes elliptiques:

Soit \(<P>\) un sous-groupe de \(E/\mathbb{F}_{p^l}\) d'ordre \(q\) possédant un multiplicateur de sécurité \(\alpha\). Nous pouvons résoudre le problème du logarithme discret de 2 manières:

• MOV: On utilise un homomorphisme pour transformer le problème du logarithme discret dans \(<P>\) en un problème de logarithme discret dans une extension de \(\mathbb{F}_{p^l}\) (par exemple: \(\mathbb{F}_{p^{li}}\)). (Voir Wiki Sujet 18: Le problème du logarithme discret et attaques III). Pour ce faire, il faut que l'image de \(<P>\) par cet homomorphisme soir un sous-groupe de \(\mathbb{F}^*_{p^{li}}\) d'ordre \(q\). On a donc que \(q | p^{li} - 1 \) , ce qui implique par définition du multiplicateur de sécurité que \(i \ge \alpha\). Ainsi, par MOV, on peut dans le meilleur des cas résoudre le problème du logarithme discret sur un sous groupe de \(\mathbb{F}^*_{p^{l\alpha}}\) .

Pour que le problème du logarithme discret soit difficile sur \(<P>\), il faut donc que \(\alpha\) soit grand.

• Générique: (Pas de bébé-Pas de géant ; Méthode \(\rho\) de Pollard). Ces algorithmes fonctionnent en un temps proportionnel à \(\sqrt{q}\). Il faut donc que \(q\) soit suffisamment grand pour rendre le problème du logarithme discret difficile sur \(<P>\).

(Voir Wiki Sujets 16 et 17: Le problème du logarithme discret et attaques I & II).

B. DDH sur ces courbes elliptiques:

Soit \(P \in E/\mathbb{F}_{p^l}\) un point d'ordre \(q\) premier. Supposons que le sous-groupe \(<P>\) possède un multiplicateur de sécurité \(\alpha\) et supposons aussi que \( q \nmid p^{l} - 1\). Un résultat de Balasubramanian & Koblitz montre que \(E/\mathbb{F}_{p^{l\alpha}}\) possède un point \(Q\) linéairement indépendant de \(P\). (C'est-à-dire, on ne peut pas trouver de \(k\) tel que \(Q=kP\); on peut le vérifier facilement par le couplage de Weil:

En posant \(E[q]\) le sous-groupe de \(E/ \mathbb{F}_{p^{l\alpha}}\) généré par \(P\) et \(Q\), on définit le couplage de Weil \(e : E[q] \times E[q] \to \mathbb{F}^*_{p^{l\alpha}}\) tel que \(\forall R_{1}, R_{2} \in E[q], e(R_{1},R_{2}) = 1 \) si et seulement si \(R_{1}\) et \(R_{2}\) sont linéairement dépendants. . Puisque \(P\) et \(Q\) sont des points linéairement indépendants (d'ordre \(q\)), ce couplage de Weil nous permet de de déterminer si le tuple \((P,aP,Q,bQ)\) est tel que \(a = b\) mod \(q\) (En effet c'est le cas si et seulement si \(e(P,bQ) = e(aP,Q)\) ).

De plus, si on suppose qu'il existe un morphisme \(\phi\) de \(<P>\) à \(<Q>\), on a que \(\forall a, \phi(aP) = axQ\) ,où \(xQ = \phi(P)\). Dans ce cas, le couplage de Weil nous permet de déterminer si le tuple \((P,aP,bP,cP)\) est tel que \(ab = c\) mod \(q\). (C'est bien le cas si et seulement si \( e(P,\phi(cP)) = e(aP, \phi(bP)\) ).

Grâce à ce morphisme \(\phi\), le couplage de Weil nous fournit un algorithme pour le problème de Diffie-Hellman Décisionnel. (Voir Wiki Sujet 20: Solution du problème de Diffie-Hellman décisionnel par le couplage de Weil))

C. Courbe supersingulière

Rappel: (cf. Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 5.3.1)

Soit \(E\) une courbe elliptique définie sur \(\mathbb{F}_{q}\), où \(q\) est la puissance d'un nombre premier \(p\). Alors #\(E(\mathbb{F}_{q^m})=q+1−a\) pour un certain entier \(a\). On dit qu'une courbe \(E\) est supersingulière si \(a \equiv 0 \) mod \(p\) (où lorsque \(a = 0\) si \(p = q \ge 5\) (Corollaire 4.32).

En utilisant les méthodes A. et B. on dérive les courbes supersingulières (groupes GDH) \(E\) données par \(y^2 = x^3 + 2x ± 1\) sur \(\mathbb{F}_{3^l}\). En effet, ce sont les seules courbes ellptiques supersingulières possédant un multiplicateur de sécurité \(\alpha = 6\). (A noter que pour des courbes supersingulières, \(\alpha = 6\) est la valeur maximale que l'on peut obtenir). La réduction MOV transforme le problème du logarithme discret sur \(E/\mathbb{F}_{3^l}\) en un problème sur \(\mathbb{F}^3_{3^{6l}}\). De cette façon, on peut utiliser des valeurs assez petites pour \(l\) afin d'obtenir des signatures courtes (bonus efficacité) ; mais la sécurité dépend toujours du problème du logarithme discret dans un champ large mais fini (i.e. \(\mathbb{F}^3_{3^{6l}}\)).

III. Schéma de signature GDH [Modifier]

Ce schéma de signature fonction pour tout groupe GDH \(G\) (y compris les courbes supersingulières de la forme \(y^2 = x^3 + 2x ± 1 \) sur \(\mathbb{F}_{3^l}\) ). Comme on l'a vu précédemment, l'intérêt d'utiliser des telles courbes dans ce schéma de signature est de fournir des signatures plus courtes.

Le schéma de signature GDH permet la création de signatures sur un message arbitraire \(m \in\) {\(0,1\)}\(^*\). Une signature \(\sigma\) est un élément du groupe \(G\). Notre groupe de \(G\) ainsi que le générateur \(g\) sont des paramètres du système. On note \(G^*\) l'ensemble \(G^* = G\) \ {\(1\)} où \(1\) est l'identité de \(G\).

Le schéma de signature comprend 3 algorithmes :

• La génération des clés
• La signature
• La vérification.

et il nécessite une fonction de hachage \(h : \){\(0,1\)}\(^* \to G^*\).

• Création des clés: On choisit un nombre aléatoire \(x \in \mathbb{Z}^*_{p}\) et on calcule \(v \leftarrow g^x\). La clé publique est \(v\). La clé secrète est \(x\).
• Algorithme de signature: Donnée une clé secrète \(x\) et un message \(M \in \){\(0,1\)}\(^*\), on calcule \(h \leftarrow h(M)\) et \(\sigma \leftarrow h^x\).La signature est \(\sigma \in G^*\).
• Algorithme de vérification: Donnée une clé publique \(v\) ; un message \(M\) et une signature \(\sigma\), on calcule \(h \leftarrow h(M)\) et on vérifie que \((g, v, h, \sigma)\) est un tuple valide de Diffie-Hellman.

Ici c'est bien le cas puisque, comme \(g\) et \(h\) sont connues des deux parties, (B) possède toutes les informations nécessaires pour vérifier la signature \(\sigma\) (à partir du message \(M\) qu'elle a envoyé à (A)), en calculant \(h(M)^x = \sigma\). Si l'égalité est vérifée, cela implique que la signature a été validée et que les deux parties s'authentifient comme étant les bons destinataires. A noter que la vérification se fait en résolvant le DDH (supposé facile).

IV. Agrégation de signatures [Modifier]

Le schéma de signature est complété par une procédure d'agrégation de signature. Donnés un triplet contenant: une signature \(\sigma_{i}\), une clé publique \(p_{i}\) et un message \(m_{i}\), on peut agréger les signatures \(\sigma_{1}, ..., \sigma_{n} \in G\) en une signature \(\sigma\) comprenant la somme des \(\sigma_{i}; \forall i = 1,...n\). On calcule donc \(\sigma \leftarrow \sigma_{1} \cdot \cdot \cdot \sigma_{n} \in G\)

Pour vérifier une telle signature agrégée \(\sigma\), on vérifie que \(e(g,\sigma) = e(p_{1},H(m_{1}))\cdot e(p_{2},H(m_{2}))...e(p_{n},H(m_{n})) \)

Vérifions alors:
\(e(g,\sigma)= e(g,\sigma_{1}) \cdot e(g,\sigma_{2}) \cdot ... \cdot e(g,\sigma_{n}) \)
\(\Leftrightarrow e(g,\sigma) = e(g, (H(m_{1}))^{x_{1}}) \cdot e(g, (H(m_{2}))^{x_{2}}) \cdot ... \cdot e(g, (H(m_{n}))^{x_{n}}) \)
\( \Leftrightarrow e(g,\sigma) = e(g^{x_{1}}, H(m_{1})) \cdot ... \cdot e(g^{x_{n}}, H(m_{1})) \)
\(\Leftrightarrow e(g,\sigma)= e(p_{1},H(m_{1}))\cdot e(p_{2},H(m_{2}))...e(p_{n},H(m_{n})) \)

Il faut tout de même connaître toutes les clés publiques et calculer \(n+1\) fonctions de couplage, mais au moins on a toutes les signatures agrégées en un bloc qui prends moins de place que toutes les signatures indépendamment.

Références [Modifier]

[1] Sujets 16, 17, 18 : Le problème du logarithme discret et attaques (I, II et III).
[2] Sujet 20: Echange de clés de Diffie-Hellman
[3] Dan Boneh, Ben Lynn, Hovav Shacham, Short signatures from the Weil pairing, Sections 2, 3
[4] BLS signatures: better than Schnorr
[5] Dan Boneh, Manu Drijvers, Gregory Neven, Compact multi-signatures for smaller blockchains, Section 1.1