El supuesto externo de Diffie-Hellman (XDH) es un supuesto de dureza computacional que se utiliza en la criptografía de curva elíptica . La suposición de XDH sostiene que existen ciertos subgrupos de curvas elípticas que tienen propiedades útiles para la criptografía. Específicamente, XDH implica la existencia de dos grupos distintos con las siguientes propiedades:
- El problema del logaritmo discreto (DLP), el problema computacional de Diffie-Hellman (CDH) y el problema computacional de co-Diffie-Hellman son todos intratables en y .
- Existe un mapa bilineal computable de manera eficiente (emparejamiento).
- El problema decisional de Diffie-Hellman (DDH) es intratable en.
La formulación anterior se denomina XDH asimétrica . Una versión más fuerte de la suposición ( XDH simétrica o SXDH ) es válida si la DDH también es intratable en.
La suposición de XDH se utiliza en algunos protocolos criptográficos basados en emparejamiento . En ciertos subgrupos de curvas elípticas, la existencia de un mapa bilineal computable de manera eficiente (emparejamiento) puede permitir soluciones prácticas al problema de DDH . Estos grupos, denominados grupos gap Diffie-Hellman (GDH), facilitan una variedad de protocolos criptográficos novedosos, incluido el intercambio de claves tripartito , el cifrado basado en identidad y los apretones de manos secretos (por nombrar algunos). Sin embargo, la facilidad de calcular DDH dentro de un grupo GDH también puede ser un obstáculo al construir criptosistemas; por ejemplo, no es posible utilizar criptosistemas basados en DDH como ElGamal dentro de un grupo GDH. Debido a que la suposición de DDH se mantiene dentro de al menos uno de un par de grupos XDH, estos grupos se pueden usar para construir protocolos basados en emparejamiento que permiten el cifrado de estilo ElGamal y otras técnicas criptográficas novedosas.
En la práctica, se cree que la suposición XDH puede ser válida en ciertos subgrupos de curvas elípticas MNT . Esta noción fue propuesta por primera vez por Scott (2002), y luego por Boneh , Boyen y Shacham (2002) como un medio para mejorar la eficiencia de un esquema de firma. El supuesto fue definido formalmente por Ballard, Green, de Medeiros y Monrose (2005), y en ese trabajo se adelantaron los detalles completos de una implementación propuesta. La evidencia de la validez de este supuesto es la prueba de Verheul (2001) y Galbraith y Rotger (2004) de la inexistencia de mapas de distorsión en dos subgrupos específicos de curvas elípticas que poseen un emparejamiento eficientemente computable. Como los emparejamientos y los mapas de distorsión son actualmente los únicos medios conocidos para resolver el problema de DDH en grupos de curvas elípticas, se cree que el supuesto de DDH por lo tanto se mantiene en estos subgrupos, mientras que los emparejamientos aún son factibles entre elementos en grupos distintos.
Referencias
- Mike Scott. Intercambio basado en ID autenticado e inicio de sesión remoto con token y PIN simples . Archivo de impresión electrónica (2002/164), 2002. ( archivo pdf )
- Dan Boneh , Xavier Boyen, Hovav Shacham. Firmas de grupo corto. CRYPTO 2004. ( archivo pdf )
- Lucas Ballard, Matthew Green, Breno de Medeiros, Fabian Monrose. Almacenamiento resistente a la correlación mediante cifrado con búsqueda de palabras clave. Archivo de impresión electrónica (2005/417), 2005. ( archivo pdf )
- Steven D Galbraith, Victor Rotger. Grupos Diffie-Hellman de decisión fácil. Revista LMS de Computación y Matemáticas, agosto de 2004. ( [1] )
- ER Verheul, Evidencia de que XTR es más seguro que los criptosistemas de curva elíptica supersingular, en B. Pfitzmann (ed.) EUROCRYPT 2001, Springer LNCS 2045 (2001) 195-210. [2]