Hypothèse décisionnelle de Diffie-Hellman

Cet article est une ébauche concernant la cryptologie et la sécurité informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

L'hypothèse décisionnelle de Diffie-Hellman (abrégé l'hypothèse DDH de l'anglais decisional Diffie–Hellman) est une hypothèse calculatoire à propos d'un problème impliquant la difficulté calculatoire du calcul du logarithme discret dans les groupes cycliques. Il est utilisé comme hypothèse de base dans les preuves de la sécurité de nombreux protocoles cryptographiques, notamment le cryptosystème de ElGamal et le cryptosystème de Cramer-Shoup.

Définition[modifier | modifier le code]

Soit un groupe (noté multiplicativement) cyclique $G$ d'ordre $q$ , et un générateur $g$ de $G$ . L'hypothèse décisionnelle de Diffie-Hellman énonce que pour $g^{a}$ et $g^{b}$ avec $a,b\in \mathbb {Z} _{q}$ choisis uniformément et indépendamment, la valeur $g^{ab}$ « ressemble » à un élément aléatoire de $G$ .

Cette notion intuitive est formellement énoncée en considérant les deux distributions de probabilité suivantes comme étant calculatoirement indistinguables (avec comme paramètre de sécurité, $n=\log(q)$ ) :

$(g^{a},g^{b},g^{ab})$ , avec $a$ et $b$ choisis uniformément et indépendamment dans $\mathbb {Z} _{q}$ .
$(g^{a},g^{b},g^{c})$ , avec $a,b,c$ choisis uniformément et indépendamment dans $\mathbb {Z} _{q}$ .

Les 3-uplets du premier genre sont souvent appelés triplés DDH ou tuples DDH.

Relation avec les autres hypothèses[modifier | modifier le code]

L'hypothèse décisionnelle de Diffie-Hellman est en lien avec l'hypothèse du logarithme discret. S'il était possible de calculer rapidement les logarithmes discrets dans $G$ , alors l'hypothèse de Diffie-Hellman ne serait pas définie dans $G$ . Si on a $(g^{a},g^{b},z)$ , n'importe qui pourrait déterminer efficacement $z=g^{ab}$ en prenant le premier $\log _{g}$ discret de $g^{a}$ puis comparer $z$ avec $(g^{b})^{a}$ .

L'hypothèse décisionnelle de Diffie-Hellman est considérée comme une hypothèse plus forte que le logarithme discret. L'hypothèse est plus forte puisque s'il était possible de résoudre le logarithme discret dans le groupe $G$ , alors il serait aisé de résoudre l'hypothèse de décision de Diffie-Hellmann. Par conséquent, si l'hypothèse DDH tient, alors la difficulté du logarithme discret tient aussi. Ainsi, avoir l'hypothèse de Diffie-Hellman qui tient sur un groupe est une condition nécessaire plus restrictive.

L'hypothèse DDH est également liée a sa variante calculatoire CDH (pour Computational Diffie-Hellman). S'il était possible de calculer efficacement $g^{ab}$ à partir de $(g^{a},g^{b})$ , alors n'importe qui pourrait facilement distinguer les deux distributions de probabilité énoncées ci-dessus, il lui suffirait de calculer $g^{ab}$ et de le comparer au troisième terme du triplet. De la même manière qu'énoncé précédemment, l'hypothèse DDH est considérée comme hypothèse plus forte que l'hypothèse calculatoire de Diffie-Hellman. Et même strictement plus forte puisqu'il existe des groupes où DDH est facile, mais sa variante calculatoire ne l'est pas^[1]. Cette séparation stricte implique aussi la séparation stricte entre DDH et le logarithme discret, puisque CDH est aussi une hypothèse plus forte que le problème du logarithme discret.

Autres propriétés[modifier | modifier le code]

Le problème de la détection des tuples DDH est l'auto-réductibilité aléatoire (random self-reducibility en anglais), signifiant en substance que s'il est compliqué, même pour une petite fraction des entrées, il est difficile pour presque toutes les sorties; s'il est facile même pour une fraction des entrées, il est facile pour presque toutes les sorties.

Cette auto-réductibilité aléatoire se prouve ainsi : étant donnés $r,r'$ tirés aléatoirement, et $(g^{a},g^{b},g^{ab})$ un triplet DDH, alors $((g^{a})^{r},(g^{b})^{r'},(g^{ab})^{r\cdot r'})$ est lui-même un triplet DDH.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Decisional Diffie-Hellmann assumption » (voir la liste des auteurs).

↑ Joux et Nguyen 2003.

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[Boneh 1998] (en) Dan Boneh, « The Decision Diffie-Hellmann Problem », ANTS, lNCS,‎ 1998 (DOI 10.1007/BFb0054851)
[Menezes, van Oorschot et Vanstone 1996] (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, 1996, 780 p. (ISBN 0-8493-8523-7, lire en ligne [PDF]), « Chapitre 3.7 The Diffie-Hellman problem »
[Joux et Nguyen 2003] (en) Antoine Joux et Kim Nguyen, « Separating Decision Diffie–Hellman from Computational Diffie–Hellman in Cryptographic Groups », Journal of Cryptology, vol. 16, n^o 4,‎ 2003, p. 239−247 (DOI 10.1007/s00145-003-0052-4)

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

(en) « What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman? », sur StackExchange (consulté le 23 janvier 2017)

[JouxNguyen2003-1] Joux et Nguyen 2003.

[1]