Supuesto decisional de Diffie-Hellman

El supuesto de Diffie-Hellman decisional (DDH) es un supuesto de dificultad computacional sobre un determinado problema que involucra logaritmos discretos en grupos cíclicos . Se utiliza como base para demostrar la seguridad de muchos protocolos criptográficos , en particular los criptosistemas ElGamal y Cramer-Shoup .

Definición

Consideremos un grupo cíclico (multiplicativo) de orden , y con generador . El supuesto DDH establece que, dados y para , elegidos de manera uniforme e independiente , el valor "parece" un elemento aleatorio en . ${\displaystyle G}$ ${\displaystyle q}$ ${\displaystyle g}$ ${\displaystyle g^{a}}$ ${\displaystyle g^{b}}$ ${\displaystyle a,b\in \mathbb {Z} _{q}}$ ${\displaystyle g^{ab}}$ ${\displaystyle G}$

Esta noción intuitiva se puede expresar formalmente diciendo que las siguientes dos distribuciones de probabilidad son computacionalmente indistinguibles (en el parámetro de seguridad , ): ${\displaystyle n=\log(q)}$

• ${\displaystyle (g^{a},g^{b},g^{ab})}$, donde y se eligen aleatoriamente e independientemente de . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \mathbb {Z} _{q}}$
• ${\displaystyle (g^{a},g^{b},g^{c})}$, donde se eligen aleatoriamente e independientemente de . ${\displaystyle a,b,c}$ ${\displaystyle \mathbb {Z} _{q}}$

Los triples del primer tipo a menudo se denominan tripletes DDH o tuplas DDH .

Relación con otros supuestos

El supuesto DDH está relacionado con el supuesto de logaritmo discreto . Si fuera posible calcular de manera eficiente logaritmos discretos en , entonces el supuesto DDH no se cumpliría en . Dado , uno podría decidir de manera eficiente si tomando primero el discreto de , y luego comparando con . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle (g^{a},g^{b},z)}$ ${\displaystyle z=g^{ab}}$ ${\displaystyle \log _{g}}$ ${\displaystyle g^{a}}$ ${\displaystyle z}$ ${\displaystyle (g^{b})^{a}}$

Se considera que la suposición DDH es una suposición más sólida que la suposición de logaritmo discreto, porque hay grupos para los que se cree que calcular logaritmos discretos es difícil (y, por lo tanto, se cree que la suposición DL es verdadera), pero detectar tuplas DDH es fácil (y, por lo tanto, la suposición DDH es falsa). Debido a esto, se cree que exigir que la suposición DDH se cumpla en un grupo es un requisito más restrictivo que DL.

El supuesto DDH también está relacionado con el supuesto computacional Diffie-Hellman (CDH). Si fuera posible calcular de manera eficiente a partir de , entonces se podrían distinguir fácilmente las dos distribuciones de probabilidad anteriores. Se considera que DDH es un supuesto más sólido que CDH porque si se resuelve CDH, lo que significa que podemos obtener , la respuesta a DDH será obvia. ${\displaystyle g^{ab}}$ ${\displaystyle (g^{a},g^{b})}$ ${\displaystyle g^{ab}}$

Otras propiedades

El problema de detectar tuplas DDH es aleatorio y autoreducible , lo que significa, aproximadamente, que si es difícil incluso para una pequeña fracción de entradas, es difícil para casi todas las entradas; si es fácil incluso para una pequeña fracción de entradas, es fácil para casi todas las entradas.

Grupos para los que se supone que se cumple la DDH

Al utilizar un protocolo criptográfico cuya seguridad depende del supuesto DDH, es importante que el protocolo se implemente utilizando grupos en los que se cree que se cumple el DDH:

• El subgrupo de residuos -ésimos módulo un primo , donde también es un primo grande (también llamado grupo de Schnorr ). Para el caso de , esto corresponde al grupo de residuos cuadráticos módulo un primo seguro . ${\displaystyle \mathbb {G} _{q}}$ ${\displaystyle k}$ ${\displaystyle p=kq+1}$ ${\displaystyle q}$ ${\displaystyle k=2}$
• El grupo cociente para un primo seguro , que consta de las clases laterales . Estas clases laterales se pueden representar por , lo que implica . Dado que y son isomorfos, y el isomorfismo se puede calcular de manera eficiente en ambas direcciones, la DDH es igualmente difícil en ambos grupos. ${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$ ${\displaystyle p=2q+1}$ ${\displaystyle \{\{1,-1\},\ldots \{q,-q\}\}}$ ${\displaystyle \{x,-x\}}$ ${\displaystyle x}$ ${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}\equiv \{1,\ldots ,q\}}$ ${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$ ${\displaystyle \mathbb {G} _{q}}$
• Una curva elíptica de orden primo sobre el campo , donde es primo, siempre que tenga un grado de incrustación grande. ${\displaystyle E}$ ${\displaystyle GF(p)}$ ${\displaystyle p}$ ${\displaystyle E}$
• Un jacobiano de una curva hiperelíptica sobre el cuerpo con un número primo de divisores reducidos, donde es primo, siempre que el jacobiano tenga un grado de incrustación grande. ${\displaystyle GF(p)}$ ${\displaystyle p}$

Es importante destacar que la suposición DDH no se cumple en el grupo multiplicativo , donde es primo. Esto se debe a que si es un generador de , entonces el símbolo de Legendre de revela si es par o impar. Dados , y , uno puede calcular y comparar eficientemente el bit menos significativo de , y , respectivamente, lo que proporciona un método probabilístico para distinguirlo de un elemento de grupo aleatorio. ${\displaystyle \mathbb {Z} _{p}^{*}}$ ${\displaystyle p}$ ${\displaystyle g}$ ${\displaystyle \mathbb {Z} _{p}^{*}}$ ${\displaystyle g^{a}}$ ${\displaystyle a}$ ${\displaystyle g^{a}}$ ${\displaystyle g^{b}}$ ${\displaystyle g^{ab}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle ab}$ ${\displaystyle g^{ab}}$

La suposición DDH no se cumple en curvas elípticas sobre con un grado de incrustación pequeño (por ejemplo, menor que ), una clase que incluye curvas elípticas supersingulares . Esto se debe a que el emparejamiento de Weil o el emparejamiento de Tate se pueden usar para resolver el problema directamente de la siguiente manera: dada en una curva de este tipo, se puede calcular y . Por la bilinealidad de los emparejamientos, las dos expresiones son iguales si y solo si módulo el orden de . Si el grado de incrustación es grande (digamos alrededor del tamaño de ), entonces la suposición DDH seguirá siendo válida porque el emparejamiento no se puede calcular. Incluso si el grado de incrustación es pequeño, hay algunos subgrupos de la curva en los que se cree que se cumple la suposición DDH. ${\displaystyle GF(p)}$ ${\displaystyle \log ^{2}(p)}$ ${\displaystyle P,aP,bP,cP}$ ${\displaystyle e(P,cP)}$ ${\displaystyle e(aP,bP)}$ ${\displaystyle ab=c}$ ${\displaystyle P}$ ${\displaystyle p}$

Véase también

• Problema de Diffie-Hellman
• Intercambio de claves Diffie-Hellman
• Supuestos de dureza computacional
• Supuesto XDH
• Supuesto lineal de decisión

Referencias

• Boneh, Dan (1998). "El problema de decisión Diffie-Hellman". Actas del Tercer Simposio de Teoría Algorítmica de Números . Apuntes de clase en Ciencias de la Computación. Vol. 1423. págs. 48–63. CiteSeerX  10.1.1.461.9971 . doi :10.1007/BFb0054851. ISBN. 978-3-540-64657-0.