Hypothèse décisionnelle de Diffie-Hellman

L'hypothèse décisionnelle de Diffie-Hellman (abrégé l'hypothèse DDH de l'anglais Modèle:Langue) 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

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

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 Modèle:Langue). 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 pasModèle:Sfn. 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

Le problème de la détection des tuples DDH est l'auto-réductibilité aléatoire (Modèle:Langue 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^{\prime }$ tirés aléatoirement, et $(g^a,g^b,g^{ab})$ un triplet DDH, alors $((g^a{)}^r,(g^b{)}^{r^{\prime }},(g^{ab}{)}^{r\cdot r^{\prime }})$ est lui-même un triplet DDH.

Annexes

Bibliographie

• Modèle:Article
• Modèle:Ouvrage
• Modèle:Article

Articles connexes

• Problème de Diffie-Hellman
• Problème RSA
• Logarithme discret
• Hypothèse calculatoire

Liens externes

• Modèle:Lien web

Modèle:Portail