Suposición computacional de Diffie-Hellman

La suposición de Diffie-Hellman computacional (CDH) es una suposición de dificultad computacional sobre el problema de Diffie-Hellman . ^{[ 1 ]} La suposición CDH implica el problema de calcular el logaritmo discreto en grupos cíclicos . El problema CDH ilustra el ataque de un intruso en el protocolo de intercambio de claves Diffie-Hellman ^{[ 2 ]} para obtener la clave secreta intercambiada.

Consideremos un grupo cíclico G de orden q . La hipótesis CDH establece que, dado 

${\displaystyle (g,g^{a},g^{b})\,}$

para un generador g elegido aleatoriamente y aleatorio

${\displaystyle a,b\in \{0,\ldots ,q-1\},\,}$

Es computacionalmente intratable calcular el valor

${\displaystyle g^{ab}.\,}$

La suposición CDH está fuertemente relacionada con la suposición del logaritmo discreto . Si calcular el logaritmo discreto (base g ) en G fuera fácil, entonces el problema CDH podría resolverse fácilmente:

Dado

${\displaystyle (g,g^{a},g^{b}),\,}$

uno podría calcular eficientemente${\displaystyle g^{ab}}$De la siguiente manera:

• calcular${\displaystyle a}$tomando el logaritmo discreto de${\displaystyle g^{a}}$a base${\displaystyle g}$;
• calcular${\displaystyle g^{ab}}$por exponenciación:${\displaystyle g^{ab}=(g^{b})^{a}}$;

El cálculo del logaritmo discreto es el único método conocido para resolver el problema CDH. Sin embargo, no existe prueba alguna de que sea, de hecho, el único método. Es un problema abierto determinar si la suposición del logaritmo discreto es equivalente a la suposición CDH, aunque en ciertos casos especiales se puede demostrar que lo es. ^{[ 3 ] [ 4 ]}

La suposición CDH es una suposición más débil que la suposición decisional de Diffie-Hellman (suposición DDH). Si se calcula${\displaystyle g^{ab}}$de${\displaystyle (g,g^{a},g^{b})}$Si el problema CDH era fácil, entonces se podía resolver el problema DDH trivialmente.

Muchos esquemas criptográficos construidos a partir del problema CDH se basan, de hecho, en la dificultad del problema DDH. La seguridad semántica del intercambio de claves Diffie-Hellman , así como la seguridad del cifrado ElGamal, dependen de la dificultad del problema DDH.

Existen construcciones concretas de grupos donde la suposición más fuerte de DDH no se cumple, pero la suposición más débil de CDH todavía parece ser una hipótesis razonable. ^{[ 5 ]}

Se han estudiado las siguientes variaciones del problema CDH y se ha demostrado que son equivalentes al problema CDH: ^{[ 6 ]}

• Problema computacional cuadrado de Diffie-Hellman (SCDH): En la entrada${\displaystyle g,g^{x}}$, calcular${\displaystyle g^{x^{2}}}$; ^{[ 7 ]}
• Problema inverso computacional de Diffie-Hellman (InvCDH): En la entrada${\displaystyle g,g^{x}}$, calcular${\displaystyle g^{x^{-1}}}$; ^{[ 8 ]}
• Problema de Diffie-Hellman de cálculo divisible (DCDH): En la entrada${\displaystyle g,g^{x},g^{y}}$, calcular${\displaystyle g^{y/x}}$.

Dejar${\displaystyle G_{1}}$y${\displaystyle G_{2}}$sean dos grupos cíclicos .

• Problema de Diffie-Hellman co-computacional (co-CDH): Dado${\displaystyle g,g^{a}\in G_{1}}$y${\displaystyle h\in G_{2}}$, calcular${\displaystyle h^{a}\in G_{2}}$. ^{[ 9 ]}