Supuesto computacional de Diffie-Hellman

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

Consideremos un grupo cíclico G de orden  q . El supuesto 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 los logaritmos discretos

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

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

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

El cálculo del 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 del logaritmo discreto es equivalente al supuesto CDH, aunque en ciertos casos especiales se puede demostrar que es así. ^{[3] [4]}

Relación con el supuesto decisional de Diffie-Hellman

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

Muchos esquemas criptográficos que se construyen 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.

Hay construcciones concretas de grupos en los que el supuesto DDH más fuerte no se cumple, pero el supuesto CDH más débil 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 , calcular ; ^[7] ${\displaystyle g,g^{x}}$ ${\displaystyle g^{x^{2}}}$
• Problema Diffie–Hellman computacional inverso (InvCDH): En la entrada , calcula ; ^[8] ${\displaystyle g,g^{x}}$ ${\displaystyle g^{x^{-1}}}$
• Problema de Diffie-Hellman de cálculo divisible (DCDH): En la entrada , calcular ; ${\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 Diffie–Hellman co-computacional (co-CDH): Dados y , calcule ; ^[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 el logaritmo 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 del método Diffie-Hellman de decisión del método 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 equitativo de claves con un período de tiempo limitado (o cómo hacer cumplir la expiración del tiempo criptográficamente)" (PDF) , Depósito equitativo de claves con un período de tiempo limitado (o cómo hacer cumplir la expiración del tiempo criptográficamente) , Lecture Notes in Computer Science, 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 digitales anónimas con no repudio directo" (PDF) , Advances in Cryptology — 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 de Weil" (PDF) , Journal of Cryptology , 17 (4): 297–319, doi :10.1007/s00145-004-0314-9, S2CID  929219