Criptografía basada en emparejamiento

La criptografía basada en emparejamiento es el uso de un emparejamiento entre elementos de dos grupos criptográficos a un tercer grupo con un mapeo para construir o analizar sistemas criptográficos . ${\displaystyle e:G_{1}\times G_{2}\to G_{T}}$

Definición

La siguiente definición se utiliza comúnmente en la mayoría de los artículos académicos. ^[1]

Sea un cuerpo finito sobre primos , dos grupos cíclicos aditivos de orden primo y otro grupo cíclico de orden escrito multiplicativamente. Un emparejamiento es una función: , que satisface las siguientes propiedades: ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q}$ ${\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 \mathbb {F} _{q}^{*},P\in G_{1},Q\in G_{2}:\ e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}}$

No degeneración

${\displaystyle e\neq 1}$

Computabilidad

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

Clasificación

Si se utiliza el mismo grupo para los dos primeros grupos (es decir, ), el emparejamiento se denomina simétrico y es una asignación de dos elementos de un grupo a un elemento de un segundo grupo. ${\displaystyle G_{1}=G_{2}}$

Algunos investigadores clasifican las instancias de emparejamiento en tres (o más) tipos básicos:

1. ${\displaystyle G_{1}=G_{2}}$;
2. ${\displaystyle G_{1}\neq G_{2}}$pero hay un homomorfismo computable eficientemente ; ${\displaystyle \phi :G_{2}\to G_{1}}$
3. ${\displaystyle G_{1}\neq G_{2}}$y no existen homomorfismos computables eficientemente entre y . ^[2] ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

Uso en criptografía

Si son simétricos, los emparejamientos se pueden utilizar para reducir un problema difícil en un grupo a un problema diferente, normalmente más fácil, en otro grupo.

Por ejemplo, en grupos equipados con una función de mapeo bilineal como el emparejamiento de Weil o el emparejamiento de Tate , se cree que las generalizaciones del problema computacional de Diffie-Hellman son inviables, mientras que el problema decisorio más simple de Diffie-Hellman se puede resolver fácilmente utilizando la función de emparejamiento. El primer grupo a veces se denomina grupo Gap debido a la diferencia supuesta en dificultad entre estos dos problemas en el grupo. ^[3]

Sea un emparejamiento bilineal, no degenerado y computable de manera eficiente. Sea un generador de . Consideremos una instancia del problema CDH , , , . Intuitivamente, la función de emparejamiento no nos ayuda a calcular , la solución al problema CDH. Se conjetura que esta instancia del problema CDH es intratable. Dado , podemos verificar si sin conocimiento de , , y , probando si se cumple. ${\displaystyle e}$ ${\displaystyle g}$ ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle g^{x}}$ ${\displaystyle g^{y}}$ ${\displaystyle e}$ ${\displaystyle g^{xy}}$ ${\displaystyle g^{z}}$ ${\displaystyle g^{z}=g^{xy}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle e(g^{x},g^{y})=e(g,g^{z})}$

Utilizando la propiedad bilineal de los tiempos, vemos que si , entonces, dado que es un grupo de orden primo, . ${\displaystyle x+y+z}$ ${\displaystyle e(g^{x},g^{y})=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^{z})}$ ${\displaystyle G_{T}}$ ${\displaystyle xy=z}$

Aunque en un principio se utilizaron para el criptoanálisis , ^[4] los emparejamientos también se han utilizado para construir muchos sistemas criptográficos para los que no se conoce ninguna otra implementación eficiente, como el cifrado basado en identidad o los esquemas de cifrado basados ​​en atributos . Por lo tanto, el nivel de seguridad de algunas curvas elípticas compatibles con el emparejamiento se ha reducido posteriormente.

La criptografía basada en emparejamiento se utiliza en el esquema de compromiso criptográfico KZG .

Un ejemplo contemporáneo del uso de emparejamientos bilineales se ejemplifica en el esquema de firma digital BLS . ^[3]

La criptografía basada en emparejamiento se basa en supuestos de dureza distintos de, por ejemplo, la criptografía de curva elíptica , que es más antigua y se ha estudiado durante más tiempo.

Criptoanálisis

En junio de 2012, el Instituto Nacional de Tecnología de la Información y las Comunicaciones (NICT), la Universidad de Kyushu y Fujitsu Laboratories Limited mejoraron el límite anterior para calcular con éxito un logaritmo discreto en una curva elíptica supersingular de 676 bits a 923 bits. ^[5]

En 2016, el algoritmo Extended Tower Number Field Sieve ^[6] permitió reducir la complejidad de encontrar el logaritmo discreto en algunos grupos resultantes de emparejamientos. Existen varias variantes del algoritmo Tower Number Field Sieve múltiple y extendido que amplían la aplicabilidad y mejoran la complejidad del algoritmo. En 2019 se publicó una descripción unificada de todos estos algoritmos con mejoras adicionales. ^[7] En vista de estos avances, varios trabajos ^{[8] [9]} proporcionaron estimaciones concretas revisadas sobre los tamaños de clave de los criptosistemas seguros basados ​​en emparejamientos.

Referencias

1. 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.
2. Galbraith, Steven; Paterson, Kenneth; Smart, Nigel (2008). "Emparejamientos para criptógrafos". Matemáticas Aplicadas Discretas . 156 (16): 3113–3121. doi : 10.1016/j.dam.2007.12.010 .
3. Boneh, Dan; Lynn, Ben; Shacham, Hovav (2001). "Firmas breves del emparejamiento de Weil". En Boyd, Colin (ed.). Avances en criptología — ASIACRYPT 2001. Apuntes de clase en informática. Vol. 2248. Berlín, Heidelberg: Springer. págs. 514–532. doi :10.1007/3-540-45682-1_30. ISBN 978-3-540-45682-7.
4. Menezes, Alfred J. Menezes; Okamato, Tatsuaki; Vanstone, Scott A. (1993). "Reducción de logaritmos de curvas elípticas a logaritmos en un cuerpo finito". IEEE Transactions on Information Theory . 39 (5): 1639–1646. doi :10.1109/18.259647.
5. "NICT, la Universidad de Kyushu y los laboratorios Fujitsu logran un récord mundial en criptoanálisis de criptografía de próxima generación". Nota de prensa de NICT . 18 de junio de 2012.
6. Kim, Taechan; Barbulescu, Razvan (2015). "Tamiz de campo numérico de torre extendida: una nueva complejidad para el caso de primos medianos". Archivo de ePrints de criptología .
7. Sarkar, Palash; Singh, Shashank (2019). "Un método de selección polinomial unificado para el algoritmo de tamiz de campo numérico (de torre)". Avances en las matemáticas de las comunicaciones . 13 (3): 435–455. doi : 10.3934/amc.2019028 .
8. Menezes, Alfred; Sarkar, Palash; Singh, Shashank (2016), Desafíos en la evaluación del impacto de los avances de NFS en la seguridad de la criptografía basada en emparejamiento, Lecture Notes in Computer Science, vol. 10311, Springer-Verlag, págs. 83–108, doi :10.1007/978-3-319-61273-7_5, ISBN 978-3-319-61272-0
9. Barbulescu, Razvan; Duquesne, Sylvain (1 de octubre de 2019). "Actualización de las estimaciones del tamaño de clave para emparejamientos". Revista de criptología . 32 (4): 1298–1336. doi :10.1007/s00145-018-9280-5. ISSN  1432-1378. S2CID  253635514.

Enlaces externos

• Conferencia sobre criptografía basada en emparejamiento
• Biblioteca PBC de Ben Lynn