El problema de Diffie-Hellman es el siguiente:
-
Sabemos que si podemos resolver el problema del Logaritmo Discreto, entonces podemos resolver el problema de Diffie-Hellman. Así, el problema de Diffie-Hellman es no más duro que el problema del logaritmo discreto. Hasta donde sabemos, el problema del logaritmo discreto es difícil.
-
Sin embargo, no sabemos si resolver el problema de Diffie-Hellman es al menos con la misma intensidad como resolver el problema del logaritmo discreto. En otras palabras, ¿hay alguna forma más fácil de calcular $g^{xy}$ dado $g$ , $g^x$ y $g^y$ que no implican encontrar $x$ o $y$ ? ¿O la resolución del problema de Diffie-Hellman también permitirá encontrar una solución fácil al correspondiente problema del logaritmo discreto (demostrando así que el problema del logaritmo discreto no es más difícil que el de Diffie-Hellman)?
Para darle una analogía, considere el problema de encontrar el máximo común divisor de dos enteros positivos $n$ y $m$ . Si podemos factorizar $n$ y $m$ en primos, $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ y $m=q_1^{\beta_1}\cdots q_r^{\beta_r}$ , entonces podemos encontrar el máximo común divisor encontrando todos los primos que aparecen en ambas factorizaciones, y tomando el menor de los dos exponentes. Por lo tanto, encontrar el gcd no es más difícil que la factorización; y hasta donde sabemos, la factorización es difícil. ¿Significa eso que encontrar el gcd es difícil?
¡No! Porque resulta que hay un método para calcular el gcd que hace no se basan en encontrar las factorizaciones primos de $n$ y $m$ (el Algoritmo euclidiano ), y este algoritmo resulta ser "fácil" (computacionalmente hablando).
La cuestión con el problema de Diffie-Hellman es que no sabemos si ocurre lo mismo. ¿Podría haber alguna otra forma inteligente de averiguar $g^{xy}$ sin tener que pasar por el problema del logaritmo discreto? Generalmente se cree que el Diffie-Hellman es al menos tan difícil como el problema del logaritmo discreto, por lo que se cree que no hay una forma tan inteligente, pero no hay ninguna prueba (hasta donde yo sé).
