Mapa criptográfico multilineal

Un mapa criptográfico${\estilo de visualización n}$ -multilineal es un tipo de mapa multilineal , es decir, una función tal que para cualquier número entero y elemento , , y que además es eficientemente computable y satisface algunas propiedades de seguridad. Tiene varias aplicaciones en criptografía, como protocolos de intercambio de claves , cifrado basado en identidad y cifrado de difusión . Existen construcciones de mapas criptográficos 2-multilineales, conocidos como mapas bilineales, ^[1] sin embargo, el problema de construir tales mapas multilineales ^[1] para parece mucho más difícil ^[2] y la seguridad de los candidatos propuestos aún no está clara. ^[3]${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$${\displaystyle a_{1},\ldots ,a_{n}}$${\displaystyle g_{i}\en G_{i}}$${\displaystyle e(g_{1}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,g_{n})^{\prod _{i=1}^{n}a_{i}}}$${\displaystyle n>2}$

En este caso, las aplicaciones multilineales se conocen principalmente como aplicaciones bilineales o emparejamientos, y suelen definirse de la siguiente manera: ^[4] Sean dos grupos cíclicos aditivos de orden primo , y otro grupo cíclico de orden escrito multiplicativamente. Un emparejamiento es una aplicación: , que satisface las siguientes propiedades: $Estilo de visualización G1, G2$${\estilo de visualización q}$$Estilo de visualización G_{T}}$${\estilo de visualización q}$${\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T}}$

Bilinealidad

${\displaystyle \forall a,b\in F_{q}^{*},\ \forall P\in G_{1},Q\in G_{2}:\ e(aP,bQ)=e(P,Q)^{ab}}$

No degeneración

Si y son generadores de y , respectivamente, entonces es un generador de .${\displaystyle g_{1}}$${\displaystyle g_{2}}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle e(g_{1},g_{2})}$${\displaystyle G_{T}}$

Computabilidad

Existe un algoritmo eficiente para calcular .${\displaystyle e}$

Además, por motivos de seguridad, se requiere que el problema del logaritmo discreto sea difícil tanto en como en . ${\displaystyle G_{1}}$${\displaystyle G_{2}}$

Decimos que un mapa es un mapa -multilineal si satisface las siguientes propiedades: ${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$${\displaystyle n}$

1. Todos (para ) y son grupos del mismo orden;${\displaystyle G_{i}}$${\displaystyle 1\leq i\leq n}$${\displaystyle G_{T}}$
2. si y , entonces ;${\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {Z} }$${\displaystyle (g_{1},\ldots ,g_{n})\in G_{1}\times \cdots \times G_{n}}$${\displaystyle e(g_{1}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,g_{n})^{\prod _{i=1}^{n}a_{i}}}$
3. el mapa no es degenerado en el sentido de que si son generadores de , respectivamente, entonces es un generador de${\displaystyle g_{1},\ldots ,g_{n}}$${\displaystyle G_{1},\ldots ,G_{n}}$${\displaystyle e(g_{1},\ldots ,g_{n})}$${\displaystyle G_{T}}$
4. Existe un algoritmo eficiente para calcular .${\displaystyle e}$

Además, por motivos de seguridad, se requiere que el problema del logaritmo discreto sea difícil . ${\displaystyle G_{1},\ldots ,G_{n}}$

Todos los mapas multilineales candidatos son en realidad generalizaciones leves de mapas multilineales conocidos como sistemas de codificación gradual, ya que permiten que el mapa se aplique parcialmente: en lugar de aplicarse en todos los valores a la vez, lo que produciría un valor en el conjunto objetivo , es posible aplicarlo a algunos valores, lo que genera valores en conjuntos objetivo intermedios. Por ejemplo, para , es posible hacer then . ${\displaystyle e}$${\displaystyle n}$${\displaystyle G_{T}}$${\displaystyle e}$${\displaystyle n=3}$${\displaystyle y=e(g_{2},g_{3})\in G_{T_{2}}}$${\displaystyle e(g_{1},y)\in G_{T}}$

Los tres candidatos principales son GGH13, ^[5] que se basa en ideales de anillos polinomiales ; CLT13, ^[6] que se basa en un problema MCD aproximado y funciona con números enteros, por lo tanto, se supone que es más fácil de entender que el mapa multilineal GGH13; y GGH15, ^[7] que se basa en gráficos.