Suposición XDH

La suposición de Diffie-Hellman externa (XDH) es una suposición de dificultad computacional utilizada en la criptografía de curvas elípticas . La suposición XDH se cumple si existen ciertos subgrupos de curvas elípticas que poseen propiedades útiles para la criptografía. Específicamente, XDH implica la existencia de dos grupos distintos.${\displaystyle \langle {\mathbb {G} }_{1},{\mathbb {G} }_{2}\rangle }$con las siguientes propiedades:

1. El problema del logaritmo discreto (DLP), el problema computacional de Diffie-Hellman (CDH) y el problema co-computacional de Diffie-Hellman son todos intratables en${\displaystyle {\mathbb {G} }_{1}}$y${\displaystyle {\mathbb {G} }_{2}}$.
2. Existe un mapeo bilineal (emparejamiento) computable de manera eficiente.${\displaystyle e(\cdot ,\cdot ):{\mathbb {G} }_{1}\times {\mathbb {G} }_{2}\rightarrow {\mathbb {G} }_{T}}$.
3. El problema de decisión de Diffie-Hellman (DDH) es intratable en${\displaystyle {\mathbb {G} }_{1}}$.

La formulación anterior se denomina XDH asimétrica . Una versión más fuerte de la suposición ( XDH simétrica o SXDH ) se cumple si DDH también es intratable en${\displaystyle {\mathbb {G} }_{2}}$.

La suposición XDH se utiliza en algunos protocolos criptográficos basados ​​en emparejamientos . En ciertos subgrupos de curvas elípticas, la existencia de un mapeo bilineal (emparejamiento) computable eficientemente permite soluciones prácticas al problema DDH . Estos grupos, denominados grupos Diffie-Hellman con brecha (GDH), facilitan diversos protocolos criptográficos novedosos, como el intercambio de claves tripartito , el cifrado basado en identidad y los intercambios de claves secretos (entre otros). Sin embargo, la facilidad para 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. Dado que la suposición DDH se cumple en al menos uno de un par de grupos XDH, estos grupos pueden utilizarse para construir protocolos basados ​​en emparejamientos que permiten el cifrado al estilo ElGamal y otras técnicas criptográficas novedosas.

En la práctica, se cree que la suposición XDH puede cumplirse en ciertos subgrupos de curvas elípticas MNT . Esta idea fue propuesta inicialmente por Scott (2002) y posteriormente por Boneh , Boyen y Shacham (2002) como un medio para mejorar la eficiencia de un esquema de firma. La suposición fue definida formalmente por Ballard, Green, de Medeiros y Monrose (2005), y en ese trabajo se presentaron todos los detalles de una implementación propuesta. La evidencia de la validez de esta suposición reside en la demostración 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 computable eficientemente. Dado que los emparejamientos y los mapas de distorsión son actualmente los únicos medios conocidos para resolver el problema DDH en grupos de curvas elípticas, se cree que la suposición DDH se cumple en estos subgrupos, mientras que los emparejamientos siguen siendo factibles entre elementos de grupos distintos.

1. Mike Scott. Intercambio autenticado basado en ID e inicio de sesión remoto con token y PIN simples . Archivo de preimpresiones (2002/164), 2002. ( archivo pdf )
2. Dan Boneh , Xavier Boyen, Hovav Shacham. Firmas de grupo cortas. CRYPTO 2004. ( archivo pdf )
3. Lucas Ballard, Matthew Green, Breno de Medeiros, Fabian Monrose. Almacenamiento resistente a la correlación mediante cifrado con búsqueda por palabras clave. Archivo de preimpresiones (2005/417), 2005. ( archivo pdf )
4. Steven D Galbraith, Victor Rotger. Grupos Diffie - Hellman de decisión fácil . LMS Journal of Computation and Mathematics, agosto de 2004. (Archivado el 27/10/2005 en Wayback Machine )
5. 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.