Supuesto lineal de decisión

Supuesto de dureza computacional

El supuesto de decisión lineal (DLIN) es un supuesto de dureza computacional utilizado en criptografía de curva elíptica . En particular, el supuesto DLIN es útil en entornos donde el supuesto de decisión de Diffie-Hellman no se cumple (como suele ser el caso en la criptografía basada en emparejamiento ). El supuesto de decisión lineal fue introducido por Boneh , Boyen y Shacham. ^[1]

De manera informal, el supuesto 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 }$

Motivación

En la criptografía basada en emparejamiento simétrico, el grupo está equipado con un emparejamiento que es bilineal . Este mapa proporciona un algoritmo eficiente para resolver el problema de decisión de Diffie-Hellman . ^[2] Dado el valor de entrada , es fácil comprobar si es igual a . Esto se obtiene 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 construir el cifrado y las firmas de ElGamal , no se cumple en este caso, se necesitan nuevos supuestos para construir la criptografía en grupos bilineales simétricos. El supuesto DLIN es una modificación de los supuestos de tipo Diffie-Hellman para frustrar el ataque anterior.

Definición formal

Sea un grupo cíclico de orden primo . Sean , , y generadores uniformemente aleatorios de . Sean elementos uniformemente aleatorios de . Defina 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 uniformemente aleatorio de . Defina otra distribución ${\displaystyle \eta }$ ${\displaystyle G}$

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

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

Aplicaciones

Cifrado lineal

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 los rendimientos ${\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 IND-CPA suponiendo que se cumple el supuesto DLIN.

Firmas breves de grupos

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 , se pueden representar en solo 250 bytes .

Su protocolo utiliza primero el cifrado lineal para definir un tipo especial de prueba de conocimiento cero . Luego 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 requeridos para una firma de grupo.

Su prueba se basa no sólo en el supuesto DLIN sino también en otro supuesto llamado supuesto Diffie-Hellman q {\displaystyle q} -fuerte. Está probado en el modelo de oráculo aleatorio .

Otras aplicaciones

Desde su definición en 2004, el supuesto de decisión lineal ha tenido diversas aplicaciones, entre ellas 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]

Referencias

1. Dan Boneh , Xavier Boyen, Hovav Shacham: Firmas breves de grupos. CRYPTO 2004: 41–55
2. John Bethencourt: Introducción a los mapas bilineales
3. Allison Bishop Lewko, Brent Waters : Funciones pseudoaleatorias eficientes a partir del supuesto lineal de decisión y variantes más débiles. CCS 2009: 112-120
4. Lucas Kowalczyk, Allison Bishop Lewko: Expansión de entropía bilineal a partir del supuesto lineal de decisión. CRYPTO 2015: 524-541
5. Benoît Libert, Thomas Peters, Marc Joye, Moti Yung : Ocultación compacta de tramos lineales. ASIACRYPT 2015: 681-707