Criptografía basada en emparejamiento

La criptografía basada en emparejamiento es el uso de un emparejamiento entre elementos de dos grupos criptográficos con 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 primo , dos grupos cíclicos aditivos de orden primo y otro grupo cíclico de orden escrito multiplicativamente. Un emparejamiento es un mapa: , 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 existe un homomorfismo eficientemente computable ; ${\displaystyle \phi :G_{2}\to G_{1}}$
3. ${\displaystyle G_{1}\neq G_{2}}$y no existen homomorfismos eficientemente computables entre y . ^[2] ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

Uso en criptografía

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

Por ejemplo, en grupos equipados con un 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 de decisión 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 supuesta diferencia de dificultad entre estos dos problemas en el grupo. ^[3]

Sea un par bilineal no degenerado, computable eficientemente. Sea un generador de . Considere un ejemplo del problema CDH , , . Intuitivamente, la función de emparejamiento no nos ayuda a calcular la solución al problema CDH. Se conjetura que este ejemplo del problema de la 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})}$

Al usar la propiedad bilineal de los tiempos, vemos que si , entonces, puesto 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 se utilizaron por primera vez para criptoanálisis , ^[4] los emparejamientos también se han utilizado para construir muchos sistemas criptográficos para los cuales no se conoce ninguna otra implementación eficiente, como el cifrado basado en identidad o esquemas de cifrado basados ​​en atributos . Por lo tanto, el nivel de seguridad de algunas curvas elípticas amigables 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 pares bilineales se ejemplifica en el esquema de firma digital BLS . ^[3]

La criptografía basada en emparejamiento se basa en supuestos de dureza separados 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 logaritmos discretos en algunos grupos de emparejamientos resultantes. Existen varias variantes del algoritmo de tamiz de campo numérico de torres múltiples 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 nuevas mejoras. ^[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 emparejamiento.

Referencias

1. Koblitz, Neal; Menezes, Alfred (2005). "Criptografía basada en emparejamiento con altos niveles de seguridad". Criptografía y codificación . Apuntes de conferencias sobre informática. vol. 3796, págs. 13–36. doi :10.1007/11586821_2. ISBN 978-3-540-30276-6.
2. Galbraith, Steven; Paterson, Kenneth; Inteligente, Nigel (2008). "Emparejamientos para criptógrafos". Matemática Aplicada Discreta . 156 (16): 3113–3121. doi : 10.1016/j.dam.2007.12.010 .
3. Boneh, Dan; Lynn, Ben; Shacham, Hovav (2001). Boyd, Colin (ed.). "Firmas breves del emparejamiento Weil". Avances en criptología - ASIACRYPT 2001 . Berlín, Heidelberg: Springer: 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). "Reducir logaritmos de curva elíptica a logaritmos en un campo finito". Transacciones IEEE sobre teoría de la información . 39 (5): 1639-1646. doi : 10.1109/18.259647.
5. "NICT, la Universidad de Kyushu y los laboratorios Fujitsu logran un criptoanálisis récord mundial de criptografía de próxima generación". Nota de prensa del NTIC . 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 medio-prime". Archivo ePrint 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 (torre)". Avances en las Matemáticas de las Comunicaciones . doi : 10.3934/amc.2019028 .
8. Menezes, Alfred; Sarkar, Palash; Singh, Shashank (2016), Desafíos de evaluar el 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, ISBN 978-3-319-61272-0
9. Barbulescu, Razvan; Duquesne, Sylvain (1 de octubre de 2019). "Actualización de estimaciones de 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