Supuesto computacional de Diffie-Hellman

El supuesto computacional de Diffie-Hellman (CDH) es un supuesto de dureza computacional sobre el problema de Diffie-Hellman . ^[1] El supuesto 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.

Definición

Considere un grupo cíclico G de orden  q . El supuesto de 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}.\,}$

Relación con logaritmos discretos

El supuesto de CDH está fuertemente relacionado con el supuesto de 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}),\,}$

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

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

Calcular el logaritmo discreto es el único método conocido para resolver el problema CDH. Pero no hay pruebas de que sea, de hecho, el único método. Es un problema abierto determinar si el supuesto de registro discreto es equivalente al supuesto de CDH, aunque en ciertos casos especiales se puede demostrar que así es. ^{[3] [4]}

Relación con el supuesto decisivo de Diffie-Hellman

El supuesto CDH es más débil que el supuesto decisional de Diffie-Hellman (supuesto DDH). Si calcular desde fuera fácil (problema CDH), entonces se podría resolver el problema DDH de forma trivial. ${\displaystyle g^{ab}}$ ${\displaystyle (g,g^{a},g^{b})}$

Muchos esquemas criptográficos que se construyen a partir del problema CDH dependen de la dureza del problema DDH. La seguridad semántica del intercambio de claves Diffie-Hellman , así como la seguridad del cifrado ElGamal, dependen de la dureza del problema DDH.

Hay construcciones concretas de grupos en las que el supuesto más fuerte de DDH no se cumple, pero el supuesto más débil de CDH todavía parece ser una hipótesis razonable. ^[5]

Variaciones del supuesto computacional de Diffie-Hellman

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 , calcule ; ^[7] ${\displaystyle g,g^{x}}$ ${\displaystyle g^{x^{2}}}$
• Problema computacional inverso de Diffie-Hellman (InvCDH): en la entrada , calcule ; ^[8] ${\displaystyle g,g^{x}}$ ${\displaystyle g^{x^{-1}}}$
• Cálculo divisible Problema de Diffie-Hellman (DCDH): en la entrada , calcule ; ${\displaystyle g,g^{x},g^{y}}$ ${\displaystyle g^{y/x}}$

Variaciones del supuesto computacional de Diffie-Hellman en grupos de productos

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

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

Referencias

1. Bellare, Mihir; Rogaway, Phillip (2005), Introducción a la criptografía moderna (PDF)
2. Diffie, Whitfield; Hellman, Martin (1976), Nuevas direcciones en criptografía (PDF)
3. den Boer, Bert (1988), Diffie-Hellman es tan fuerte como un registro discreto para ciertos números primos (PDF) , Lecture Notes in Computer Science, vol. 403, págs. 530–539, doi : 10.1007/0-387-34799-2_38 , ISBN 978-0-387-97196-4
4. Maurer, Ueli M. (1994), Hacia la equivalencia de romper el protocolo Diffie-Hellman y calcular logaritmos discretos , CiteSeerX 10.1.1.26.530 
5. Joux, Antoine; Nguyen, Kim (2003), "Separación de la decisión Diffie-Hellman de la Diffie-Hellman computacional en grupos criptográficos", Journal of Cryptology , 16 (4): 239–247, doi : 10.1007/s00145-003-0052-4
6. Bao, Feng; Deng, Robert H.; Zhu, Huafei (2003), Variaciones del problema Diffie-Hellman (PDF)
7. Burmester, Mike; Desmedt, Yvo; Seberry, Jeniffer (1998), "Resumen ampliado de depósito de claves equitativo con un período de tiempo limitado (o cómo hacer cumplir el vencimiento del tiempo criptográficamente)" (PDF) , depósito de claves equitativo con un período de tiempo limitado (o cómo hacer cumplir el vencimiento del tiempo criptográficamente) , Apuntes de conferencias sobre informática, vol. 1514, págs. 380–391, doi : 10.1007/3-540-49649-1_30 , ISBN 978-3-540-65109-3
8. Pfitzmann, Brigitte; Sadeghi, Ahmad-Reza (2000), "Huellas dactilares anónimas con no repudio directo" (PDF) , Avances en criptología - ASIACRYPT 2000 , Lecture Notes in Computer Science, vol. 1976, págs. 401–414, doi : 10.1007/3-540-44448-3_31 , ISBN 978-3-540-41404-9
9. Boneh, Dan; Lynn, Ben; Shacham, Hovav (2004), "Firmas breves del emparejamiento Weil" (PDF) , Journal of Cryptology , 17 (4): 297–319, doi :10.1007/s00145-004-0314-9, S2CID  929219