Suposición computacional de Diffie-Hellman
La suposición computacional de Diffie-Hellman (CDH) es una suposición de dureza computacional sobre el problema de Diffie-Hellman . [1] La suposición de CDH implica el problema de calcular el logaritmo discreto en grupos cíclicos . El problema CDH ilustra el ataque de un espía en el protocolo de intercambio de claves Diffie-Hellman [2] para obtener la clave secreta intercambiada.
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 de CDH podría resolverse fácilmente:
uno podría calcular eficientemente de la siguiente manera:
Calcular el logaritmo discreto es el único método conocido para resolver el problema de CDH. Pero no hay pruebas de que sea, de hecho, el único método. Es un problema abierto determinar si la suposición de logaritmo discreto es equivalente a la suposición de CDH, aunque en ciertos casos especiales se puede demostrar que este es el caso. [3] [4]
El supuesto CDH es un supuesto más débil que el supuesto decisional Diffie-Hellman (supuesto DDH). Si calcular from fuera fácil (problema de CDH), entonces uno podría resolver el problema de DDH de manera trivial.
Muchos esquemas criptográficos que se construyen a partir del problema CDH se basan, de hecho, en la dureza del problema DDH. La seguridad semántica del intercambio de claves Diffie-Hellman , así como la seguridad del cifrado ElGamal, se basan en la dureza del problema DDH.