Mapa criptográfico multilineal

Un mapa criptográfico ${\displaystyle 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}\in 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}$

Definición

Paranorte= 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: ${\displaystyle G_{1},G_{2}}$ ${\displaystyle q}$ ${\displaystyle G_{T}}$ ${\displaystyle 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}}$

Caso general (para cualquiernorte)

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}}$

Candidatos

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.

Referencias

1. Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). "Protocolos criptográficos basados ​​en emparejamiento: una encuesta". e-Print IACR .
2. Boneh, Dan; Silverberg, Alice (2003). "Aplicaciones de formas multilineales a la criptografía". Temas de geometría algebraica y no conmutativa. Matemáticas contemporáneas. Vol. 324. págs. 71–90. doi :10.1090/conm/324/05731. ISBN . 9780821832097. Recuperado el 14 de marzo de 2018 .
3. Albrecht, Martin R. "¿Ya se rompió el sistema de codificación gradual?" . Consultado el 14 de marzo de 2018 .
4. Koblitz, Neal; Menezes, Alfred (2005). "Criptografía basada en emparejamiento con altos niveles de seguridad". Criptografía y codificación . Apuntes de clase en informática. Vol. 3796. págs. 13–36. doi :10.1007/11586821_2. ISBN 978-3-540-30276-6.
5. Garg, Sanjam; Gentry, Craig; Halevi, Shai (2013). "Mapas multilineales candidatos a partir de redes ideales". Avances en criptología – EUROCRYPT 2013. Apuntes de clase en informática. Vol. 7881. págs. 1–17. doi : 10.1007/978-3-642-38348-9_1 . ISBN . 978-3-642-38347-2Archivado del original el 18 de junio de 2022 – vía SpringerLink.
6. Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi (2013). "Mapas multilineales prácticos sobre números enteros". Avances en criptología – CRYPTO 2013. Apuntes de clase en informática. Vol. 8042. págs. 476–493. doi : 10.1007/978-3-642-40041-4_26 . ISBN . 978-3-642-40040-7Archivado del original el 20 de enero de 2022 – vía SpringerLink.
7. Gentry, Craig; Gorbunov, Sergey; Halevi, Shai (2015). "Mapas multilineales inducidos por grafos a partir de retículos". Teoría de la criptografía . Apuntes de clase en informática. Vol. 9015. págs. 498–527. doi : 10.1007/978-3-662-46497-7_20 . ISBN. 978-3-662-46496-0Archivado del original el 19 de abril de 2022 – vía SpringerLink.