Supuesto decisional de Diffie-Hellman

---

La suposición decisional de Diffie-Hellman (DDH) es una suposición de dureza computacional sobre un cierto problema que involucra logaritmos discretos en grupos cíclicos . Se utiliza como base para probar la seguridad de muchos protocolos criptográficos , especialmente los criptosistemas ElGamal y Cramer-Shoup .

Considere un grupo cíclico (multiplicativo) de orden y con generador . La suposición de DDH establece que, dado y elegido de manera uniforme e independiente , el valor "parece" un elemento aleatorio en .${\ Displaystyle G}$${\ Displaystyle q}$ ${\ Displaystyle g}$${\ Displaystyle g ^ {a}}$${\ Displaystyle g ^ {b}}$${\displaystyle a,b\in \mathbb {Z} _{q}}$${\displaystyle g^{ab}}$${\displaystyle G}$

Esta noción intuitiva puede afirmar formalmente diciendo que los siguientes dos distribuciones de probabilidad son computacionalmente indistinguibles (en el parámetro de seguridad , ):${\displaystyle n=\log(q)}$

El supuesto de DDH está relacionado con el supuesto de logaritmo discreto . Si fuera posible calcular de manera eficiente los registros discretos , entonces la suposición de DDH no se mantendría . Dado , uno podría decidir eficientemente si primero se toma el discreto de y luego se compara con .${\displaystyle G}$${\displaystyle G}$${\displaystyle (g^{a},g^{b},z)}$${\displaystyle z=g^{ab}}$${\displaystyle \log _{g}}$${\displaystyle g^{a}}$${\displaystyle z}$${\displaystyle (g^{b})^{a}}$

Se considera que DDH es una suposición más fuerte que la suposición de logaritmo discreto, porque hay grupos para los que se cree que calcular registros discretos es difícil (y por lo tanto, se cree que la suposición de DL es cierta), pero detectar tuplas de DDH es fácil (y, por lo tanto, DDH es falso). Debido a esto, se cree que exigir que la suposición de DDH se mantenga en un grupo es un requisito más restrictivo que DL.

---