Problema de Diffie-Hellman

El problema Diffie-Hellman ( DHP ) es un problema matemático propuesto por primera vez por Whitfield Diffie y Martin Hellman ^[1] en el contexto de la criptografía y sirve como base teórica del intercambio de claves Diffie-Hellman y sus derivados. La motivación de este problema es que muchos sistemas de seguridad utilizan funciones unidireccionales : operaciones matemáticas que son rápidas de calcular, pero difíciles de revertir. Por ejemplo, permiten cifrar un mensaje, pero revertir el cifrado es difícil. Si resolver el DHP fuera fácil, estos sistemas se romperían fácilmente.

Descripción del problema

El problema de Diffie-Hellman se enuncia informalmente de la siguiente manera:

Dado un elemento y los valores de y , ¿cuál es el valor de ? ${\displaystyle g}$ ${\displaystyle g^{x}}$ ${\displaystyle g^{y}}$ ${\displaystyle g^{xy}}$

Formalmente, es un generador de algún grupo (normalmente el grupo multiplicativo de un campo finito o un grupo de curvas elípticas ) y y son números enteros elegidos aleatoriamente. ${\displaystyle g}$ ${\displaystyle x}$ ${\displaystyle y}$

Por ejemplo, en el intercambio de claves Diffie-Hellman, un espía observa e intercambia como parte del protocolo, y las dos partes calculan la clave compartida . Un medio rápido para resolver el DHP permitiría a un espía violar la privacidad del intercambio de claves Diffie-Hellman y muchas de sus variantes, incluido el cifrado ElGamal . ${\displaystyle g^{x}}$ ${\displaystyle g^{y}}$ ${\displaystyle g^{xy}}$

Complejidad computacional

En criptografía , para ciertos grupos, se supone que el DHP es difícil, y esto a menudo se denomina hipótesis de Diffie-Hellman . El problema ha sobrevivido al escrutinio durante algunas décadas y aún no se ha publicado ninguna solución "fácil".

A partir de 2006, el medio más eficiente conocido para resolver el DHP es resolver el problema del logaritmo discreto (DLP), que consiste en hallar x dados g y g ^x . De hecho, se ha logrado un progreso significativo (por den Boer, Maurer , Wolf, Boneh y Lipton ) para demostrar que en muchos grupos el DHP es casi tan difícil como el DLP. Hasta la fecha no hay pruebas de que ni el DHP ni el DLP sean un problema difícil, excepto en grupos genéricos (por Nechaev y Shoup ). Una prueba de que cualquiera de los dos problemas es difícil implica que P  ≠  NP .

Otras variantes

Se han considerado muchas variantes del problema de Diffie-Hellman. La variante más significativa es el problema de Diffie-Hellman decisional (DDHP), que consiste en distinguir g ^xy de un elemento aleatorio de un grupo, dados g , g ^x y g ^y . A veces, el DHP se denomina problema de Diffie-Hellman computacional (CDHP) para distinguirlo más claramente del DDHP. Recientemente, los grupos con emparejamientos se han vuelto populares y, en estos grupos, el DDHP es fácil, aunque todavía se supone que el CDHP es difícil. Para variantes menos significativas del DHP, consulte las referencias.

Véase también

• Problema de logaritmo discreto
• Criptografía de curva elíptica

Referencias

1. Diffie, W.; Hellman, M. (1976-11-01). "Nuevas direcciones en criptografía". IEEE Transactions on Information Theory . 22 (6): 644–654. doi :10.1109/TIT.1976.1055638. ISSN  0018-9448 – vía IEEE.

• B. den Boer, Diffie–Hellman es tan fuerte como el logaritmo discreto para ciertos números primos en Advances in Cryptology – CRYPTO 88, Lecture Notes in Computer Science 403, Springer, pág. 530, 1988.
• UM Maurer y S. Wolf, Oráculo Diffie–Hellman en Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, págs. 268–282, 1996.
• Maurer, Ueli M.; Wolf, Stefan (2000). "El protocolo Diffie-Hellman". Diseños, códigos y criptografía . 19 (2/3): 147–171. doi :10.1023/A:1008302122286. S2CID  42734334.
• D. Boneh y RJ Lipton, Algoritmos para campos de caja negra y su aplicación a la criptografía en Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, págs. 283–297, 1996.
• A. Muzereau, NP Smart y F. Vercauteran, La equivalencia entre DHP y DLP para curvas elípticas utilizadas en aplicaciones prácticas , LMS J. Comput. Math., 7 , págs. 50–72, 2004. Véase [www.lms.ac.uk].
• DRL Brown y RP Gallant, El problema estático de Diffie-Hellman, IACR ePrint 2004/306.
• VI Nechaev, Complejidad de un algoritmo determinado para el logaritmo discreto , Notas matemáticas, 55 (2), págs. 165-172, 1994.
• V. Shoup, Límites inferiores para logaritmos discretos y problemas relacionados en Advances in Cryptology – EUROCRYPT 97, (W. Fumy, ed.), Lecture Notes in Computer Science 1233, Springer, págs. 256–266, 1997.
• Bao, Feng; Deng, Robert H.; Zhu, Huafei (2003). "Variaciones del problema de Diffie-Hellman". ICICS 2003: Seguridad de la información y las comunicaciones . Apuntes de clase en informática. Vol. 2836. Springer. págs. 301–312. CiteSeerX  10.1.1.104.3007 . doi :10.1007/978-3-540-39927-8_28. ISBN . 978-3-540-20150-2.
• Boneh, Dan (1998). "El problema de decisión Diffie-Hellman". ANTS 1998: Teoría algorítmica de números . Apuntes de clase en informática. Vol. 1423. Springer. págs. 48–63. CiteSeerX  10.1.1.461.9971 . doi :10.1007/bfb0054851. ISBN. 978-3-540-64657-0.
• Bresson, Emmanuel; Chevassut, Olivier; Pointcheval, David (2003). "Los problemas del grupo Diffie-Hellman" (PDF) . SAC 2002: Áreas seleccionadas en criptografía . Apuntes de clase en informática. Vol. 2595. Springer. págs. 325–338. doi :10.1007/3-540-36492-7_21. ISBN . 978-3-540-00622-0.S2CID14425909  .​
• Biham, Eli; Boneh, Dan; Reingold, Omer (1999). "Romper un módulo Diffie–Hellman generalizado de un compuesto no es más fácil que factorizar". Information Processing Letters . 70 (2): 83–87. CiteSeerX  10.1.1.39.110 . doi :10.1016/S0020-0190(99)00047-2.
• Steiner, Michael; Tsudik, Gene; Waidner, Michael (1996). "Distribución de claves Diffie-Hellman extendida a la comunicación grupal" . Actas de la 3.ª conferencia de la ACM sobre seguridad informática y de las comunicaciones - CCS '96. ACM. págs. 31–37. CiteSeerX  10.1.1.35.9717 . doi :10.1145/238168.238182. ISBN . 978-0897918299.S2CID 13919278  .