Hypothèse décisionnelle de Diffie-Hellman

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

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

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

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 ${\displaystyle G}$, alors l'hypothèse de Diffie-Hellman ne serait pas définie dans ${\displaystyle G}$. Si on a ${\displaystyle (g^{a},g^{b},z)}$, n'importe qui pourrait déterminer efficacement ${\displaystyle z=g^{ab}}$ en prenant le premier ${\displaystyle \log _{g}}$ discret de ${\displaystyle g^{a}}$ puis comparer ${\displaystyle z}$ avec ${\displaystyle (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 ${\displaystyle 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 ${\displaystyle g^{ab}}$ à partir de ${\displaystyle (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 ${\displaystyle 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.

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 ${\displaystyle r,r'}$ tirés aléatoirement, et ${\displaystyle (g^{a},g^{b},g^{ab})}$ un triplet DDH, alors ${\displaystyle ((g^{a})^{r},(g^{b})^{r'},(g^{ab})^{r\cdot r'})}$ est lui-même un triplet DDH.