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 DLIN establece que, dado , con elementos de grupo aleatorios y exponentes aleatorios, es difícil distinguirlo de un elemento de grupo aleatorio independiente . ${\displaystyle (u,\,v,\,h,\,u^{x},\,v^{y})}$${\displaystyle u,\,v,\,h}$${\displaystyle x,\,y}$${\displaystyle h^{x+y}}$${\displaystyle \eta }$

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

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

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

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.

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

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

Sea otro elemento aleatorio uniforme de . Definamos otra distribución ${\displaystyle \eta }$${\displaystyle G}$

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

La suposición de decisión lineal establece que y son computacionalmente indistinguibles . ${\displaystyle D_{1}}$${\displaystyle D_{2}}$

Boneh, Boyen y Shacham definen un esquema de cifrado de clave pública por analogía con el cifrado ElGamal. ^{[ 1 ]} En este esquema, una clave pública son los generadores . La clave privada son dos exponentes tales que . El cifrado combina un mensaje con la clave pública para crear un texto cifrado. ${\displaystyle u,v,h}$${\displaystyle u^{x}=v^{y}=h}$${\displaystyle m\in G}$

${\displaystyle c:=(c_{1},\,c_{2},\,c_{3})=(u^{a},\,v^{b},\,m\cdot h^{a+b})}$.

Para descifrar el texto cifrado, se puede utilizar la clave privada para calcular

${\displaystyle m':=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}.}$

Para comprobar que este esquema de cifrado es correcto , es decir, cuando ambas partes siguen el protocolo, tenga en cuenta que ${\displaystyle m'=m}$

${\displaystyle m'=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{a})^{x}\cdot (v^{b})^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{x})^{a}\cdot (v^{y})^{b})^{-1}.}$

Luego, utilizando el hecho de que produce ${\displaystyle u^{x}=v^{y}=h}$

${\displaystyle m'=m\cdot h^{a+b}\cdot (h^{a}\cdot h^{b})^{-1}=m\cdot (h^{a+b}\cdot h^{-a-b})=m.}$

Además, este esquema es seguro según la normativa IND-CPA, siempre que se cumpla la suposición de DLIN.

Boneh, Boyen y Shacham también utilizan DLIN en un esquema para firmas de grupo . ^{[ 1 ]} Las firmas se denominan "firmas de grupo cortas" porque, con un nivel de seguridad estándar , pueden representarse en solo 250 bytes .

Su protocolo utiliza primero el cifrado lineal para definir un tipo especial de prueba de conocimiento cero . A continuación , se aplica la heurística Fiat-Shamir para transformar el sistema de prueba en una firma digital . Demuestran que esta firma cumple con los requisitos adicionales de infalsificación, anonimato y trazabilidad exigidos para una firma grupal.

Su prueba se basa no solo en la suposición DLIN sino también en otra suposición llamada suposición de Diffie-Hellman fuerte . Se demuestra en el modelo de oráculo aleatorio . ${\displaystyle q}$

Desde su definición en 2004, la suposición de decisión lineal ha tenido diversas aplicaciones. Estas incluyen la construcción de una función pseudoaleatoria que generaliza la construcción de Naor-Reingold , ^{[ 3 ]} un esquema de cifrado basado en atributos , ^{[ 4 ]} y una clase especial de pruebas de conocimiento cero no interactivas . ^{[ 5 ]}