Decisión basada en un supuesto lineal

La suposición de linealidad de decisión ( suposición DLIN ) es una suposición de dificultad computacional utilizada en criptografía de curva elíptica . En particular, la suposición DLIN es útil en entornos donde la suposición decisional de Diffie-Hellman no se cumple (como suele ocurrir en la criptografía basada en emparejamientos ). La suposición de linealidad de decisión fue introducida por Boneh , Boyen y Shacham. ^{[ 1 ]}

De manera informal, la suposición de DLIN establece que dado${\displaystyle (u,\,v,\,h,\,u^{x},\,v^{y})}$, con${\displaystyle u,\,v,\,h}$elementos de grupo aleatorios y${\displaystyle x,\,y}$exponentes aleatorios, es difícil distinguir${\displaystyle h^{x+y}}$de un elemento de grupo aleatorio independiente${\displaystyle \eta }$.

En la criptografía basada en emparejamiento simétrico, el grupo${\displaystyle G}$está equipado con un emparejamiento${\displaystyle e:G\times G\to T}$que es bilineal . Este mapa proporciona un algoritmo eficiente para resolver el problema de decisión de Diffie-Hellman . ^{[ 2 ]} Dado el input${\displaystyle (g,\,g^{a},\,g^{b},\,h)}$, es fácil comprobar si${\displaystyle h}$es igual a${\displaystyle g^{ab}}$. Esto se deduce utilizando el emparejamiento: tenga en cuenta que

${\displaystyle e(g^{a},g^{b})=e(g,g)^{ab}=e(g,g^{ab}).}$

Por lo tanto, si${\displaystyle h=g^{ab}}$, entonces los valores${\displaystyle e(g^{a},g^{b})}$y${\displaystyle e(g,h)}$serán iguales.

Dado que este supuesto criptográfico, esencial para la creación de cifrado y firmas ElGamal , no se cumple en este caso, se necesitan nuevos supuestos para desarrollar criptografía en grupos bilineales simétricos. El supuesto DLIN es una modificación de los supuestos de tipo Diffie-Hellman para contrarrestar el ataque mencionado.

Dejar${\displaystyle G}$ser un grupo cíclico de orden primo${\displaystyle p}$. Dejar${\displaystyle u}$,${\displaystyle v}$, y${\displaystyle h}$ser generadores aleatorios uniformes de${\displaystyle G}$. Dejar${\displaystyle a,b}$ser elementos aleatorios uniformes de${\displaystyle \{1,\,2,\,\dots ,\,p-1\}}$Definir una distribución

${\displaystyle D_{1}=(u,\,v,\,h,\,u^{a},\,v^{b},\,h^{a+b}).}$

Dejar${\displaystyle \eta }$ser otro elemento aleatorio uniforme de${\displaystyle G}$Defina otra distribución

${\displaystyle D_{2}=(u,\,v,\,h,\,u^{a},\,v^{b},\,\eta ).}$

El supuesto de decisión lineal establece que${\displaystyle D_{1}}$y${\displaystyle D_{2}}$son indistinguibles desde el punto de vista computacional .